¿Qué es el algoritmo de búsqueda difusa 'Ir a archivo' de textmate?

Question

La búsqueda difusa de 'ir a archivo' de Textmate es realmente increíble.

El complemento Command-T de Wincent para vim hace algo similar y también se complica.

¿Alguien puede explicar cómo funcionan? ¿Hay un término general para el método que usan?

Editar: que poco más de detalle acerca de lo que estas herramientas hacen

Las herramientas le permiten obtener, de una lista de opciones (en este caso de archivos de caminos) a medida que escribe.

Por ejemplo, si tuviera los siguientes archivos:

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

para llegar a reducir la lista a /app/models/people.rb pude escribir cualquiera de los siguientes:

amp 
peo 
mp 
modelsp 

que es muy flexible y me encuentro con mi Me falta esta "reducción de listas" cuando la aplicación que estoy usando no la tiene. Me gustaría obtener más información al respecto para poder implementar mis propios complementos si alguna vez lo necesitaba. Me gustaría poder explicarlo mejor, pero es por eso que estoy aquí :)

Para verlo en acción echar un vistazo a la Wincent demo of command-t

Answer 1

Parece que está haciendo una búsqueda de comodín entre cada letra.

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

Si coincide con sólo un elemento de la lista de opciones, entonces sería volver que a medida que la opción deseada.

Answer 2

Parece Comando-T hace una especie basado en una puntuación double dada por la función recursive_match en match.c para hacer la búsqueda difusa. La fuente de Command-T es propiedad del autor, pero la fuente se puede encontrar abriendo vimball en un editor de texto (descargar en la parte inferior de this page), y probablemente podría usarse como inspiración para un algoritmo de búsqueda difusa más general (por alguien que lee C mejor que yo al menos).

Answer 3

No tengo idea de cómo funciona esto, pero para búsquedas rápidas puedes generar algo similar a http://en.wikipedia.org/wiki/Directed_acyclic_word_graph y tener complejidad O (L), donde L es la longitud del patrón de búsqueda.

Answer 4

Como nota al margen: Eche un vistazo a (Apache Solr) y la forma en que genera los índices. Me encuentro usándolo bastante cuando intento implementar algo similar al Command-T de Textmate en la web.

Específicamente echa un vistazo al EdgeNGramFilterFactory. Creo que incluso podría haber algún código fuente en alguna parte. (Está en Java ...)

Answer 5

Parece que este es el código exacto que está hablando:

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