Что такое алгоритм нечеткого поиска textmate 'Go to File'?

Question

Нечеткий поиск TextMate 'go to file' действительно потрясающий.

Плагин Command-T от Wincent для vim делает что-то похожее, и это тоже потрясающе.

Может кто-нибудь объяснить, как они работают?Есть ли общий термин для метода, который они используют?

Редактировать: Я немного подробнее о том, что делают эти инструменты

Инструменты позволяют сузить список параметров (в этом случае пути к файлам) при вводе.

Например, если бы у меня были следующие файлы:

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

, чтобы сузить список до /app/models/people.rb, я мог набрать любой изследующее:

amp
peo
mp
modelsp

это очень гибко, и я обнаруживаю, что мне не хватает этого «сужения списка», когда приложение, которое я использую, не имеет его.Я хотел бы узнать больше об этом, чтобы я мог реализовать свои собственные плагины, если я когда-либо чувствовал необходимость.Хотел бы я объяснить это лучше, но вот почему я здесь:)

Чтобы увидеть это в действии, взгляните на демонстрационную версию wincent command-t

Answer 1

Похоже, что он выполняет поиск по подстановочным знакам между каждой буквой.

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

Если он соответствует только одному элементу в списке параметров, он вернет его в качестве намеченного параметра.

Answer 2

Похоже, это именно тот код, о котором вы говорите:

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

Answer 3

Похоже, что Command-T выполняет сортировку на основе оценки double, заданной функцией recursive_match в match.c для нечеткого поиска.Источник Command-T защищен авторским правом, но источник можно найти, открыв vimball в текстовом редакторе (скачать в нижней части эта страница ), и, вероятно, может использоваться в качестве вдохновения для более общегоалгоритм нечеткого поиска (кем-то, кто читает C лучше меня).

Answer 4

Как примечание: посмотрите ( Apache Solr ) и то, как он генерирует индексы. Я довольно часто использую его, когда пытаюсь реализовать что-то похожее на Textmate Command-T в Интернете.

В частности, проверьте EdgeNGramFilterFactory . Я верю, что где-то может даже быть какой-то исходный код. (Хотя это на Java ...)

Answer 5

Понятия не имею, как это работает, но для быстрого поиска вы можете сгенерировать что-то похожее на http://en.wikipedia.org/wiki/Directed_acyclic_word_graph и иметь сложность O (L), где L - длина шаблона поиска.