Fuzzy matching with levenshtein: take 2

[tgross35]

#34 brought this up before, but was closed because search patterns are typically short, so there isn't much of a need. However, as some others have pointed out on the thread, it is definitely helpful when there are a small number of mistakes in a longer search

A way to do this is with a levenshtein algorithm that exits if a limit is exceeded. I maintain a small crate that provides this with try_levenshtein(a, b, limit) -> Option<u32>, which returns None if a specified limit is exceeded (crate link: https://docs.rs/stringmetrics/latest/stringmetrics/, but you could also just copy the implementation if you don't want the dependency).

Something basic like this would find the closest match within a percent difference of the query's length.

possible_matches.iter()
    .filter_map(|m| try_levenshtein(query, m, floor(0.3 * query.len())))
    .max()

I'm not sure how best this would fit into the current algorithm (or what exactly fzf currently does), but I'm happy to help & clarify anything needed

[tgross35]

Closing this in favor of my new nucleo issue