Skip to content

Latest commit

 

History

History
173 lines (120 loc) · 6.63 KB

ALGORITHM.md

File metadata and controls

173 lines (120 loc) · 6.63 KB
Raw

This document describes the scoring algorithm of fzy as well as the algorithm of other similar projects.

Matching vs Scoring

I like to split the problem a fuzzy matchers into two subproblems: matching and scoring.

Matching determines which results are eligible for the list. All the projects here consider this to be the same problem, matching the candidate strings against the search string with any number of gaps.

Scoring determines the order in which the results are sorted. Since scoring is tasked with finding what the human user intended, there is no correct solution. As a result there are large variety in scoring strategies.

fzy's matching

Generally, more time is taken in matching rather than scoring, so it is important that matching be as fast as possible. If this were case sensitive it would be a simple loop calling strchr, but since it needs to be case insensitive.

fzy's scoring

fzy treats scoring as a modified edit distance problem of calculating the Levenshtein distance. Edit distance is the measure of how different two strings are in terms of insertions, deletions, and substitutions. This is the same problems as DNA sequence alignment. Fuzzy matching is a simpler problem which only accepts insertions, not deletions or substitutions.

fzy's scoring is a dynamic programming algorithm similar to Wagner–Fischer and Needleman–Wunsch.

Dynamic programming requires the observation that the result is based on the result of subproblems.

Fzy borrows heavily from concepts in bioinformatics to performs scoring.

Fzy builds a n-by-m matrix, where n is the length of the search string and m the length of the candidate string. Each position (i,j) in the matrix stores the score for matching the first i characters of the search with the first j characters of the candidate.

Fzy calculates an affine gap penalty, this means simply that we assign a constant penalty for having a gap and a linear penalty for the length of the gap. Inspired by the Gotoh algorithm (pdf), fzy computes a second D (for diagonal) matrix in parallel with the score matrix. The D matrix computes the best score which ends in a match. This allows both computation of the penalty for starting a gap and the score for a consecutive match.

Using this algorithm fzy is able to score based on the optimal match.

  • Gaps (negative score)
    • at the start of the match
    • at the end of the match
    • within the match
  • Matches (positive score)
    • consecutive
    • following a slash
    • following a space, underscore, or dash (the start of a word)
    • capital letter (the start of a CamelCase word)
    • following a dot (often a file extension)

Other fuzzy finders

TextMate

TextMate deserves immense credit for popularizing fuzzy finding from inside text editors. It's influence can be found in the command-t project, various other editors use command-t for file finding, and the 't' command in the github web interface.

command-t, ctrlp-cmatcher

Command-t is a plugin first released in 2010 intending to bring TextMate's "Go to File" feature to vim.

Anecdotally, this algorithm works very well. The recursive nature makes it a little hard to

The wy last_idx is suspicious.

Length of shortest first match: fzf

https://github.com/junegunn/fzf/blob/master/src/algo/algo.go

Fzy scores based on the size of the greedy shortest match. fzf finds its match by the first match appearing in the candidate string. It has some cleverness to find if there is a shorter match contained in that search, but it isn't guaranteed to find the shortest match in the string.

Example results for the search "abc"

  • AXXBXXCxxabc
  • xxxxxxxAXBXC
  • xxxxxxxxxABC

Length of first match: ctrlp, pick, selecta (<= 0.0.6)

These score based on the length of the first match in the candidate. This is probably the simplest useful algorithm. This has the advantage that the heavy lifting can be performed by the regex engine, which is faster than implementing anything natively in ruby or Vim script.

Length of shortest match: pick

Pick has a method, min_match, to find the absolute shortest match in a string. This will find better results than the finders, at the expense of speed, as backtracking is required.

selecta (latest master)

https://github.com/garybernhardt/selecta/commit/d874c99dd7f0f94225a95da06fc487b0fa5b9edc garybernhardt/selecta#80

Selecta doesn't compare all possible matches, but only the shortest match from the same start location. This can lead to inconsistent results.

Example results for the search "abc"

  • xAXXXXBC
  • xABXCx
  • xABXCxbc

The third result here should have been scored the same as the first, but the lower scoring but shorter match is what is measured.

others

Possible fzy Algorithm Improvements

Case sensitivity

fzy currently treats all searches as case-insensitive. However, scoring prefers matches on uppercase letters to help find CamelCase candidates. It might be desirable to support a case sensitive flag or "smart case" searching.

Faster matching

Matching is currently performed using the standard lib's strpbrk, which has a very simple implementation (at least in glibc).

Glibc has an extremely clever strchr implementation which searches the haystack string by word, a 4 or 8 byte long int, instead of by byte. It tests if a word is likely to contain either the search char or the null terminator using bit twiddling.

A similar method could probably be written to perform to find a character in a string case-insensitively.