Отчет по алгоритмам поска подстроки в строке
Самунь Виктор, группа КН-101, e-mail: samun@k66.ru

Содержание:
  1. Тестируемые алгоритмы
  2. Методика тестирования
  3. Проводимые тесты
  4. Параметры компьютера, на котором проводилось тестирование
  5. Ход тестирования и предварительные результаты
  6. Сравнение результатов тестирования
  7. Заключение

Тестируемые алгоритмы

Нами будет проведено тестирование следующих алгоритмов:

Архив с тестирующей системой, реализацией алгоритмов и результатами тестов расположен здесь.

 

Методика тестирования
Для каждого алгоритма у нас уже имеется тестирующая система, которая представляет из себя набор минимум трех файлов:
Timer.js, Tester.wsf, *.cmd
Timer.js выполняет считывание данных для проверки (искомая подстрока и файл с текстом, в котором будет выполняться поиск) и выполняет роль таймера для измерения времени работы алгоритма;
Tester.wsf выполняет реализованный алгоритм на исходных данных (текст и подстрока), считанных сценарием  Timer.js;
*.cmd выполняют пакетную обработку алгоритма.

Запуск проверки осуществляется следующим образом: в командной строке пишется следующая команда:
cscript Tester.wsf подстрока имя_файла_с_текстом количество_байт
подстрока – строка, которую мы ищем;
имя_файла_с_текстом – имя файла, где расположен текст, в котором мы будем искать подстроку;
количество_байт – аргумент, указывающий, сколько байт текста нам нужно прочитать от начала текста (если указан ноль, то будет прочитан весь текст).

Эти программы позволят нам получить нужную нам характеристику алгоритмов – время работы и на основе полученных результатов подвести итоги.



Проводимые тесты
Для каждого алгоритма мы сначала проведем предварительное тестирование на одном и том же тесте.
Предварительное тестирование заключается в следующем: сначала мы напишем самый простой вариант алгоритма и запустим его проверку на большой длине текста (будем брать текст длиной 2700000 символов). Далее, не меняя сути алгоритма, при помощи средств языка JScript начнем оптимизировать его, тем самым уменьшая время работы алгоритма. После того, как будут получены достаточно короткие времена работы и последующие изменения уже не будут оказывать значительное влияние на время выполнения алгоритма, запустим основную проверку алгоритма.

В основную проверку алгоритма войдут следующие тесты:

Отметим, что каждый тест мы будем запускать несколько раз из-за того, что точное время работы мы измерить не можем, а значит, будем иметь погрешности в измерениях времени работы. Но если есть погрешности в измерении тестирования, то нужно будет запускать один и тот же тест несколько раз, а результатом (временем работы) в этом случае следует считать средний результат всех тестов.
Для многократного запуска определенного теста предусмотрен пакетный файл Run.cmd.
Команда запуска: Run.cmd TESTSCOUNT TESTER SUBSTRING FILENAME LENGTH RESULTFILE
TESTSCOUNT – количество запусков теста;
TESTER.wsf файл с алгоритмом, который будет тестироваться;
SUBSTRING – искомая подстрока;
FILENAME – имя файла с текстом, в котором будет проводиться поиск;
LENGTH – сколько байт текста нам нужно прочитать от начала (чтобы прочесть весь текст, указывается ноль (0));
RESULTFILE – имя файла, куда будут выводится результаты проверки. (время работы каждого теста, среднее время и параметры запуска пакетного файла)
При этом, если файл существует, он будет перезаписан.

Запуск первой части основной проверки выполняет пакетный файл Start.cmd.
Команда запуска: Start.cmd TESTSCOUNT TESTER SUBSTRING FILENAME MAXLENGTH
TESTSCOUNT – количество запусков теста;
TESTER – .wsf файл с алгоритмом, который будет тестироваться;
SUBSTRING – искомая подстрока;
FILENAME – имя файла с текстом, в котором будет проводиться поиск;
MAXLENGTH – 0.01% от максимальной длины текста.
Этот пакетный файл работает следующим образом: он генерирует числа от 2 до параметра MAXLENGTH включительно (если это число четное и исключительно, если оно нечетное) с шагом 2, и умножает число на 10000. Полученное число – количество байт, которые будут прочитаны от начала текста. Затем Start.cmd запускает пакетный файл Run.cmd, который и выполнит тестирование на указанных параметрах. Имя результирующих файлов будет состоять из префикса r_ , сгенерированного числа и расширения .txt. При этом, если какой-нибудь файл с таким именем будет существовать, он будет просто перезаписан.

