Qu'est-ce que l'algorithme de recherche floue 'Aller au fichier' de textmate?

Question

La recherche floue "go to file" de Textmate est vraiment géniale.

Le plugin Command-T de Wincent pour vim fait quelque chose de similaire et il berce aussi.

Quelqu'un peut-il expliquer comment cela fonctionne? Y a-t-il un terme général pour la méthode qu'ils utilisent?

Edit: Je peu plus de détails sur ce que ces outils ne

Les outils vous permettent de restreindre une liste d'options (dans ce chemins de fichiers de cas) que vous tapez.

Par exemple, si j'avais les fichiers suivants:

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

pour arriver à réduire la liste à /app/models/people.rb je pouvais taper une des opérations suivantes:

amp 
peo 
mp 
modelsp 

il est très flexible et je trouve mon Je manque cette 'liste rétrécie' quand l'application que j'utilise ne l'a pas. J'aimerais en savoir plus à ce sujet afin de pouvoir implémenter mes propres plugins si jamais j'en avais besoin. Souhaite que je pourrais l'expliquer mieux, mais c'est la raison pour laquelle je suis ici :)

Pour le voir en action jeter un oeil chez Wincent demo of command-t

Answer 1

Il semble faire une recherche générique entre chaque lettre. S'il ne correspond qu'à un seul élément de la liste d'options, il le retournera comme l'option voulue.

Answer 2

Il ressemble à commande T fait une sorte fondée sur un score double donné par la fonction dans match.c pour faire la recherche floue. La source de Command-T est protégée par l'auteur mais la source peut être trouvée en ouvrant le vimball dans un éditeur de texte (téléchargement au bas de this page), et pourrait probablement être utilisée comme source d'inspiration pour un algorithme de recherche floue plus générale (par quelqu'un lit C mieux que moi au moins).

Answer 3

N'avez aucune idée de comment cela fonctionne, mais pour les recherches rapides, vous pouvez générer quelque chose de similaire à http://en.wikipedia.org/wiki/Directed_acyclic_word_graph et avoir O (L) complexité, où L est la longueur du motif de recherche.

Answer 4

Comme un sidenote: Jetez un oeil à (Apache Solr) et la façon dont il génère des index. Je me retrouve souvent à l'utiliser lorsque j'essaie d'implémenter quelque chose de similaire au Command-T de Textmate sur le Web.

Spécifiquement consulter le EdgeNGramFilterFactory. Je crois qu'il pourrait même y avoir un code source quelque part. (Il est en Java bien que ...)

Answer 5

On dirait que c'est le code exact que vous parlez:

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