Краткий обзор 5 строковых алгоритмов: наивный алгоритм Кнута-Морриса-Пратта, алгоритм Бойера-Мура, строковый хэш, суффикс-три.
TL;DR;
Шпаргалка по алгоритмам приведена в конце статьи.
Что первое приходит вам на ум, когда вы слышите слово алгоритмы? Двоичный поиск, «разделяй и властвуй», алгоритмы DFS, я полагаю. А как насчет строковых алгоритмов?
Давайте поговорим о самых известных алгоритмах String в этой статье.
Что такое алгоритмы String?
Алгоритмы, используемые для поиска строки в другой строке.
Случаи использования варьируются от обработки естественного языка до обнаружения плагиата, поисковых систем и схем баз данных. Например, вы когда-нибудь ошибались в слове и искали его? А вы видели сообщение Google `Вы имели в виду…`? Вот и все. Еще один прекрасный пример — поиск текста на веб-сайте, в pdf-файле или документе.
Цель алгоритмов сопоставления строк — найти точное одно или несколько вхождений заданной строки (шаблона/иголки) в большей строке (последовательности/стоге сена) или тексте.
В этой статье я приведу шпаргалку по некоторым алгоритмам поиска строк, также известным как алгоритмы сопоставления строк, после краткого ознакомления с каждым из них.
Здесь упоминается несколько алгоритмов:
1. Наивный алгоритм
Подход грубой силы, который проверяет все символы последовательности.
✏️ Попробуйте поискать abc
в aaaaaabc
.
⚙️ Он сдвигает стог сена один за другим, чтобы увидеть вхождение. Если он найден, он снова переходит к следующим вхождениям.
🏆 Каковы его лучшие и худшие случаи?
- В лучшем случае, когда иголки нет в стоге сена, поэтому ее не нужно лишний раз скользить.
- Наихудший случай можно увидеть, когда отличается только последний элемент стога сена или когда все элементы стога сена включают иголку (
xx
inxxxxxxxxxx
).
Таким образом, поиск строки грубым подходом приведет к временной сложности O(n*m)
, а в худшем случае к O(m*(n-m+1))
, где m
— длина шаблона/иголки, а n
— длина последовательности/стога сена.
2. Алгоритм Кнута-Морриса-Пратта (KMP)
Это улучшенная версия наивного алгоритма для стога сена, в котором иголка появляется более одного раза.
⚙️ Алгоритм не обходит стог сена один за другим, вместо этого, при обнаружении несовпадения, КМП начинает искать совпадение с того символа, где совпадение было найдено.
✏️ Рассмотрим пример:
haystack = 'ABCACD', needle = 'ABCAB';
Итерация будет следующей:
Таким образом, в KMP стог сена проходится, когда временная сложность составляет O(n) даже для наихудшего случая.
3. Алгоритм Бойера Мура:
Это комбинация алгоритмов Naive и KMP.
⚙️ Предварительно обрабатывает строку как KMP и использует ее для пропуска несоответствий. Одним из важных моментов является то, что поиск начинается с последнего символа иглы.
Алгоритм использует два правила:
- правило плохого характера и
- Правило хорошего суффикса
Максимальное смещение, полученное из этих двух правил, является фактическим смещением, которое будет применено.
Правило плохого характера
1. Стрелка ищется с последнего символа и сравнение начинается слева.
2. Как только обнаруживается несоответствие, оно помечается как плохой символ.
3. Далее ищется плохой персонаж слева от стрелки
4. Если такой символ найден, то он заносится в смещение плохого символа.
✏️ Рассмотрим пример:
haystack = 'HELLOXWORLDXHEYWORLD', needle = 'XHEYWORLD';
Итерация будет следующей:
Правило хорошего суффикса
Разработано потому, что правило плохого характера не всегда может дать наилучшее предложение.
1. Стрелка ищется от последних символов, образующих подшаблон p от стрелки, и сравнение начинается слева.
2. Обнаружив несоответствие, проверьте следующее вхождение, p’
, p
слева. Есть еще несколько правил, которые необходимо учитывать, которые я объясню на примере ниже.
✏️ Рассмотрим пример:
haystack = ‘xyziHEYyABCxABCxABC’, needle = ‘yABCxABC’;
Итерация будет следующей:
В случае, если p’
не найдено, они находят наименьший возможный сдвиг, который соответствует префиксу иглы суффиксу p в стоге сена.
Если такой сдвиг невозможен, сместите иглу на ее длину так, чтобы игла прошла p
.
4. Строковый хэш
Идея здесь состоит в том, чтобы преобразовать строку в число, хэш строки, используя хеш-функцию.
Две строки считаются равными, если их хэши равны, поэтому, если H(x) === H (y)
, то x = y.
⚙️Полиномиальный мод некоторого простого числа p — самая мощная и простая хеш-функция со следующей формулой:
H(x1 . . . xk) = x[1]a^(k−1) + x[2]a^(k−2) + · · · + x[k−1]a + x[k] * (mod p)
5. Суффикс Трие
Trie — это древовидная структура данных для хранения строк, по одному символу в каждом узле.
Ниже приведена визуализация тройки, содержащей слова HELLO, HEY, HUMAN и HUMBLE.
Дерево суффиксов хранит каждый уникальный суффикс в каждом узле.
Это можно визуализировать следующим образом:
где um
из human
и humble
образуют уникальный суффикс.
После построения дерева поиск в нем строки займет O(n) время, где n
— длина текста.
Подводя итог, ниже можно найти шпаргалку для
- Наивный
- Алгоритм Кнута – Морриса – Пратта (KMP)
- Бойер Мур
- Строковый хэш и
- Суффикс Три
алгоритмы:
где n
и m
обозначают длину стога сена и иглы.
Надеюсь, вам понравилось читать! 🤞
Дайте мне знать, если вам нужна сводка для других строковых алгоритмов.
Открывайте свои комментарии и предложения в комментариях 📝.
А также не стесняйтесь обращаться ко мне в LinkedIn.