Какой textmate 'Go to File' нечеткий алгоритм поиска?
Textmate 'go to file' нечеткий поиск действительно потрясающий.
Плагин Wincent Command-T для vim делает что-то подобное, и он тоже качается.
Может кто-нибудь объяснить, как это работает? Существует ли общий термин для метода, который они используют?
Изменить: Я немного больше расскажу о том, что эти инструменты делают
Инструменты позволяют сузить список параметров (в этом случае путь к файлу) при вводе.
Например, если у меня были следующие файлы:
/app/models/people.rb
/app/models/address.rb
/app/person.rb
/person.rb
чтобы сузить список до /app/models/people.rb
, я мог бы ввести любое из следующих значений:
amp
peo
mp
modelsp
он очень гибкий, и я нахожу, что у меня отсутствует этот "сужение списка", когда приложение, которое я использую, не имеет его. Я хотел бы узнать больше об этом, чтобы я мог реализовать свои собственные плагины, если я когда-либо почувствовал необходимость. Хотел бы я объяснить это лучше, но вот почему я здесь:)
Чтобы увидеть это в действии, посмотрите на wincent демонстрацию команды-t
Ответы
Ответ 1
Кажется, он выполняет поиск по шаблону между каждой буквой.
amp -> *a*m*p*
peo -> *p*e*o*
mp -> *m*p*
modelsp -> ...
Если он соответствует только одному элементу в списке параметров, тогда он будет возвращать его в качестве предполагаемой опции.
Ответ 2
Похоже, что Command-T выполняет сортировку, основанную на значении double
, заданном функцией recursive_match
в match.c
, для выполнения нечеткого поиска. Источник Command-T защищен авторским правом, но источник можно найти, открыв vimball в текстовом редакторе (загрузите внизу эту страницу), и, вероятно, можно было бы использовать в качестве вдохновения для более общего алгоритма нечеткого поиска (кем-то, кто лучше читает C лучше меня).
Ответ 3
Похоже, это точный код, о котором вы говорите:
https://github.com/textmate/textmate/blob/master/Frameworks/text/src/ranker.cc
Ответ 4
Не знаю, как это работает, но для быстрого поиска вы можете сгенерировать что-то похожее на http://en.wikipedia.org/wiki/Directed_acyclic_word_graph и иметь сложность O (L) где L - длина шаблона поиска.
Ответ 5
В качестве побочного элемента: посмотрите (Apache Solr) и способ генерации индексов. Я нахожу, что использую его совсем немного, когда пытаюсь реализовать что-то похожее на Textmate Command-T в Интернете.
В частности, проверьте EdgeNGramFilterFactory. Я верю, что где-то может быть какой-то исходный код. (Это на Java, хотя...)