Алгоритмы поиска подстроки (очень большой стог сена, маленькая игла)

Стоит взглянуть на массивы суффиксов и деревья . Оба они требуют предварительных вычислений и значительного объема памяти, но они лучше, чем обратные индексы в том смысле, что вы можете искать произвольные подстроки в O (m) (для суффиксных деревьев) и O (m + log n) (для массивов суффиксов с наименьшей общей префиксной информацией).

Если у вас есть много времени, вы можете изучить сжатые массивы суффиксов и сжатые CSA, которые представляют собой сжатые версии ваших данных, которые также являются самоиндексирующимися ( т.е. данные также являются индексом, внешнего индекса нет).Это действительно лучший из миров, потому что у вас есть не только сжатая версия ваших данных (вы можете выбросить исходные данные), но она также проиндексирована! Проблема состоит в том, чтобы понять исследовательские работы и перевести их в код :)

Если вам не нужно идеальное сопоставление подстрок, а скорее общие возможности поиска, ознакомьтесь с Lucene .

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

Учитывая Кнута – Морриса – Пратта или Бойера – Мура, вы не добьетесь большего успеха, поэтому вам следует подумать о распараллеливании процесса поиска.

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

Но вот другая идея, которая прибегает к фильтрам Блума. Вы, вероятно, знаете, что это такое, но на всякий случай (и для других людей, читающих этот ответ): Фильтры Блума - это очень маленькие, очень компактные битовые векторы, которые аппроксимируют включение множества. Если у вас есть множество S и фильтр Блума для этого множества B(S), то

x ∈ S ⇒ x ∈ B(S)

но обратное утверждение будет ложным. Вот что является вероятностным в этой структуре: существует (количественно измеримая) вероятность того, что фильтр Блума вернет ложное срабатывание. Но аппроксимация включения с помощью фильтра Блума дико быстрее, чем его точное тестирование на множестве.

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

Фильтры Блума с некоторым успехом использовались в строковом поиске. Вот набросок (возможно, я неправильно помню некоторые детали) этого применения. Текстовый файл представляет собой последовательность из N строк. Вы ищете слово, состоящее из M букв (причем ни одно слово не может быть разнесено на две строки). На этапе предварительной обработки будет создан ОДИН фильтр Блума для каждой строки, путем добавления каждой подпоследовательности строки в фильтр Блума; например, для этой строки

 Touching this dreaded sight, twice seene of vs,

И соответствующий фильтр Блума будет создан с "T", "To", "Tou" .... "o", "ou", ... "vs,", "s", "s,", ",". (Я могу ошибаться в этой части. Или вы можете захотеть оптимизировать.)

Затем при поиске подслова размером M просто сделайте одну очень быструю проверку каждого из фильтров Блума, и когда есть совпадение, внимательно изучите строку, например, с помощью алгоритма KMP. На практике, если вы хорошо настроите свои фильтры Блума, компромисс будет замечательным. Поиск становится невероятно быстрым, потому что вы удаляете все бесполезные строки".

Я полагаю, что на основе этой концепции вы могли бы вывести полезную схему для вашей ситуации. На данный момент я вижу два очевидных варианта адаптации:

• либо разрезать набор данных на множество блоков размером K (каждый со своим фильтром Блума, как строки в предыдущем примере);

• либо использовать своего рода дихотомию, когда вы разбиваете набор на два подмножества, каждое из которых имеет фильтр Блума, затем каждое подмножество разбивается на два подмножества со своим фильтром Блума и т. д. (если вы собираетесь добавить все подстроки, как это предлагается в описанном мной методе, эта вторая идея будет немного запретительной - за исключением того, что вам не нужно добавлять все подстроки, а только подстроки размером от 1 до 10).

Обе идеи могут быть объединены изобретательными способами для создания многоуровневых схем.