Feature Request: Fuzzy matching for teleports and subdirectories

[CatEars]

Assuming I have ~/Documents and the teleport home:~ then goto hom/Diocuemants should take me there. Perhaps hide it behind some configuration?

For example

$ goto --config set AllowFuzzyMatch True
$ goto --config set AllowFuzzySubdirectoryTraversal True
$ goto --config set FuzzinessLevel 5 # Allow hamming distance/text difference of 5 characters

[CatEars]

I think this one can go in several directions. The inspiration originally comes from Sublime Texts excellent "Goto Anywhere" where you just haphazardly type something that is close to correct and gets you there. That is the inspiration at least, but ideas are welcome.

I believe it would be smart to start with something simple, where the actual fuzzy matching is pluggable (for example just matching prefixes of subdirectories so "aaa/bbb/ccc" would shorten to "a/b/c").

[CatEars]

Perhaps start even more simple where the "normal" fuzzy matching is just straight up:

def fuzzy_matching_normal(teleport: str):
    return teleport

and make sure that fuzzy_matching_normal is used in a pluggable way with regards to --config set FuzzyMatchingAlgorithm XYZ.

[CatEars]

Here I am just listing a few ideas I have for different fuzzy matchers:

• PrefixMatching
  Match the longest prefix to a teleport, remove that prefix from the input string, do a prefix match from the teleport directory where all the subdirectories are compared to the remaining teleport string
• HammingDistance
  Use Hamming Distance as a measure of how similar the input string and the actual teleport is.
• A combination of the two above
  The PrefixMatch algorithm is a recursive algorithm, because once you reach a similar state you use the same algorithm to solve that problem (from these input strings, which can be teleport names or subdirectories, match as much in the user input as possible). At any point you choose the PrefixMatch algorithm you can also choose the HammingDistance algorithm and so you can combine them.

[CatEars]

So the different PRs for this should be something like this:

1. Implement fuzzy matching configuration. The default fuzzy matching should be turned off but there should be an available debug fuzzy matching that simply returns the same string as input.
2. Implement an algorithm described above and add configuration options for it. I believe the easiest one to implement is the prefix matching one

[CatEars]

Essentially we are trying to solve the Approximate String Matching problem.

[CatEars]

The Jaro-Winkler algorithm looks quite suitable. It seems that a lot of these Edit Distance algorithms have a threshold of some sort and the Jaro-Winkler will normalize the value of the match between 0 and 1, so this makes the configuration more intuitive. For example goto --config set JaroWinklerSimlarityThreshold 0.5 means that the Jaro-winkler algorithm would match to at least 50%, else throw an exception.