0

Say I have file paths like this:

my/long/directory/structure/index.js
my/long/directory/structure2/index.js
my/long/directory/structure3/index.js
my/long/directory/structure.../index.js
my/long/directory/structuren/index.js
my/long/directory/index.js
my/long/directory2/index.js
my/long/directory.../index.js
my/long/directoryn/index.js
my/long/index.js
my/index.js
...

I search for d <n> i (e.g. d 2 i or d 3 i), and it gives this:

my/long/irectory/structure/ndex.js
my/long/irectory/ndex.js

The questions are 2:

  1. How it actually matches the strings.
  2. How it returns the results as syntax highlighted.

For (1), there is the data structure and the algorithm. In terms of data structure, I have seen a lot of autocomplete-like functionality recommended to be implemented as a trie. That makes sense for keywords, but I don't see how that would work for a file path. As a start, it seems you could break it into individual directories/filenames:

my
long
directory
structuren
index.js

And have a trie for each level. That would allow at least for exact prefix match of the file path. I don't see how it would work for fuzzy match, as in a d <n> i search. That search stretches over several layers of this multi-trie system. The only way I could seeing it return fuzzy results is by checking every file path from start to end, thus no better than simply doing a regexp match against each file path in its entirety. So I'm wondering what sort of data structure is actually used for fuzzy matching in this case.

For (2), most fuzzy matching implementations I've seen are based on the levenshtein distance, and simply return a yes/no match, not a parse tree. Wondering if there are implementations that return the parse tree, or there are alternative ways to accomplish this. That way you can easily syntax highlight without having to resort to a hack that duplicates some of the work of finding the matching parts of the file text from the frontend.

  • 1
    What tool does this? – Kilian Foth Aug 27 '18 at 6:32
  • 1
    Fuzzy search is a fuzzy concept, there are several ways to do it. – Stop harming Monica Aug 27 '18 at 7:58
  • @KilianFoth sublime text does this, I wanted to replicate it. – Lance Pollard Aug 27 '18 at 15:30
  • Also, stackexchange tags do this too sort of, but I'm not sure if they match with non-matching letters in between like sublime does. – Lance Pollard Aug 27 '18 at 15:32
  • Before we can give a useful answer, could you be more specific on the matching rules? You will likely need to specify a predicate matching_path_element(a,b) that tells you whether two path elements are similar. Or do you consider that two paths with a different depth could be matched? Also, could you explain why you wish a parse tree with a Levenshtein algorithm? – fralau Nov 26 '18 at 7:31
1

I don't know how exactly Sublime text does fuzzy search as Sublime is not open source.

However, we do have fzf, which is a very good open source implementation of fuzzy finder. You're probably going to be interested in the fzf search algorithm's description:

Algorithm

[...]

FuzzyMatchV2 implements a modified version of Smith-Waterman algorithm to find the optimal solution (highest score) according to the scoring criteria. [Smith-Waterman algorithm Wikipedia page]

[...]

Scoring criteria

  • We prefer matches at special positions, such as the start of a word, or uppercase character in camelCase words.

  • That is, we prefer an occurrence of the pattern with more characters matching at special positions, even if the total match length is longer.

    e.g. "fuzzyfinder" vs. "fuzzy-finder" on "ff"
                            ````````````
    
  • Also, if the first character in the pattern appears at one of the special positions, the bonus point for the position is multiplied by a constant as it is extremely likely that the first character in the typed pattern has more significance than the rest.

    e.g. "fo-bar" vs. "foob-r" on "br"
          ``````
    
  • But since fzf is still a fuzzy finder, not an acronym finder, we should also consider the total length of the matched substring. This is why we have the gap penalty. The gap penalty increases as the length of the gap (distance between the matching characters) increases, so the effect of the bonus is eventually cancelled at some point.

    e.g. "fuzzyfinder" vs. "fuzzy-blurry-finder" on "ff"
          ```````````
    
  • Consequently, it is crucial to find the right balance between the bonus and the gap penalty. The parameters were chosen that the bonus is cancelled when the gap size increases beyond 8 characters.

  • The bonus mechanism can have the undesirable side effect where consecutive matches are ranked lower than the ones with gaps.

    e.g. "foobar" vs. "foo-bar" on "foob"
                       ```````
    
  • To correct this anomaly, we also give extra bonus point to each character in a consecutive matching chunk.

    e.g. "foobar" vs. "foo-bar" on "foob"
          ``````
    
  • The amount of consecutive bonus is primarily determined by the bonus of the first character in the chunk.

    e.g. "foobar" vs. "out-of-bound" on "oob"
                       ````````````
    

Couple things of note: fzf uses a matrix-based algorithm to calculate a fuzzy match score, and a score algorithm that is optimised for common cases of what people usually do when searching files.

| improve this answer | |
0

The only way I could seeing it return fuzzy results is by checking every file path from start to end, thus no better than simply doing a regexp match against each file path in its entirety

What do you mean "no better"? Without knowing what tool you are talking about, from your description I am pretty sure this is indeed done using regular expressions. If you have the Match object you have a lot of information already that will allow you to determine what to highlight. You may have to do an additional plain string search to find the exact location of the fuzzy characters but that would be all.

| improve this answer | |
  • I was imagining creating n-grams somehow. For example. hello. You could create 2-grams to show what letters follow what letters. So it would be: he, hl, ho, el, eo, ll, lo. Then you would be able to check if any string was split apart across a file path, without having to use regexes. Was hoping for an answer or techique like that, b/c then you could take advantage of tries somehow. – Lance Pollard Aug 27 '18 at 15:26
  • Here we go: github.com/mattyork/fuzzy – Lance Pollard Aug 27 '18 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.