Эта страница требует существенной переработки. |
Поиск подстроки в строке — одна из простейших задач поиска информации. Применяется в виде встроенной функции в текстовых редакторах, СУБД, поисковых машинах, языках программирования и т. п.
В задачах поиска традиционно принято обозначать шаблон поиска как needle (с англ. — «иголка»), а строку, в которой ведётся поиск — как haystack (с англ. — «стог сена»). Также обозначим через Σ алфавит, на котором проводится поиск.[источник не указан 1129 дней]
Если считать, что строки нумеруются с 1, простейший алгоритм (англ. brute force algorithm, naïve algorithm) выглядит так.
for i=0...|haystack|-|needle| for j=0...|needle| if haystack[i+j + 1]<>needle[j] then goto 1 output("Найдено: ", i+1) 1:
Простейший алгоритм поиска даже в лучшем случае проводит |haystack|−|needle|+1 сравнение; если же есть много частичных совпадений, скорость снижается до O(|haystack|·|needle|).
Показано, что примитивный алгоритм отрабатывает в среднем 2h сравнений[1].
На сегодняшний день существует огромное разнообразие алгоритмов поиска подстроки. Программисту приходится выбирать подходящий в зависимости от таких факторов.
rep cmpsd
на x86). На таких процессорах заманчиво применить алгоритм, который просто бы сравнивал needle с haystack — разумеется, не во всех позициях.Как правило, в текстовом редакторе достаточно взять самый простой эвристический алгоритм наподобие Бойера — Мура — Хорспула — даже очень медленный ПК справится с поиском за доли секунды. Если же объём текста измеряется гигабайтами, либо поиск запущен на сервере, который обрабатывает множество запросов — приходится выбирать наиболее удачный алгоритм из доступных. Например, программы определения плагиата осуществляют онлайн-проверку, используя алгоритмы поиска подстроки среди большого количества документов, хранящихся в собственной базе.
Для сокращения обозначим:
Вычислительная сложность определяется до первого совпадения. Жирным шрифтом выделены важнейшие с практической точки зрения алгоритмы.
Во всех этих алгоритмах сравнение строк является «чёрным ящиком». Это позволяет использовать стандартные функции сравнения участков памяти, зачастую оптимизированные на ассемблерном уровне под тот или иной процессор и не выдающие точки, в которой наступило несовпадение.
К этой категории относится и примитивный алгоритм поиска.
Название | Предв. обработка | Сложность | Примечания | |
---|---|---|---|---|
типичная | макс. | |||
Примитивный алгоритм | Нет | 2H | O(Hn) | |
Алгоритм Бойера — Мура — Хорспула | O(n+σ) | ~ 2H / σ[2] | O(Hn) | Упрощённый до предела алгоритм Бойера — Мура; использует только видоизменённую эвристику стоп-символа — за стоп-символ всегда берётся символ haystack, расположенный напротив последнего символа needle. |
Алгоритм быстрого поиска Алгоритм Санди |
O(n+σ) | <H | O(Hn) | Также использует исключительно эвристику стоп-символа — но за стоп-символ берётся символ haystack, идущий за последним символом needle. |
Это семейство алгоритмов страдает невысокой скоростью на «хороших» данных, что компенсируется отсутствием регрессии на «плохих».
Название | Предв. обработка | Сложность | Примечания | |
---|---|---|---|---|
типичная | макс. | |||
Алгоритм Рабина-Карпа | O(n) | <H+n | O(Hn) | Хеширование позволяет серьёзно снизить сложность в среднем |
Автоматный алгоритм Алгоритм Ахо-Корасик |
O(nσ) | = H | Строит конечный автомат, который распознаёт язык, состоящий из одной-единственной строки. После небольшой модификации позволяет за один проход по haystack найти одну строку из нескольких. | |
Алгоритм Кнута-Морриса-Пратта | O(n) | ≤ 2H | Один из первых алгоритмов с линейной оценкой в худшем случае. Модификация алгоритма Ахо-Корасик, строящая автомат неявно на основе префикс-функции. | |
Алгоритм Апостолико-Крошмора | O(n) | < H | ≤1,5H | |
Алгоритм Shift-Or Bitap-алгоритм Двоичный алгоритм |
O(n+σ) | =H·ceil(n/w) | Эффективен, если размер needle (в символах) не больше размера машинного слова (в битах, обозначен как w). Легко переделывается на приблизительный поиск, поиск нескольких строк. |
В этом семействе алгоритмов needle движется по haystack слева направо, но сравнение этих строк друг с другом проводится справа налево. Сравнение справа налево позволяет в случае несовпадения сдвинуть needle не на одну позицию, а на несколько.
Название | Предв. обработка | Сложность | Примечания | |
---|---|---|---|---|
типичная | макс. | |||
Алгоритм Бойера — Мура | O(n+σ) | <H | O(Hn) | Стандартный алгоритм поиска подстроки в строке. Считается наиболее эффективным алгоритмом общего назначения.[3] |
Алгоритм Чжу-Такаоки | O(n+σ²) | <H | O(Hn) | Алгоритм Бойера — Мура, оптимизированный под короткие алфавиты |
Алгоритм Апостолико-Джанкарло | O(n+σ) | <H | ≤1,5H | Одна из первых попыток получить <H в типичном случае и O(H) в худшем. Очень сложен в реализации. |
Турбо-алгоритм Бойера — Мура | O(n+σ) | <H | ≤2H | Один из наиболее эффективных алгоритмов, не дающих регрессии на «плохих» данных |
Название | Предв. обработка | Сложность | Примечания | |
---|---|---|---|---|
типичная | макс. | |||
Непримитивный алгоритм | const | <H | O(Hn) | Простой алгоритм, сравнивающий второй символ, затем начиная с третьего в режиме «чёрного ящика», и, наконец, первый. При n[1]≠n[2][4] и несовпадении на второй-третьей стадии — сдвиг на 2 вправо. |
Алгоритм Райты Алгоритм Бойера — Мура — Хорспула — Райты |
O(n+σ) | <H | O(Hn) | Эмпирический алгоритм, оптимизированный под английские тексты. Сравнивает последний символ, потом первый, потом средний, потом все остальные; при несовпадении — сдвиг по Хорспулу. |
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .