Каковы хорошие структуры данных для алгоритмов автоматического завершения? Какие структуры данных позволяют эффективно находить строки, содержащие определенную подстроку?
Структура данных для автоматического завершения
Ответ 1
Если вы хотите сделать что-то похожее на то, как Google реализует его автозаполнение, вы можете проверить трехмерное дерево поиска:
http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
Однако, если вы хотите найти произвольную подстроку в строке, попробуйте обобщенное дерево суффиксов.
Ответ 2
Откажитесь от и дерева суффиксов.
Ответ 3
Если вы делаете префиксы (это то, что делают большинство автозаполнений), то тройное дерево поиска также я рекомендую. Если вы делаете общие инфиксы, переходите к дереву суффиксов, как упоминалось выше.
Ответ 4
В качестве альтернативы массивам, деревьям и попыткам суффикса взгляните на Направленные ациклические графы Word (DAWG) и сжатый вариант ( CDAWGs). Они могут быть построены в линейном времени, занимать линейное пространство и разрешать поиск подстроки.
С более сложной функцией поиска вы можете даже поддерживать ограниченный набор подстановочных знаков.
Ответ 5
Если набор предложений автозаполнения упорядочен по рангу, SuggestTree является хорошей структурой данных. Для любого префикса он обеспечивает быстрый доступ к верхним предложениям, начинающимся с этого префикса.
Ответ 6
Я создал приложение только для того, что вы хотите. Это самый эффективный алгоритм автозаполнения, основанный на префиксе.