Алгоритм для автоматического заполнения?

Существуют такие инструменты, как soundex и расстояние Левенштейна , которые можно использовать для поиска нечетких совпадений, находящихся в определенном диапазоне.

Soundex находит слова, которые звучат одинаково, а расстояние левенштейна находит слова, которые находятся на определенном расстоянии редактирования от другого слова.

Я думаю, что лучше построить специализированную тройку, чем использовать совершенно другую структуру данных.

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

Метод поискового запроса отображал бы узлы листьев-потомков с наибольшими значениями, рассчитанными путем умножения расстояния до каждого узла листа-потомка на частоту поиска, связанную с каждым узлом листа-потомка.

Структура данных (и, следовательно, алгоритм), используемая Google, вероятно, намного сложнее, потенциально учитывает большое количество других факторов, таких как частота поиска в вашем конкретном аккаунте (и время суток... и погода... сезон... и лунная фаза... и... ). Однако я считаю, что базовая структура данных trie может быть расширена до любого вида специализированных поисковых предпочтений путем включения дополнительных полей в каждый из узлов и использования этих полей в методе поискового запроса.

Посмотрите на алгоритм Awesome bar в Firefox

Google suggest полезен, потому что он учитывает миллионы популярных запросов + ваши прошлые связанные запросы.

Однако у него нет хорошего алгоритма завершения / пользовательского интерфейса:

1. Не работает с подстроками
2. Кажется, что это относительно простой алгоритм префиксации границ слов.
   Например: Попробуйте tomcat tut --> правильно предложит "tomcat tutorial". Теперь попробуйте tomcat rial --> никаких предложений )-:
3. Не поддерживает "did you mean?" - как в результатах поиска google.