Каковы хорошие тестовые примеры для алгоритмов поиска подстрок?

Question

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

Answer 1

Некоторые мысли и частичный ответ самому себе:

Наихудший случай для алгоритма перебора:

a^(n+1) b в (a^n b)^m

например. aaab в aabaabaabaabaabaabaab

Худший случай для SMOA:

Что-то вроде yxyxyxxyxyxyxx в (yxyxyxxyxyxyxy)^n. Нуждается в дальнейшей доработке. Я пытаюсь сделать так, чтобы каждое продвижение составляло только половину длины частичного совпадения, и чтобы вычисление максимального суффикса требовало максимального количества возвратов. Я почти уверен, что я на правильном пути, потому что этот тип кейса - единственный способ, который я нашел до сих пор, чтобы моя реализация SMOA (которая асимптотически 6n+5) работала медленнее, чем Two-Way glibc (который асимптотически 2n-m, но имеет умеренно болезненные накладные расходы на предварительную обработку).

Наихудший случай для чего-либо на основе скользящего хэша:

Какая бы последовательность байтов ни вызывала столкновения с хешем иглы. Для любого достаточно быстрого хэша и данной иглы должно быть легко построить стог сена, хэш которого сталкивается с хэшем иглы в каждой точке. Однако, кажется, трудно одновременно создавать длинные частичные совпадения, которые являются единственным способом получить поведение в худшем случае. Естественно, для наихудшего поведения игла должна иметь некоторую периодичность и способ эмулировать хэш, корректируя только последние символы.

Худший чехол для двухсторонней связи:

Кажется, очень короткая игла с нетривиальным разложением MS - что-то вроде bac - где стог сена содержит повторяющиеся ложные срабатывания в правой половине иглы - что-то типа dacdacdacdacdacdacdac. Единственный способ, которым этот алгоритм может быть медленным (за исключением того, что авторы glibc плохо его реализуют ...), это сделать внешний цикл многократно повторяющимся и многократно переносить эти издержки (и делать накладные расходы на установку значительными).

Другие алгоритмы:

Меня действительно интересуют только алгоритмы, которые O(1) находятся в пространстве и имеют незначительные накладные расходы на предварительную обработку, так что я не слишком много смотрел на их худшие случаи. По крайней мере, Бойер-Мур (без модификаций, чтобы сделать его O(n)) имеет нетривиальный наихудший случай, когда он становится O(nm).

Answer 2

Вы можете рекурсивно генерировать строки контейнера (соответственно, содержащиеся тестовые значения) с помощью:

Начиная с пустой строки, сгенерируйте все строки, заданные расширением строки, находящейся в данный момент в наборе, добавив символ из алфавита слева или справа (оба).

Алфавит для генерации контейнерных строк выбран вами.

Вы проверяете 2 алфавита на содержащиеся строки. Один - это тот, который составляет контейнерные строки, другой - его дополнение.

Answer 3

Процедура, которая может дать интересную статистику, хотя у меня нет времени сейчас тестировать:

Рандомизировать по длине строки, затем рандомизировать по содержимому строки этой длины, затем рандомизировать по смещению / длине подстроки(возможно, что-то не в строке), затем случайным образом перебить подстроку (возможно, не совсем), повторить.

Answer 4

Непосредственно не отвечает на ваш вопрос, но вы можете найти алгоритмы в книге - Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология - интересные (имеет много новых алгоритмов поиска по подстроке).Кроме того, это также хороший источник особых и сложных случаев.