Запуск второй части основной проверки выполняет пакетный файл StartTest.cmd.
Команда запуска: StartTest.cmd TESTSCOUNT TESTER FILENAME LENGTH STRINGS
TESTSCOUNT – количество запусков теста;
TESTER – .wsf файл с алгоритмом, который будет тестироваться;
FILENAME – имя файла с текстом, в котором будет проводиться поиск;
LENGTH – сколько байт текста нам нужно прочитать от начала (чтобы прочесть весь текст, указывается ноль (0));
STRINGS – имя файла с подстроками, поиск которых будет осуществлен.
Этот пакетный файл работает следующим образом: он считывает из файла STRINGS очередную строку, запоминает число, записанное в начале строки, все остальное (исключая ведущие пробелы) считается подстрокой. Затем StartTest.cmd запускает пакетный файл Run.cmd, который выполнит проверку на данных параметрах теста. Имя результирующих файлов будет состоять из префикса r_ , запомненного числа и расширения .txt. Опять же, если какой-нибудь файл с таким именем уже будет существовать, он будет просто-напросто перезаписан. В качестве числа для удобства рекомендуется указывать длину подстроки.

 

Параметры компьютера, на котором проводилось тестирование
  1. Операционная система: Windows XP Professional SP2;
  2. Процессор: Intel Pentium III 1.00 ГГц;
  3. Размер RAM: 256 Мб 


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

Ход тестирования и предварительные результаты

Напомним, что мы проведем тестирование следующих алгоритмов:

Теперь пришло время описать ход проводимого нами тестирования, дать некоторое описание тестируемых алгоритмов и получить некие предварительные результаты.

1. Поиск грубой силой (Bruteforce)
Все реализации этого алгоритма и результаты тестирования расположены в папке Bruteforce. В подпапках расположены различные реализации этого алгоритма.
Сначала мы написали ту реализацию данного алгоритма, которая первая приходит в голову. Затем, выполнив предварительное тестирование на подстроке длиной 3 символа и тексте длиной 2700000 байт (далее эти параметры тестирования мы будем называть начальными параметрами), получим среднее время работы алгоритма (файл Result.txt): 27636 мс. Такое время работы является долгим, поэтому будем искать пути улучшения алгоритма, используя конструкции языка JScript, при этом сам алгоритм сохраняя неизменным.
Первую оптимизацию можно провести, заметив в коде такую строку:

