Каковы хорошие тестовые примеры для алгоритмов поиска подстрок?
Я пытаюсь оценить различные алгоритмы и реализации поиска по подстроке (ala strstr) и ищу некоторые тщательно продуманные строки игл и стога сена, которые улавливают производительность в худшем случае и возможные ошибки в угловых случаях. Я полагаю, что смогу решить их сам, но я полагаю, что у кого-то должна быть хорошая коллекция тестов, где-то сидящих...
4 ответа
Несколько мыслей и частичный ответ на себя:
Худший случай для алгоритма грубой силы:
a^(n+1) b в (a^n b)^m
например aaab в aabaabaabaabaabaabaab
Худший случай для SMOA:
Что-то вроде yxyxyxxyxyxyxx в (yxyxyxxyxyxyxy)^n, Нуждается в дальнейшей доработке. Я пытаюсь обеспечить, чтобы каждое продвижение составляло только половину длины частичного соответствия, и чтобы вычисление максимального суффикса требовало максимального количества возвратов. Я почти уверен, что я на правильном пути, потому что этот тип случая - единственный способ, который я нашел до сих пор, чтобы сделать мою реализацию SMOA (которая асимптотически 6n+5) работает медленнее, чем Two-Way (который асимптотически работает в glibc) 2n-m но имеет умеренно болезненные накладные расходы на предварительную обработку).
Наихудший случай для чего-либо на основе скользящего хэша:
Какая бы последовательность байтов ни вызывала столкновения с хэшем иглы. Для любого достаточно быстрого хэша и данной иглы должно быть легко построить стог сена, хеш которого сталкивается с хэшем иглы в каждой точке. Однако, кажется, трудно одновременно создавать длинные частичные совпадения, которые являются единственным способом получить поведение в худшем случае. Естественно, для наихудшего поведения игла должна иметь некоторую периодичность и способ эмулировать хэш, корректируя только последние символы.
Худший случай для двухстороннего:
Кажется, очень короткая игла с нетривиальным разложением РС - что-то вроде bac - где стог сена содержит повторные ложные срабатывания в правой половине иглы - что-то вроде dacdacdacdacdacdacdac, Единственный способ, которым этот алгоритм может быть медленным (кроме того, что авторы glibc плохо его реализуют...), это сделать внешний цикл многократно повторяющимся и многократно увеличивать эти издержки (и делать накладные расходы на установку значительными).
Другие алгоритмы:
Меня действительно интересуют только алгоритмы, которые O(1) в космосе и имеют малые накладные расходы на предварительную обработку, поэтому я не слишком много смотрел на их худшие случаи. По крайней мере, Бойер-Мур (без изменений, чтобы сделать это O(n)) имеет нетривиальный наихудший случай, когда он становится O(nm),
Вы можете сгенерировать строки контейнера (соответственно, содержащиеся тестовые значения):
Начиная с пустой строки, сгенерируйте все строки, заданные расширением строки, находящейся в данный момент в наборе, добавив символ из алфавита слева или справа (оба).
Алфавит для генерации контейнерных строк выбран вами.
Вы проверяете 2 алфавита на содержащиеся строки. Один - это тот, который составляет контейнерные строки, другой - его дополнение.
Непосредственно не отвечает на ваш вопрос, но вы можете найти алгоритмы в книге - Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология - интересные (имеет много новых алгоритмов поиска по подстроке). Кроме того, это также хороший источник особых и сложных случаев.
Процедура, которая может дать интересную статистику, хотя сейчас у меня нет времени на тестирование:
Рандомизировать по длине строки, затем рандомизировать по содержимому строки этой длины, затем рандомизировать по смещению / длине подстроки (возможно, что-то не в строке), затем случайным образом перебить по подстроке (возможно, не совсем), повторить.