Qual è l'algoritmo di ricerca fuzzy "Vai a File" del textmate?

Question

La ricerca fuzzy di Textmate "go to file" è davvero fantastica.

Il plug-in Command-T di Wincent per vim fa qualcosa di simile e oscilla anche.

Qualcuno può spiegare come funzionano? Esiste un termine generale per il metodo che usano?

Edit: ho qualche dettaglio in più su ciò che questi strumenti fanno

Gli strumenti consentono di restringere un elenco di opzioni (in questo caso percorsi di file) durante la digitazione.

Per esempio, se ho avuto i seguenti file:

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

per arrivare per restringere l'elenco di /app/models/people.rb ho potuto digitare uno dei seguenti:

amp 
peo 
mp 
modelsp 

è molto flessibile e trovo il mio manca questo 'elenco ristretto' quando l'app che sto usando non ce l'ha. Mi piacerebbe saperne di più su di esso in modo che io possa implementare i miei plugin, se mai ne avessi sentito il bisogno. Vorrei poter spiegare meglio, ma è per questo che sono qui :)

Per vederlo in azione dare un'occhiata al di Wincent demo of command-t

Answer 1

Sembra stia facendo una ricerca con caratteri jolly tra ogni lettera.

amp -> *a*m*p* 
peo -> *p*e*o* 
mp -> *m*p* 
modelsp -> ... 

Se corrisponde a un solo elemento nell'elenco di opzioni, verrà restituito come l'opzione desiderata.

Answer 2

Sembra Comando-T fa una sorta sulla base di un double punteggio assegnato tramite la funzione recursive_match in match.c per eseguire la ricerca fuzzy. fonte del Comando-T è protetto da copyright da parte dell'autore, ma la fonte può essere trovata aprendo il vimball in un editor di testo (download al di sotto di this page), e potrebbe probabilmente essere usato come ispirazione per un algoritmo più generale ricerca fuzzy (da qualcuno che legge C meglio di me almeno).

Answer 3

Non ho idea di come funzioni, ma per ricerche veloci puoi generare qualcosa di simile a http://en.wikipedia.org/wiki/Directed_acyclic_word_graph e avere complessità O (L), dove L è la lunghezza del modello di ricerca.

Answer 4

Come sidenote: dare un'occhiata a (Apache Solr) e al modo in cui genera gli indici. Mi trovo ad usarlo parecchio quando sto cercando di implementare qualcosa di simile a Command-T di Textmate sul web.

Controllare in particolare lo EdgeNGramFilterFactory. Credo che potrebbe esserci anche qualche codice sorgente da qualche parte. (E 'in Java anche se ...)

Answer 5

Sembra che questo è il codice esatto si sta parlando:

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