(i = 0; i < (string.length - subString.length + 1); ++i) {
Мы видим, что в условии продолжения работы цикла находится неизменное в ходе работы неконстантное выражение, которое каждый раз вычисляется. Добавим перед циклом строку:
l = (string.length - subString.length + 1);
и изменим условие продолжения работы цикла соответствующим образом, а затем снова запустим тестирование на начальных условиях. При этом время работы сократится. Итак, мы уменьшили время работы: теперь алгоритм работает не 27636 мс, как раньше, а всего 22797 мс – заметный выигрыш.
Но давайте выполним еще несколько оптимизаций.
Вторая оптимизация заключается в следующем: весь алгоритм занесем в некоторую функцию F(), а каждый раз будем вызывать эту функцию. Казалось бы, вызов функции – лишние временные затраты, но дело, как мы сейчас убедимся, обстоит иным образом в языке JScript. Запустим вторую оптимизацию алгоритма, и заметим следующее: время работы сократилось с 22797 мс до 18906 мс. То есть, в JScript'е, по сути, при вызове функции время работы уменьшается. Почему это происходит – остается только догадываться…
Но мы пойдем дальше и еще немного усовершенствуем алгоритм.
Третья оптимизация заключается в том, что мы во время выполнения алгоритма оперируем с переменными, которые имеют длинные имена (например, string и subString). Мы заменим имена на более короткие и после запуска третьей оптимизации увидим, что, действительно, время работы немного сократилось: теперь алгоритм работает не 18906 мс, а 18758 мс.
Но эта небольшая оптимизация не очень заметна, хотя при многократном вызове она все равно окажет влияние. Таким образом, средствами языка мы сократили время работы в 1,5 раза.
После оптимизации алгоритма можно запускать тестирование. Как мы уже говорили, у нас есть два основных теста: тест с фиксированной длиной подстроки и переменной длиной текста и тест с фиксированной длиной текста, но переменной длиной подстроки.
Результаты тестирования на фиксированной длине подстроки с переменной длиной текста приведены на этом графике:
Как мы видим, алгоритм работает линейное время.
Но нам интересно еще взглянуть на зависимость числа вхождений этой фиксированной подстроки от длины текста. Может быть, эта зависимость оказывает какое-нибудь влияние на наш результат? Зависимость числа вхождений фиксированной подстроки от длины текста приведена на этом графике (темно-синяя линия – реальная зависимость, а красная линия – наилучшее линейное приближение реальной зависимости):
Как видно, эта зависимость хорошо ложится на прямую.
Оказывается, что этот факт влияет на то, насколько сильно будет отклоняться от прямой график зависимости времени работы алгоритма от длины текста. Давайте в этом убедимся. Мы сгенерировали искусственный текст (то есть практически не встречающийся реально), в котором зависимость числа вхождений фиксированной подстроки от длины текста ведет себя следующим образом:
Выполнив тестирование, мы получим следующий график зависимости времени работы алгоритма от длины текста:
Как видно, время работы в этом случае нелинейно. Даже в пределах погрешности (50 мс) график не ложится на синюю прямую, которая является наилучшим линейным приближением данных (расчет проводился программой Origin 7.5, которая использует для вычисления метод наименьших квадратов). При такой нелинейной зависимости несколько затруднительно сравнивать алгоритмы. Поэтому при непосредственном сравнении алгоритмов результатами, полученными на этом тексте, пользоваться не будем.
Алгоритмы мы будем сравнивать на основе тех результатов, которые будут получены на том тексте, которым мы пользовались сначала. Теперь приведем таблицу результатов тестирования на фиксированной длине текста с различными длинами подстрок (а значит, различным количеством вхождений):
Длина подстроки Количество вхождений Время работы алгоритма
1 165633 17332
3 8111 17001
5 307 17136
7 38 17714
9 259 17612
11 0 17569
13 0 17570
15 0 18590
19 1 17088
27 1 17112
42 1 17028
79 1 17028
Пока строить графики и анализировать результаты этого теста бессмысленно, по той причине, что количество вхождений везде разное. Будет смысл сравнивать эти результаты (время работы) в зависимости от алгоритмов. В конце мы приведем это сравнение.

2. Поиск с помощью Hash-функции 
Сначала скажем несколько слов о использованных Hash-функциях.
Мы упомянули, что будем тестировать алгоритм, который используют четыре Hash-функции, а именно:

Давайте разберемся, что же стоит за этими словами. Пусть нам дана строка s длины n, ее элементы обозначим si, код символа на позиции j обозначим s[j], hash-функцию от s обозначим H(s).

1. Простая Hash-функция.
Назовем простой hash-функцией функцию, определяемую следующим образом[1]:.
Преимущество этой hash-функции – простота пересчета при удалении начального символа и добавлении символа в конец, недостаток – много коллизий.

2. Оптимизированная Hash-функция.
Назовем оптимизированной hash-функцией функцию, определяемую следующим образом: .
Преимущество этой hash-функции – простота пересчета при удалении начального символа и добавлении символа в конец, а также эта hash-функция имеет гораздо меньше коллизий, чем предыдущая.

3. Hash-функция Рабина-Карпа.
Хотелось бы иметь некоторую hash-функцию, вычисление которой происходит быстро и которая имеет мало коллизий. Две предыдущие hash-функции дадут одинаковые результаты, если мы будем в строке переставлять буквы (так как обычное сложение обладает свойством коммутативности). Поэтому нам нужно иметь такую функцию, которая еще учитывает каким-то образом позицию символа. Такие функции существуют.
Они выглядят в простом случае следующим образом: , где f(x) – некоторая функция.
Наиболее простым вариантом функции будет умножение аргумента функции на какое-нибудь число, но результат умножения будет легко вычисляться, если это будет умножение на 2 (тогда процессору просто надо будет приписать нолики справа в двоичном представлении числа). Таким образом, hash-функция будет такого типа: , где g(x) – некоторая функция. При этом она будет легко пересчитываться, если g(i)=n-i. Будет достаточно вычесть один член из старого значения, полученное значение умножить на 2 и добавить еще один член.
Это и есть hash-функция Рабина-Карпа и выглядит она следующим образом: .

4. Полностью пересчитываемая Hash-функция.
Интересно провести тестирование с какой-нибудь hash-функцией, которую при смещении образца необходимо полностью пересчитывать. Такой, например, является hash- функция такого вида: .
Но возведение в степень – долгая операция, поэтому мы будем искать более простую с точки зрения вычислений hash-функцию. Была найдена функция HashPJW[2], мы ее реализуем за исключением одного момента, что уберем операцию взятия остатка, производимую в оригинальной функции. Это нужно для уменьшения числа коллизий. Модифицированную таким образом HashPJW мы назовем полностью пересчитываемой hash-функцией.

Теперь перейдем непосредственно к описанию проведенных нами тестов и оптимизаций.
Все реализации этого алгоритма и результаты тестирования расположены в папке Hash. В подпапках расположены различные реализации этого алгоритма.
Традиционно, начнем с описания оптимизаций алгоритма.
Самая простая реализация алгоритма поиска (при этом мы оптимизировали и все данные приводим только для простой hash-функции, в остальных меняется лишь та часть, которая отвечает за вычисления) с использованием дополнительной функции оптимального пересчета при сдвиге образца на начальном тесте работает 50441 мс. Это очень большое время – даже алгоритм грубой силы быстрее работает в несколько раз.
Выполним ту же оптимизацию, что и в алгоритмы грубой силы – заключим весь алгоритм в отдельную функцию и будем ее вызывать (а оптимизацию с длиной имен переменных и повторным вычислением константных выражений мы предусмотрели в первом варианте реализации).
Первая оптимизация, как и следовало ожидать, дает некоторое уменьшение времени работы: алгоритм работает не 50441 мс, а всего 45084 мс. Вторая оптимизация заключается в противоположном: оптимальный пересчет не будем выносить отдельно как функцию. Теперь алгоритм стал незначительно быстрее работать: 44928 мс взамен предыдущих 45084 мс.
Немного сократив время работы алгоритма, мы запустим тестирование.
Структура папок с результатами проверок следующая: все результаты лежат в подпапке 4. В ней расположены подпапки a, b, c, d - в них расположены результаты тестирования соответствующих hash-функций. В каждой из этих подпапок расположены еще две – с именами 1 и 2: в 1 расположены тесты с фиксированной длиной подстроки, в 2 - с фиксированной длиной текста.
Приведем результаты тестирования на фиксированной подстроке:


Простая hash-функция


Оптимизированная hash-функция


Hash-функция Рабина-Карпа


Полностью пересчитываемая hash-функция

Как видно, результаты тестов слабо отличаются и алгоритмы работают линейное время. Поэтому гораздо удобнее результаты тестирования занести в таблицу. Для этого будем брать точку, которой соответствует максимальная длина текста и занесем в таблицу соответствующее время работы.
Название hash-функции Время работы
Простая hash-функция 44911
Оптимизированная hash-функция 45067
Hash-функция Рабина-Карпа 45061
Полностью пересчитывваемая hash-функция 45052
Из таблицы видно, что результаты тестирования практически совпадают, различия оказывают только математические операции над числами. Теперь приведем таблицу[3] результатов тестирования на фиксированной длине текста с различными длинами подстрок (а значит, различным количеством вхождений):
Длина подстроки Количество вхождений Время работы для разных hash-функций
Hash-1 Hash-2 Hash-3 Hash-4
1 165633 43412 43410 43600 43614
3 8111 43019 43079 36282 43332
5 307 32787 32783 36348 43481
7 38 44071 44074 39402 44163
9 259 33070 33076 42678 44038
11 0 32880 32877 43120 43953
13 0 32841 32841 37950 44062
15 0 32825 32820 36434 44858
19 1 32761 32757 36320 43254
27 1 32893 32879 36446 43407
42 1 32911 32892 36449 43311
79 1 32832 32839 32846 43407
 Посмотрим, как выглядит зависимость времени работы алгоритма от длины текста на «искусственном» тексте. Hash-функция Рабина-Карпа дала следующий результат [4]:
Мы видим, что разброс все-таки есть и алгоритм работает также нелинейное время – больше половины точек касается прямой лишь границей погрешности, а отсюда следует, что они могут и не лежать на прямой, то есть прямая – это плохое приближение. Напомним, что таблица сравнения всех алгоритмов будет приведена в конце.

3. Поиск с использованием автомата
Все реализации этого алгоритма и результаты тестирования расположены в папке Automaton. В подпапках расположены различные реализации этого алгоритма.
Как обычно, начнем с описания оптимизаций алгоритма.
Самая простая реализация алгоритма работает на начальном тесте 35944 мс. Первая и последняя в этом алгоритме оптимизация заключается в том, что мы весь алгоритм помещаем в отдельную функцию. Заметим, что мы эту процедуру делаем во всех, без исключения, алгоритмах, по той причине, что нам так и не ясна природа столь странного поведения исполняющей системы языка JScript.
Выполнив первую оптимизацию, время работы сократилось с 35944 мс до 26913 мс. То есть, время сократилось примерно в 1,3 раза.
Все остальные длительные операции, которые используются в алгоритме – обращение к элементу массива, метод concat() – работают долго, но без них не обойтись. И оптимизировать их крайне затруднительно. Поэтому, оптимизировать больше нечего, и мы запустили тестирование.
График зависимости времени от длины текста выглядит следующим образом:
Нетрудно видеть, что и этот алгоритм также работает линейное время.
Теперь приведем таблицу результатов тестирования на фиксированной длине текста с различными длинами подстрок (а значит, различным количеством вхождений):
Длина подстроки Количество вхождений Время работы алгоритма
1 165633 26774
3 8111 26811
5 307 26957
7 38 27059
9 259 27070
11 0 27026
13 0 27085
15 0 27024
19 1 27300
27 1 27354
42 1 27543
79 1 27652
Теперь посмотрим, как же алгоритм работает на «искусственном» тексте.
Невооруженным глазом видно, что автомат даже на таких данных, которые были подобраны специальным образом ведет себя не так, как другие прежде рассмотренные алгоритмы – он работает линейное время. (Вспомним поиск грубой силой: при подходящем выборе данных график будет сильно напоминать ветвь параболы)

4. Поиск с помощью алгоритма Боэра-Мура
Все реализации этого алгоритма и результаты тестирования расположены в папке Boyer-Moore. В подпапках расположены различные реализации этого алгоритма.
Мы реализуем алгоритм Боэра-Мура с одной эвристикой – эвристикой плохого символа.
То есть, мы предварительно построим таблицу смещений образца, затем «наложим» подстроку на начало строки и начнем сопоставление символов, начиная с конца строки. Если совпали все символы, то мы просто сдвинем подстроку на одну позицию и повторим поиск. В противном случае, если какие-то символы у нас не совпадут, то по таблице смещений определим, на сколько позиций нам нужно сдвинуть образец (подстроку) и сдвинем его на это число позиций вправо.
Как уже неоднократно говорилось, сначала выполним самую простую реализацию алгоритма.
На ее выполнение на начальном тесте уходит 25788 мс. Сделав одну оптимизацию – помещение алгоритма в отдельную функцию, мы сократим время выполнения с 25788 мс до 19915 мс.
В остальном же реализацию алгоритма еще больше оптимизировать не нужно по тем же самым причинам, которые у нас были в предыдущем алгоритме.
График зависимости времени от длины текста выглядит следующим образом:
Заметим, что и этот алгоритм также работает линейное время.
Теперь приведем таблицу результатов тестирования на фиксированной длине текста с различными длинами подстрок (а значит, различным количеством вхождений):
Длина подстроки Количество вхождений Время работы алгоритма
1 165633 53136
3 8111 18117
5 307 11068
7 38 7901
9 259 6432
11 0 5145
13 0 4336
15 0 3823
19 1 3382
27 1 2493
42 1 1734
79 1 961
Заметим одну особенность в этой таблице, которой не было ни в одной из предыдущих: с увеличением длины подстроки, независимо от количества вхождений, время работы алгоритма уменьшается.
Таким образом, на больших подстроках он работает крайне быстро.
Теперь проанализируем, как алгоритм ведет себя на «искусственном» тексте.
На «искусственном» тексте алгоритм ведет себя следующим образом:
Видно, что и этот алгоритм на этом тексте работает также, как и автомат, за исключением того, что Боэр-Мур быстрее.



Сравнение результатов тестирования

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

Длина
подстроки
Количество
вхождений
Время работы для разных hash-функций
Грубая сила Простая
Hash-функция
Оптимизированная
Hash-функция
Hash-функция
Рабина-Карпа
Полностью
пересчитываемая
Hash-функция
Автомат Боэр-Мур
1 165633 17332 43412 43410 43600 43614 17332 17332
3 8111 17001 43019 43079 36282 43332 17001 17001
5 307 17136 32787 32783 36348 43481 17136 17136
7 38 17714 44071 44074 39402 44163 17714 17714
9 259 17612 33070 33076 42678 44038 17612 17612
11 0 17569 32880 32877 43120 43953 17569 17569
13 0 17570 32841 32841 37950 44062 17570 17570
15 0 18590 32825 32820 36434 44858 18590 18590
19 1 17088 32761 32757 36320 43254 17088 17088
27 1 17112 32893 32879 36446 43407 17112 17112
42 1 17028 32911 32892 36449 43311 17028 17028
79 1 17028 32832 32839 32846 43407 17028 17028

Из таблицы мы видим следующую закономерность:
если длина подстроки больше четырех символов, то быстрее всех работает алгоритм Боэра-Мура, затем по увеличению продолжительности времени идут: грубая сила, автомат, Hash-функции;
на средних длинах (в таблице этому соответствует длина подстроки три символа) быстрее всех работает алгоритм грубой силы, далее идут: Боэр-Мур, автомат, Hash-функции;
а на кратчайшей длине подстроки (один символ) алгоритм Боэра-Мура показывает самое продолжительное время.
У Hash-функций ситуация следующая: полностью пересчитываемая Hash-функция ведет себя практически стабильно – время работы колеблется в районе 43-44 секунд, простая и оптимизированная Hash-функции работают одинаковое время в пределах погрешности, Hash- функция Рабина-Карпа в большинстве случаев работает медленнее простой и оптимизированной функций, несмотря на то, что эта функция имеет малое число коллизий.
Дело все в том, что эта функция, по сравнению с простой Hash-функцией, выполняет более «тяжелые» операции: побитовые сдвиги, а значит, она будет работать дольше. Но почему она работает дольше оптимизированной – не ясно, по-видимому, исполняющая система JScript быстрее выполняет возведение в квадрат, чем сдвиг, хотя процессору легче сдвинуть число на нужное число позиций, чем умножать его на что-либо.
Из этой таблицы можно сделать следующий вывод: на больших длинах подстрок для увеличения быстродействия следует пользоваться алгоритмом Боэра-Мура, а на маленьких и алгоритм грубой силы даст неплохие результаты.

Теперь сравним быстродействие алгоритмов на фиксированной длине подстроки.
В силу полученных результатов, а именно того, что все зависимости на реальном тексте линейны, можно сравнить быстродействие алгоритма по значению в одной ненулевой точке.
Составим сравнительную таблицу:

Алгоритм Грубая сила Простая
Hash-функция
Оптимизированная
Hash-функция
Hash-функция
Рабина-Карпа
Полностью
пересчитываемая
Hash-функция
Автомат Боэр-Мур
Время работы 18748 44911 45067 45061 45052 27076 19974
Таким образом, на фиксированной длине подстроки быстрее всех работает алгоритм грубой силы, затем в порядке увеличения продолжительности времени идут: Боэр-Мур, Автомат, Hash-функции.
Но мы тестирование проводили на длине подстроки три символа.
Из предыдущей таблицы видно, что Боэр-Мур работает тем быстрее, чем больше длина подстроки, а автомат и алгоритм грубой силы работают в среднем одно и то же время.
Поэтому, в среднем получается следующая символическая таблица, отражающая быстродействие алгоритмов:
1 Алгоритм Боэра-Мура
2 Алгоритм грубой силы
3 Автомат
4 Простая и оптимизированная Hash-функции
5
6 Hash-функция Рабина-Карпа
7 Полностью пересчитываемая Hash-функция

Из приведенных ранее графиков работы алгоритмов не нестандартном тексте видно, что такие алгоритмы, как «Грубая сила», «Hash-функция» могут немного отклоняться от линейной сложности, а автомат и алгоритм Боэра-Мура на этом тесте ведут себя линейным образом.
Чтобы эти алгоритмы вели себя нелинейно, требуются совершенно другие искусственные тексты, на которых другие алгоритмы, похоже, будут работать линейным образом в большинстве случаев.
Например, чтобы алгоритм Боэра-Мура работал максимально долго на длине подстроки два символа, достаточно составить длинную строку, алфавит которой состоит всего лишь из одной буквы – первой буквы подстроки. Тогда, это будет, по сути, алгоритм грубой силы, так как смещение будет происходить все время на одну позицию. Но в этом случае остальные алгоритмы будут вести себя линейно. Аналогичным образом можно подобрать тексты, на которых этот алгоритм будет вести себя нелинейным образом. Для этого требуется, чтобы сначала алгоритм сравнивал максимально возможное количество символов, потом смещал подстроку на минимально возможное количество позиций, потом чтобы сравнивал минимально возможное количество символов и смещал на максимально возможное количество позиций. Тогда алгоритм сначала будет работать максимально долго, затем максимально быстро.

Давайте теперь оценим сложность каждого из алгоритмов в лучшем и худшем случаях.
Для начала обозначим длину подстроки за M, длину строки – N, причем M <= N.
Назовем данные текст и подстроку худшим случаем, если алгоритм выполняет максимально возможное количество операций.
Назовем данные текст и подстроку лучшим случаем, если алгоритм выполняет минимально возможное количество операций.

Начнем оценку с алгоритма грубой силы.
В лучшем случае сравнение первого символа окажется неудачным, тогда алгоритм сместит образец. Если при смещении всегда будет происходить та же самая ситуация, то алгоритм выполнит минимальное количество сравнений. Их число будет равно: N-M+1. Таково число сравнений при лучшем случае.
В худшем случае число вхождений подстроки в строку максимальное, то есть алгоритм совершит максимально возможное количество операций сравнения. В этом случае число сравнений оказывается равным: M*(N-M+1).
Таким образом, график зависимости времени от длины текста лежит между этими двумя прямыми.

Теперь проанализируем алгоритмы, использующие Hash-функции.
Предположим для простоты, что Hash-функцию можно пересчитать, если добавить и вычесть один член; и вычисление этой значения Hash-функции от одного символа занимает такое же время, как и сравнение двух чисел.
В этом случае, в лучшем случае вхождений подстрок не будет и функция выполнит операций, длительность которых совпадает с длительностью сравнения: 2N.
В худшем случае, опять же, подстрока будет входить максимально возможное количество раз и число операций будет равно: 2N+M*(N-M+1).
Из приведенных результатов видно, что в лучшем случае алгоритм грубой силы работает быстрее, чем hash-функция, в худшем случае наблюдается аналогичная ситуация.
А значит, в среднем, Hash-функция работает дольше, чем алгоритм грубой силы.
Можно даже доказать, что Hash работает в лучшем случае минимум в два раза медленнее, чем Bruteforce, а в худшем – минимум в три.
Для этого достаточно поделить количество сравнений, которое совершает один алгоритм на соответствующее количество сравнений другого алгоритма и оценить полученное выражение. Но сложность алгоритмов оказывается одинаковой – константа на сложность не влияет.
Из приведенных выше формул понятно, что «нелинейность» графика на «искусственном» тексте, который мы использовали ранее, будет выражена гораздо сильнее, если подстрока будет большой длины (в нашем случае длина была 11 символов).

Теперь проанализируем автомат.
Автомат сначала выполняет построение таблицы переходов, затем выполняет всегда ровно N шагов. Значит, этот алгоритм всегда работает одинаковое время, если не считать построение таблицы переходов.
Проведя аналогичные расчеты, можно показать, что автомат работает медленнее, чем Bruteforce, но быстрее, чем Hash.

Наконец, проанализируем алгоритм Боэра-Мура с одной эвристикой.
В лучшем случае образец будет сдвигаться на всю длину, то есть, сравнений будет совершено , где [x] – целая часть числа x.
В худшем случае образец будет все время сдвигаться на одну позицию и будут сопоставляться каждый раз все символы подстроки. В этом случае число сравнений будет M*(N-M+1).
Таким образом, алгоритм Боэра-Мура работает даже в самом худшем случае теоретически также, как и алгоритм грубой силы в худшем случае. Но на практике алгоритм Боэра-Мура постоянно совершает вычисление того, на сколько позиций надо сдвигать образец, а эта операция длительная.
Причем на длине подстроки 1 символ эти вычисления происходят всегда и дают один и тот же результат: сдвиг на одну позицию. Обращений к элементам таблицы переходов будет N.
Если сделать поправку на тот факт, что обращение к элементам массива занимает столько же времени, сколько и сравнение двух символов, что в лучшем случае операций с длительностью, равной длительности сравнения символов будет ,
в худшем случае - (M+1)*(N-M+1).
То есть, на небольших длинах подстрок (один или два символа) алгоритм Боэра-Мура работает примерно столько же времени, сколько работает Hash – самый медленный из рассмотренных выше алгоритмов, но на длинах подстрок больше двух символов тот факт, что длина подстроки стоит в знаменателе, оказывает существенное влияние.
Можно проверить, что зависимость времени работы алгоритма Боэра-Мура от длины подстроки будет сильно похожа на гиперболу в нашем случае.
Действительно, если построить график по точкам, которые приводились в общей сравнительной таблице, то мы увидим следующее:
Этот график был построен в программе Origin 7.5 и программа вычислила уравнение гиперболы так, что все точки находятся на минимальном расстоянии от нее. (Другими словами, вычислила уравнение, исходя из метода наименьших квадратов).
Мы видим, что гипербола действительно хорошо описывает нашу зависимость – это видно из отчета программы: коэффициент, описывающий отклонение построенного графика от наших точек, приблизительно равен единице (он равен 0,99981); и даже получено уравнение гиперболы с погрешностями.
Это означает, что все приведенные выше расчеты в какой-то степени совпадают с тем, что происходит реально и мы объяснили полученные нами экспериментальные результаты: почему, например, Hash-функции столь долго работают и почему на длине подстроки, равной единице, алгоритм Боэра-Мура долго работает, а при увеличении длины подстроки в лучшем случае время работы уменьшается.


Заключение

Итак, мы провели достаточно широкий анализ некоторых алгоритмов поиска всех вхождений подстроки в строку, объяснили полученные результаты и обнаружили некоторые интересные факты, связанные с особым подбором текстов. Также мы сделали тестирующие пакеты для наших реализаций алгоритмов. Теперь мы опишем структуру каталогов, в которой находятся все реализации, тексты, тесты и результаты тестирования. Часть этой структуры указана в тексте, часть не указана вовсе, что может составлять некоторые неудобства.
Основной текст расположен в подпапке Normal папки Text.
«Искусственный» текст – в подпапке Text2.
В этих же подпапках расположена информация о количестве вхождений подстроки в строку.
Реализация каждого алгоритма расположена в папке, название которой соответствует названию алгоритма.

Структура папки Bruteforce следующая:
в подпапке 0 расположена самая первая реализация алгоритма,
в подпапках 1-3 расположены соответствующие оптимизации.
В подпапке 4 расположены результаты проверки на тесте с фиксированной длиной подстроки,
в подпапке 5 – с фиксированной длиной текста.
В подпапке 6 расположены результаты проверки на «искусственном» тексте.

Структура папки Hash следующая:
в подпапке 0 расположена самая первая реализация алгоритма,
в подпапках 1-2 расположены соответствующие оптимизации.
В подпапке 3 расположены результаты проверки на тесте с фиксированной длиной подстроки,
в подпапке 4 – с фиксированной длиной текста.
В этих двух папках в подпапках a, b, c, d расположены результаты проверки каждой из Hash-функций.
В подпапке 5 расположены результаты проверки на «искусственном» тексте.

Структура папки Automaton следующая:
в подпапке 0 расположена самая первая реализация алгоритма,
в подпапке 1 расположена оптимизация.
В подпапке 2 расположены результаты проверки на тесте с фиксированной длиной подстроки,
в подпапке 3 – с фиксированной длиной текста.
В подпапке 4 расположены результаты проверки на «искусственном» тексте.

Структура папки Boyer-Moore точно такая же, как и структура папки Automaton.

В каждой из этих папок есть текстовые файлы – результаты проверок.
Файлы с графиками не приводятся, так как все построенные графики есть в отчете, откуда их можно скопировать.


[1] Здесь и далее предполагаем, что элементы с строке нумеруются не с нуля, а с единицы
[2] Реализацию этой функции можно найти в книге «А.Ахо, Р.Сети, Д.Ульман: Компиляторы», стр. 418 (книга также еще известна как «Книга дракона»)
[3] В таблице Hash-функции указаны в том же порядке, в котором они уже неоднократно ранее перечислялись. Как обычно, на графике синяя прямая – наилучшее линейное приближение данных.
[4] На последующих графиках синяя прямая будет иметь тот же смысл.