быстрый индекс для "содержит строку"

Question

В моем приложении до миллионов коротких строк (в основном короче 32 символов). Я хочу реализовать окно поиска с прикрепленным списком, который содержит только элементы, содержащие всю строку, введенную в поле поиска. Как я могу предварительно построить индекс, чтобы быстро найти такие строки? Все отсортированные контейнеры STL проверяют всю строку.

Для введенной строки поиска "str" ​​мне нужно найти все строки, содержащие "str": "главная улица", "struve", "ustr" и т. Д.

Answer 1

Вы можете построить Индексы перестановки .

. Для "struve" вы должны вставить в Дерево радиксов (или в дерево поиска общего назначения):

struve$
truve$s
ruve$st
uve$str
ve$stru
e$struv
$struve

Для поиска инфикса необходимо выполнить поиск в корневом узле для соответствующих строк префикса.

Answer 2

Вы можете начать с просмотра trie's .Хотя они в основном используются в качестве префиксных деревьев, сама структура данных может быть адаптирована для более быстрого общего поиска.

Answer 3

Если строки имеют произвольную длину и произвольное количество, вы можете попробовать алгоритм Aho-Corasick , который прост в реализации и масштабируется на O(n) длины поискового текста, и выполняет поиск по всем строкам одновременно.

В качестве альтернативы, если количество искомых строк невелико, попробуйте алгоритмы Horspool , которые исключительно просты в реализации и в среднем меньше O(n) на строку.

Answer 4

Вы говорите, что у вас есть миллионы коротких строк, поэтому я предполагаю, что вы не можете хранить ее в ОЗУ и хранить в базе данных. Предположим, вы храните свои «короткие строки» в таблице с именем my_string (id, string). Создайте еще одну таблицу, назовем ее my_substring (id, substring [unique]), содержащую каждую подстроку каждой строки в my_string. Также создайте объединяющую таблицу для двух таблиц выше: my_substring_to_string (id, substring_id, string_id), ее содержимое очевидно, я полагаю.

Теперь поиск выполняется просто и быстро: найдите подстроку в my_substring (не забудьте создать индекс для my_substring.substring) и присоедините ее к my_string через my_substring_to_string.

Добавление и удаление новой короткой строки потребует обновления в my_substring и my_substring_to_string, но это довольно просто.

Если это решение создаст таблицу my_substring с недопустимо большим размером, его можно оптимизировать. Вместо сохранения каждой подстроки попробуйте сохранить каждый суффикс и найдите «substring%» с помощью ilike. Например, если слово «блюз», вы должны хранить суффиксы: 'blues', 'lues', 'ues', 'es', 's' (соединены с 'blues'). Тогда поиск по 'lu' (ilike 'lu%') будет соответствовать 'lues'. Таким образом, база данных все еще будет в состоянии использовать индекс, созданный для столбца my_substring.substring, поэтому поиск по-прежнему будет быстрым.

Answer 5

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

Обратите внимание, что я не имею в виду "список", чтобы означать "связанный список", а просто "некоторую последовательную структуру данных", которая обычно означает вектор ...

Answer 6

Я бы использовал SQLite. Может быть, использовать базу данных в памяти, если в любом случае вы загрузите все в ОЗУ и нуждаетесь в производительности.