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