Каков наилучший алгоритм автозаполнения/предложения, datastructure [С++/C]

Ответ 1

A trie - это структура данных, которая может использоваться для быстрого поиска слов, соответствующих префиксу.

Изменить: Здесь пример, показывающий, как использовать его для реализации автозаполнения http://rmandvikar.blogspot.com/2008/10/trie-examples.html

Здесь сравнивается 3 различных автозаполнения реализаций (хотя это в Java не С++).

* In-Memory Trie
* In-Memory Relational Database
* Java Set

При поиске ключей, trie немного быстрее, чем реализация Set. Как trie, так и set являются хорошим бит быстрее, чем решение реляционной базы данных.

Стоимость установки набора ниже, чем решение Trie или DB. Вам нужно будет решить, будете ли вы строить новые "словарные данные" часто или скорость поиска является более высоким приоритетом.

Эти результаты представлены на Java, ваш пробег может отличаться от решения на С++.

Ответ 2

Для больших наборов данных хорошим кандидатом на бэкэнд будет тройной поиск деревьев. Они сочетают в себе лучшее из двух миров: низкое пространство накладных двоичных деревьев поиска и характерная эффективность времени поиска цифрового поиска.

Смотрите в журнале доктора Доббса: http://www.ddj.com/windows/184410528

Цель - быстрый поиск конечного набора результатов по мере ввода пользователем. Давайте сначала рассмотрим, что для поиска "информатики" вы можете начать вводить текст с "компьютера" или "науки", но не "omputer". Итак, с учетом фразы, сгенерируйте подфразы, начинающиеся со слова. Теперь для каждой из фраз подайте их в TST (тройное дерево поиска). Каждый node в TST будет представлять собой префикс фразы, которая была введена до сих пор. Мы сохраним лучшие 10 (скажем) результатов для этого префикса в том, что node. Если количество кандидатов больше, чем конечное количество результатов (здесь 10) для node, должна быть функция ранжирования для разрешения конкуренции между двумя результатами.

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

Более сложные осложнения возникнут, если будет предложено исправление орфографии. В этом случае также нужно будет рассмотреть алгоритмы редактирования расстояния.

Для небольших наборов данных, таких как список стран, будет выполнена простая реализация Trie. Если вы собираетесь реализовать такой раскрывающийся список автозаполнения в веб-приложении, виджет автозаполнения YUI3 сделает все для вас после предоставления данных в списке. Если вы используете YUI3 как только интерфейс для автозаполнения, поддерживаемый большими данными, создайте веб-службу на основе TST на С++, а затем используйте script node источник данных виджета автозаполнения для извлечения данных из веб-службы вместо простого списка.

Ответ 3

Деревья сегментов могут использоваться для эффективной реализации auto complete

Ответ 4

Если вы хотите предложить самые популярные доработки, "Рекомендовать дерево" может быть хорошим выбором: Предложить дерево

Ответ 5

Для простого решения: вы создаете "кандидат" с минимальным редактированием (Levenshtein) расстояние (1 или 2), затем вы проверяете существование кандидата с контейнером хэша ( set будет достаточным для простого разрешения, затем используйте unordered_set из tr1 или boost).

Пример: Вы писали carr и хотите машину. arr генерируется 1 удалением. Обнаруживает ваш неупорядоченный_set? № crr генерируется 1 удалением. Является ли crr в вашем неупорядоченном_set? Автомобиль номер генерируется 1 удалением. Является ли автомобиль вашей неупорядоченной? Да, вы побеждаете.

Конечно, там вставка, удаление, транспонирование и т.д.

Вы видите, что ваш алгоритм для создания кандидатов действительно там, где вы тратите время, особенно если у вас очень мало unordered_set.