Say I have file paths like this:


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


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:


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. – Goyo 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

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.

  • 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.