# Icicles - Fuzzy Completion

 Previous: Icicles - Anything Icicles IciclesIndex Next: Icicles - Completion in Other Buffers

## Fuzzy Completion

There are a few kinds of what might be called “fuzzy” matching used in Icicles completion, in addition to apropos (regexp) matching and prefix matching. And if you have your own method of matching then you can use that as well, by adding it to option `icicle-S-TAB-completion-methods-alist’.

The following methods are predefined:

• Fuzzy – This method uses a fairly sophisticated matching algorithm that seems to account for various typing mistakes. This algorithm is provided by library fuzzy-match.el, so I call its use in Iciclesfuzzy completion”. You must have library `fuzzy-match.el` to use this.
• SwankSymbols are completed using the algorithm of el-swank-fuzzy.el – see that library for details.
• Scatter – This is a simple, poor man’s fuzzy matching that I call “scatter matching”. Ido calls it “flex” matching. The TextMate editor has the same thing for file-name matching (only), without naming it.
• Levenshtein – This method checks whether two strings differ by at most a given number of character operations, the so-called Levenshtein distance. You must have library levenshtein.el to use this.
• Jaro-Winkler – This method gives matching weight to having both (a) more characters that match in the right positions (Jaro) and (b) a longer exact prefix within the first four characters (Winkler).

My opinion about the relative usefulness of the various methods: Basic (prefix) completion and apropos completion are by far the most useful. They are followed, in order of decreasing usefulness, by scatter, fuzzy, Levenshtein, vanilla, Jaro-Winkler, and swank completion. YMMV.

Besides these methods, remember that you can get ordinary substring matching with `‘S-TAB’` by using ``C-``’ to turn off (toggle) escaping of regexp special characters. With special characters escaped, `‘S-TAB’` does literal substring completion.

The type of completion matching that is used when you hit `‘S-TAB’` and `‘TAB’` is controlled by user options `‘icicle-S-TAB-completion-methods-alist’` and `‘icicle-TAB-completion-methods’`, respectively. The possible methods for `‘TAB’` are predefined, but you can add additional methods for `‘S-TAB’` by customizing `‘icicle-S-TAB-completion-methods-alist’`.

### Changing Completion Method

You can use fuzzy or swank completion in place of prefix completion (`‘TAB’`). You can use the scatter, Levenshtein, or Jaro-Winkler completion in place of apropos completion (`‘S-TAB’`). You can change completion methods easily at any time, by hitting a key in the minibuffer:

• ``C-(`’ (command `‘icicle-next-TAB-completion-method’`) to cycle among `‘TAB’` completion methods: `‘basic’`, `‘vanilla’`, `‘fuzzy’`, and `‘swank’` (`‘vanilla’` only for Emacs 23 and later; `‘fuzzy’` only if you have library fuzzy-match.el; `‘swank’` only if you have library el-swank-fuzzy.el).
• ``M-(`’ (command `‘icicle-next-S-TAB-completion-method’`) to cycle `‘S-TAB’` completion methods: `‘apropos’`, `‘scatter’`, `‘Levenshtein’`, `‘Levenshtein strict’`, and `‘Jaro-Winkler’` (only if you have the Autocomplete library `fuzzy.el`.

Repeating ``C-(`’ and `‘TAB’` or ``M-(`’ and `‘S-TAB’` on the fly for the same input can be a good way to learn the differences between the various completion methods.

If you provide a prefix argument to ``C-(`’ or ``M-(`’, then the newly chosen method is used only for the current command. More precisely, the previously active method is restored as soon as you return to the top level.

The completion methods available for cycling via ``C-(`’ or ``M-(`’ are defined by options `icicle-TAB-completion-methods’ and `icicle-S-TAB-completion-methods-alist’, respectively. By default, the first method in each list is used for matching.

Sometimes you might want to make a different set of completion methods available during input. You can use options `icicle-TAB-completion-methods-per-command’ and `icicle-S-TAB-completion-methods-per-command’ to do this. These define the methods to be made available during specific commands (that read input with completion). That is, they give you command-specific control over ``C-(`’ and ``M-(`’.

The per-command control is provided by advising (`‘defadvice’`) the particular commands. You can also do this interactively, using commands `‘icicle-set-TAB-methods-for-command’` and `‘icicle-set-S-TAB-methods-for-command’`. Invoking one of these with a negative prefix argument removes the advice, restoring the default choice of methods for the target command.

For example, this sets the available `‘TAB’` methods for command `‘icicle-read-color-wysiwyg’` to fuzzy (the default for this command) and basic:

```  M-x icicle-set-TAB-methods-for-command RET
TAB methods: fuzzy RET
TAB methods: basic RET
TAB methods: RET```

And this removes the special treatment for ``C-(`’ during `‘icicle-read-color-wysiwyg’`, restoring the default `‘TAB’` methods that are defined by option `‘icicle-TAB-completion-methods’`:

```  C-- M-x icicle-set-TAB-methods-for-command RET

### Partial Completion

This section pertains to Emacs releases starting with Emacs 23.

If option `icicle-TAB-completion-methods’ includes `‘vanilla’` (which it does, by default), and you choose `‘vanilla’` completion for `‘TAB’` (by cycling using ``C-(`’ or by customizing `‘icicle-TAB-completion-methods’` to use `‘vanilla’` as the default), then Icicles `‘TAB’` completion respects the standard Emacs option `‘completion-styles’`, so the behavior of `‘TAB’` is similar to what it is in vanilla Emacs.

Emacs includes `‘partial-completion’` in the default value of `‘completion-styles’`. This means that Icicles too will make use of partial completion when you use `‘TAB’` (with `‘vanilla’`). Icicles makes no use of `‘completion-styles’` when you use `‘S-TAB’`.

Partial completion is not really a kind of fuzzy completion, but its effect can sometimes be similar. In some ways, it is similar to scatter-match completion, but it requires you to explicitly mark where to skip ahead (using `‘*’`, `‘ ’` (space), or `‘-’`).

Icicles does not support using the mode `‘partial-completion-mode’`, and Emacs itself is in the process of deprecating it, now that the partial-completion style is active by default.

I do not necessarily recommend using `‘vanilla’` for `‘TAB’` completion, or, if you do, including `‘partial-completion’` as an entry in `‘completion-styles’`, because its effect is often counter-intuitive or confusing. But it is included by default in Emacs, and Icicles supports it. You might find it useful in file-name completion, to be able to complete directory components, for instance.

### Scatter-Match Completion

The idea behind scatter-match completion is very simple: input characters are matched in order against completion candidates, but possibly with intervening characters. That is, your input scatter-matches a completion candidate if each character is also in the candidate, and the character order is respected.

What this really amounts to is matching input `‘abc’` as if it were the regexp ``a.*b.*c`’. That’s all.

You can use Icicles scatter matching at any time in place of apropos (regexp) matching. Unlike the cases of swank and fuzzy completion (see below), you can use it to complete file names also.

### Swank (Fuzzy Symbol) Completion

If you choose `‘swank’` completion, what you get in Icicles is fuzzy completion (see next), except regarding symbols. That is, swank completion per se applies only to symbols. Symbols are completed using the algorithm of el-swank-fuzzy.el – see that library for details.

Icicles options `icicle-swank-timeout’ and `icicle-swank-prefix-length’ give you some control over the behavior. When the `‘TAB’` completion method is `‘swank’`, you can use `‘C-x 1’` (``icicle-doremi-increment-swank-timeout+`’) and `‘C-x 2’` (``icicle-doremi-increment-swank-prefix-length+`’) in the minibuffer to increment these options on the fly using the arrow keys `‘up’` and `‘down’`.

Swank symbol completion uses heuristics that relate to supposedly typical patterns found in symbol names. It also uses a timeout that can limit the number of matches. It is generally quite a bit slower than fuzzy completion, and it sometimes does not provide all candidates that you might think should match, even when all of your input is a prefix (or even when it is already complete!).

If swank completion produces no match when you think it should, remember that you can use ``C-(`’ on the fly to change the completion method.

I do not necessarily recommend swank symbol completion, but it is available for those who appreciate it.

Like fuzzy completion (see next), swank completion always sorts candidate symbols according to its own scoring, putting what it thinks are the best matches first. This means that using ``C-,`’ in the minibuffer to sort candidates differently has no effect.

### Fuzzy-Match Completion

Fuzzy completion takes more explaining. It is described in detail in the commentary of library fuzzy-match.el; please refer to that documentation. Here are some things to keep in mind when you use Icicles fuzzy completion:

• File-name completion is never fuzzy. Basic prefix completion is used for file names.
• Fuzzy completion is always case-sensitive. This means that `‘C-A’` in the minibuffer has no effect on fuzzy completion.
• Fuzzy completion always takes a space prefix in your input into account. This means that ``M-_`’ in the minibuffer has no effect on fuzzy completion.
• Fuzzy completion candidates are always sorted by decreasing match strength. This means that using ``C-,`’ in the minibuffer to sort candidates differently has no effect.

Fuzzy completion is a form of prefix completion in which some input characters might not be present in a matched candidate. Matching finds the candidates that have the most characters in common with your input, in the same order and with a minimum of non-matching characters. It can skip over non-matching characters, as long as the number of characters skipped in the candidate is less that those following them that match. After the matching candidates are found, they are sorted by skip length and then candidate length.

Here are some examples:

 Input Completion Domain Matches (Candidates) `abc` {`xxabcxx`, `xabcxxx`, `xabx`} {`xabcxxx`, `xxabcxx`} `point-mx` Emacs variables {`point-max`, `point-max-marker`} `begining-of-l` Emacs commands {`beginning-of-line`, `beginning-of-line-text`, `move-beginning-of-line`, `widget-beginning-of-line`}

The last example shows that although fuzzy matching is a kind of prefix matching, your input is not necessarily a prefix of each matching candidate. It is prefix matching because it tries to match your input starting at its beginning. This input prefix is matched against candidate substrings, not necessarily candidate prefixes, but the non-matching part (if any) preceding the matched substring must not be longer than the matching part. That is, non-matching substrings can be skipped over, but they must be no longer than the matching substrings that follow them. If an input prefix does not match under these conditions, it is skipped over.

After matching an input prefix this way, the same process is repeated, recursively, for input text following that prefix and for match positions following the matches found. That is, after each such prefix match, the process starts again where it left off in both the input and the candidates. The resulting matches contain one or more substrings of your input that are each at least as long as the non-matching parts that immediately precede them. Only matches with the highest number of matching characters are retained. They are sorted by two criteria: (1) nearness of matches to the start of the candidate and (2) candidate length.

The fuzzy-match algorithm is detailed in library fuzzy-match.el. However, it is easier to get a feel for what it does by trying it than by reading any description. Just give it a try. Do not expect it to rival apropos completion in power or expressivity, however. Instead, think of it as prefix completion for lazy or inaccurate typists! If that sounds like you, then you might find it useful. ;-)

Here are a couple of screenshots of buffer `‘*Completions*’`. The first shows command-name matches for the input `‘fo’`. The second shows command-name matches for the input `‘fol’`.

#### Command-Name Input `fol'

The first thing to notice is the distribution of candidates for input `‘fo’`. Candidates are in decreasing order of match fit:

• The nearer the match to the start of the candidate, the better the fit.
• The greater the ratio of matched text to unmatched text, the better the fit.

Note too the candidate `‘ifconfig’`. First, note that it has no strict match for substring `‘fo’`. Its match is in fact in two parts: `‘f’`, then `‘o’`. Second, note that it is considered a better fuzzy match than the candidate `‘info’`. This is because its match (`‘f’`) is nearer to the start of the candidate (second character, versus third).

The second thing to notice is that when you type the third input character, `‘l’`, the candidates are not a subset of the original set that matches `‘fo’`. The candidates in the second screenshot all match `‘fol’` in a fuzzy way, even though one of them, `‘mh-folder-mode’`, does not match `‘fo’` sufficiently well to be included as a candidate. Why? Because in the `‘fo’` case, the match is only two characters long and it starts after three non-matching characters.

For both screenshots: If all input prefixes are fair game for matching, why doesn’t `‘*Completions*’` also include other command names that match only the prefix `‘f’` and nothing else? Because there is at least one match that matches more than that – only the best matches are retained. In this case, the best matches for input `‘fo’` match both the `‘f’` and the `‘o’`, and the best matches for input `‘fol’` match all three of those characters.

Refer to fuzzy-match.el for a precise description of fuzzy matching. It refers to “matchiness” for how many characters match and “closeness” for the ratio of number of characters matched to candidate length.

Note: It is not practical to try to highlight the exact candidate portions that match different parts of your input. Because fuzzy-match input does not function as a literal string for matching purposes, it is more akin to substring matching than to plain prefix matching. For this reason, regexp-match highlighting is used for fuzzy matching. That is why you see the input `‘fo’` highlighted in `‘*Completions*’` candidates in other than just the prefix position. It is also why the matching `‘f’` and `‘o’` in candidate `‘ifconfig’` are not highlighted: for highlighting purposes, your input is treated as a regexp.

One takeaway here is that fuzzy completion is complicated. Rather than try to understand how it works and think ahead in those terms, you just need to get a feel for it – learn by doing. Have fun!

### Levenshtein Completion

The “Levenshtein distance” is the maximum number of character insertions, deletions, or replacements that are needed to transform one string to another. The more similar two strings are, the smaller their Levenshtein distance.

When this kind of completion is used, Icicles considers your input to match a completion candidate if their Levenshtein distance is no greater than the value of option `icicle-levenshtein-distance’. The default value of the option is 1, meaning that the difference is at most one character operation.

Using a strict definition of the distance, this also requires the length of your input to be within the Levenshtein distance of the length of a completion candidate, for it to match. That is quite restrictive. It is more flexible to consider your input to match a candidate if it is within `‘icicle-levenshtein-distance’` of some substring of the candidate. Because candidate substrings are tested, the length of your input need not be nearly the same as the candidate length.

When you cycle among `‘S-TAB’` completion methods using ``M-(`’, there are thus two choices for Levenshtein completion: `‘Levenshtein’` and `‘Levenshtein strict’`. The former is generally more useful.

The larger the value of `‘icicle-levenshtein-distance’`, the slower Levenshtein completion becomes, since it must test more possibilities. Also, when the value is 1 (except for ````Levenshtein strict```’), Icicles uses a fast, special-case algorithm, and it highlights the matching parts of candidates in buffer `‘*Completions*’`. 1 is the most useful value.

If the value is other than 1 (or if it is 1 with `‘Levenshtein strict’`), then you must also use library levenshtein.el, and Levenshtein completion can be quite slow. In that case, you will no doubt want to turn off incremental completion (``C-`#’).

### Jaro-Winkler Completion

The Jaro-Winkler method was developed for comparing names for the U.S. census. It tends to take into account some typical spelling mistakes, and it is best suited for use with short candidates.

When checking whether two strings match, higher matching weight results when there are more characters in each string that are also present in the other, and in approximately the same positions.

Looking only at those characters that nearly match in this sense (same character in about the same position), the more exact matches there are (same character in exactly the same position), the higher the matching weight. That is, weight is reduced for characters that nearly match but are not quite in the right position.

So far, this describes Jaro matching. The Jaro matching weight is the average of three values; (a) the ratio of the first string’s near matches to its length, the same for the second string, and (c) the ratio of exact matches to total matches (near and exact).

The Winkler part of the method comes from giving additional weight for prefixes that match exactly. The longer the exact prefix match (up to 4 characters) the greater the weight.

Unlike the other matching methods, for Jaro-Winkler to complete your input it must have the same number of characters as the candidate to be matched, plus or minus two (actually `‘fuzzy-accept-length-difference’`). In particular, this means that you cannot hit `‘S-TAB’` with an empty minibuffer to see all of the candidates.