Быстрый поиск инфиксов

Question

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

У меня вопрос: как это делают такие мощные компании, как Google / Bing и т. Д.? Они просто переборщили? Я бы вообразил нет, но я не могу найти поддержки этому.

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

Answer 1

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

*talli*

Это подобрало бы все термины, состоящие из одного слова и содержащие "talli", включая "Metallica".

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

acillateM

Answer 2

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

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

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

Answer 3

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

В Solr есть много способов реализовать это (нграммы / черепица, префикс фасета, TermsComponent, ...). Последние версии Solr поставляются с определенным компонентом для автозаполнения на основе проверки орфографии .