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

Question

Я знаю, что здесь уже есть несколько похожих вопросов, но мне нужны некоторые рекомендации для моего случая (не могу найти ничего похожего).

Мне нужно найти очень большой объем данных для подстроки, которая была бы примерно в миллиард раз меньше (10 байтов на 10 миллиардов байтов). Стог сена не меняется, поэтому я могу выдержать большие предварительные вычисления, если это необходимо. Мне просто нужно, чтобы поисковая часть была максимально быстрой.

Я нашел алгоритмы, которые занимают O (n) время ( n = размер стога сена, m = размер иглы), а наивный поиск занимает O (N + M) . Поскольку m в данном конкретном случае будет очень маленьким, есть ли другой алгоритм, на который я мог бы обратить внимание?

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

Answer 1

Вы ищете структуру данных, называемую Trie или "префиксное дерево". Короче говоря, эта структура данных кодирует все возможные строковые префиксы, которые можно найти в вашем корпусе.

Вот статья , которая ищет последовательности ДНК для небольшой подстроки, используя префиксное дерево. Я полагаю, что это может помочь вам, так как ваш случай звучит похоже.

Если вы знаете определенный предел длины входной строки поиска, вы можете ограничить рост вашего Trie, чтобы он не сохранял никаких префиксов длиннее этой длины max. Таким образом, вы можете установить Trie, представляющий все 10G, в менее чем 10G памяти. Особенно для очень повторяющихся данных, любой вид Trie является сжатым представлением данных. (Или должно быть , если реализовано разумно.) Ограничение глубины Trie до максимальной строки поиска ввода позволяет еще больше ограничить потребление памяти.

Answer 2

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

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

x ∈ S ⇒ x ∈ B(S)

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

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

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

 Touching this dreaded sight, twice seene of vs,

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

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

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

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

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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