Быстрый поиск Infix

Question

Я создаю автозаполнение, которое должно будет быстро запросить более 10 миллионов слов/фраз и столкнуться с некоторыми проблемами. Моя первая идея состояла в том, чтобы пройти через какую-то структуру trie/trernary tree, но это строго префиксное совпадение, что недостаточно для моего приложения (я хочу полное инфиксное сопоставление). Затем я перешел к некоторым более крупным решениям, SqlServer FullText Indexing, Lucene, Solr, Sphinx, но Lucent и SqlServer FullText Indexing на самом деле не являются полнотекстовыми, а префикс отличными функциями (soundex, близость и т. Д.). Я пытался подумать о том, как может помочь редактирование расстояния Левенштейна, но не может найти способ быть как по крайней мере разумным, так и поддерживать слова с большими расстояниями редактирования (т. Е. Google и ogl. Расстояние редактирования 3, но 3 путь к высокому порогу - общий случай).

Вопрос в том, как работают такие электростанции, как Google/bing и т. Д.? Они просто грубо заставляют это после бит? Я не думаю, что нет, но я не могу найти поддержки.

Любая помощь будет оценена!

Answer 1

Если включить queryParser.setAllowLeadingWildcard(true); в Lucene, вы можете использовать ведущие и ведомые символы, как:

*talli* 

Что бы забрать все члены одного слова, которые содержат «Talli», включая «Metallica».

Это может быть не достаточно быстро для вас, но в некоторых случаях (если вы предпочитаете только подстановочные подстановочные знаки), если вы можете предварительно обработать строку запроса, с которой вы могли бы справиться со старым «обратить вспять термин и индекс что также «трюк:

acillateM 

Answer 2

Lucene/Solr может сделать это очень легко. Единицей поиска в Lucene/Solr является Term, который обычно является словом, но может быть практически любым в зависимости от того, как настроено text analysis.

С помощью Solr существует множество способов реализовать это (ngrams/shingles, facet prefix, TermsComponent, ...). Последние версии Solr поставляются со специальным компонентом для autocomplete based on spell checking.

Answer 3

Когда мне понадобился поиск infix в 2013 году, я провел некоторое исследование. Единственный способ, который я нашел, - Sphinx engine. Нужно сконфигурировать его для поддержки поиска infix.

index tra 
{ 
    [...] 
    enable_star=1 
    min_infix_len=2 
} 

После этого он рассматривает проблему в глазном свете. Я думаю, что это было около 200 тыс. Записей для поиска. Я использовал локальный движок для имитации библиотеки поиска в памяти.