Was ist der unscharfe Fuzzy-Suchalgorithmus von 'text to mat'?

Question

Textmates 'Fuzzy-Suche "ist wirklich großartig.

Wincents Command-T Plugin für vim macht etwas ähnliches und es rockt auch.

Kann jemand erklären, wie diese funktionieren? Gibt es einen allgemeinen Begriff für die Methode, die sie verwenden?

Edit: ich wenig mehr Details über das, was diese Werkzeuge tun

Die Werkzeuge können Sie eine Liste von Optionen verengen (in diesem Fall Dateipfade) angezeigt werden.

Zum Beispiel, wenn ich die folgenden Dateien hatte:

/app/models/people.rb 
/app/models/address.rb 
/app/person.rb 
/person.rb 

zu erhalten, die Liste zu /app/models/people.rb verengen ich die alle folgenden geben könnte:

amp 
peo 
mp 
modelsp 

es ist sehr flexibel und ich finde meine Ich vermisse selbst diese "Listeneinschränkung", wenn die App, die ich verwende, sie nicht hat. Ich würde gerne mehr darüber erfahren, damit ich meine eigenen Plugins implementieren kann, wenn ich das Bedürfnis verspüre. Wünsche ich es besser erklären könnte, aber das ist, warum ich hier bin :)

Um es in Aktion zu sehen, Wincent der demo of command-t

Answer 1

Es scheint, eine Wildcard-Suche zwischen jedem Buchstaben zu tun.

Wenn es nur ein Element in der Liste der Optionen entspricht, würde es das als die beabsichtigte Option zurückgeben.

Answer 2

Es sieht zu sehen wie Befehl-T eine Art auf einem double Punkte tut gegeben durch die recursive_match Funktion in match.c, um die unscharfe Suche zu tun. Die Quelle von Command-T ist vom Autor urheberrechtlich geschützt, aber die Quelle kann durch Öffnen des Vimballs in einem Texteditor (Download am Ende von this page) gefunden werden und könnte wahrscheinlich als Inspiration für einen allgemeineren unscharfen Suchalgorithmus (von jemandem, der liest C besser als ich zumindest).

Answer 3

Keine Ahnung, wie das funktioniert, aber für schnelle Suchvorgänge können Sie etwas ähnlich http://en.wikipedia.org/wiki/Directed_acyclic_word_graph erzeugen und haben O (L) -Komplexität, wobei L die Länge des Suchmusters ist.

Answer 4

Als eine Nebenbemerkung: Werfen Sie einen Blick auf (Apache Solr) und die Art, wie es Indizes generiert. Ich benutze es ziemlich oft, wenn ich versuche, etwas ähnliches wie Textmates Command-T im Web zu implementieren.

Überprüfen Sie speziell die EdgeNGramFilterFactory. Ich glaube, irgendwo könnte es irgendwo einen Quellcode geben. (Es ist in Java obwohl ...)

Answer 5

Sieht aus wie dies die genaue Code Sie sprechen:

https://github.com/textmate/textmate/blob/master/Frameworks/text/src/ranker.cc