Краткий обзор 5 строковых алгоритмов: наивный алгоритм Кнута-Морриса-Пратта, алгоритм Бойера-Мура, строковый хэш, суффикс-три.

TL;DR;

Шпаргалка по алгоритмам приведена в конце статьи.

Что первое приходит вам на ум, когда вы слышите слово алгоритмы? Двоичный поиск, «разделяй и властвуй», алгоритмы DFS, я полагаю. А как насчет строковых алгоритмов?

Давайте поговорим о самых известных алгоритмах String в этой статье.

Что такое алгоритмы String?

Алгоритмы, используемые для поиска строки в другой строке.

Случаи использования варьируются от обработки естественного языка до обнаружения плагиата, поисковых систем и схем баз данных. Например, вы когда-нибудь ошибались в слове и искали его? А вы видели сообщение Google `Вы имели в виду…`? Вот и все. Еще один прекрасный пример — поиск текста на веб-сайте, в pdf-файле или документе.

Цель алгоритмов сопоставления строк — найти точное одно или несколько вхождений заданной строки (шаблона/иголки) в большей строке (последовательности/стоге сена) или тексте.

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

Здесь упоминается несколько алгоритмов:

1. Наивный алгоритм

Подход грубой силы, который проверяет все символы последовательности.

✏️ Попробуйте поискать abcв aaaaaabc.
⚙️ Он сдвигает стог сена один за другим, чтобы увидеть вхождение. Если он найден, он снова переходит к следующим вхождениям.

🏆 Каковы его лучшие и худшие случаи?

  • В лучшем случае, когда иголки нет в стоге сена, поэтому ее не нужно лишний раз скользить.
  • Наихудший случай можно увидеть, когда отличается только последний элемент стога сена или когда все элементы стога сена включают иголку (xxin xxxxxxxxxx).

Таким образом, поиск строки грубым подходом приведет к временной сложности 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.