Алгоритмы поиска в строке

Постановка задачи поиска в строке


Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

Алгоритм прямого поиска



Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,

Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.

Сложность алгоритма:
Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).

Недостатки алгоритма:
1. высокая сложность — O(N*M), в худшем случае – Θ((N-M+1)*M);
2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);
3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

Алгоритм Д. Кнута, Д. Мориса и В. Пратта (КМП-поиск)



Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.
Пример.
(Символы, подвергшиеся сравнению, подчеркнуты.)


После частичного совпадения начальной части образа W с соответствующими символами строки Т мы фактически знаем пройденную часть строки и может «вычислить» некоторые сведения (на основе самого образа W), с помощью которых потом быстро продвинемся по тексту.

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Особенности КМП-поиска:
1. требуется порядка (N+M) сравнений символов для получения результата;
2. схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на единицу. К несчастью совпадения встречаются значительно реже чем несовпадения. Поэтому выигрыш от КМП-поиска в большинстве случаев текстов весьма незначителен.

Алгоритм Р. Боуера и Д. Мура (БМ-поиск)



На практике алгоритм БМ-поиска наиболее эффективен, если образец W длинный, а мощность алфавита достаточно велика.

Идея БМ-поиска – сравнение символов начинается с конца образца, а не с начала, то есть сравнение отдельных символов происходит справа налево. Затем с помощью некоторой эвристической процедуры вычисляется величина сдвига вправо s. И снова производится сравнение символов, начиная с конца образца.

Этот метод не только улучшает обработку самого плохого случая, но и даёт выигрыш в промежуточных ситуациях.
Почти всегда, кроме специально построенных примеров, БМ-поиск требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ образца всегда попадает на несовпадающий символ текста, число сравнений равно (N / M), в худшем же случае – О((N-M+1)*M+ p), где p – мощность алфавита.

Алгоритм Рабина-Карпа (РК-поиск)



Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

Пример. Пусть образец имеет вид W = 3 1 4 1 5
Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.


23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …
k1=314157(mod 13) – вхождение образца,
k2=673997(mod 13) – холостое срабатывание.

Из равенства ki= kj (mod q) не следует, что ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W[1…m] и T[s+1…s+m] на самом деле.
Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики.
В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

Пример: Сколько холостых срабатываний k сделает алгоритм РК, если
q= 11, 13, 17. Пусть W={2 6}

26 mod 11=4 → k =3 холостых срабатывания,
26 mod 13=0 → k =1 холостое срабатывание,
26 mod 17=9 → k =0 холостых срабатываний.

Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 38

    +3
    у Никлауса Вирта в «Алгоритмы и структуры данных» тоже неплохо описано и примеры есть на модуле или паскале.
      +8
      А вообще копипаста есть немного…
        0
        Частично взято из лекций, переработал, отредактировал, вот что получилось…
          +6
          Чего-то всёравно не хватает. Не мне указывать, но я бы добавил блок-схемы, какие-нибудь таблицы со сравнениями результатов работы алгоритмов. Можно сделать лучше. Удачи!
            0
            Спасибо за советы, в следующий раз все учту и исправлюсь.
              +6
              Ещё не поздно дополнить этот топик.
                +3
                Поддерживаю, с краткими блоксхемами и со сравнением работы алгоритмов будет намного лучше.
                  +2
                  К тому же пытался подвести. :-)
        +1
        Еще можно добавить что алгоритм Рабина — Карпа использует для проверки плагиата, так же что он эффективен для многострочного поиска и поиск по множество шаблонам и что нужно делать пре подготовку текста (вырезать все знаки пунктуации). Так же, что можно спокойно использовать свои хэш функции.
          0
          а Вы, случайно, не проводили тесты данных алгоритмов? недавно по информатике нужно было написать КМП и Рабина-Карпа и сравнить их с наивным алгоритмом (за квадрат), и Рабин-Карп работал в 2-10 раз хуже, чем наивный:) я грешу на медленную операцию % в питоне, но как-то это не очень похоже на правду
            0
            Рабин-Карп на коротких образцах (меньше 20 символов) сильно проигрывает (стабильно 40 мб/с при поиске чего угодно где угодно). КМП довольно быстрый (300 мб/с при поиска «Наташа» в Войне и Мир), Бойер-Мур (300-700 мб/с), Хорспул — до 2 гб/с(!), если не синтетические тесты.
            0
            А вы ничего не путаете c оценкой РК?
            Я, если честно, не осилил идею РК за вашей алегброй, но предположим N = 1000, M = 10 тогда в худшем случае РК намного менее шустр чем КМП, порядка О(9910) против O(1010), то есть почти в 10 раз медленее в худшем случае, как и заметил mydoom
              0
              Он заметил, что РК работал в 2-10 раз хуже наивного алгоритма, не смотря на то, что асимптотически сложности равны. Читайте внимательно.
                +1
                Извините, что читаю невнимательно комментарии, но если сконцентророваться на статье я вижу слова для РК:

                В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

                а для КМП:

                Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.

                и не вижу вообще нигде слов про то что то чему то асимптотически равно.

                Отсюда следует вопрос, который я и задал — не напутали ли с оценкой алгоритмов?

                Собственно, какова полезность алгоритма. который в худшем случае имеет квадратичную сложность по сравнению с линейной у КМП?

                Рабин и Карп с бухты-барахты придумали медленный алгоритм, а преподаватели от нечего делать его преподают, так по вашему что ли?
              +1
              А где же хеширование???
                0
                РК, имхо, один из частичных случаев хеширования :)
                +1
                Когда я учился, те же алгоритмы объясняли по этой книжке. Мне кажется, там доходчивее…
                  –3
                  это все интересно, но в современных языках данные алгоритмы встроены
                    +1
                    Это не отменяет необходимости знать их работу и применение.
                      –3
                      в большинстве практических задач таки отменяет :)
                      +1
                      Можно поинтересоваться, в каких?
                        –1
                        методы substring substr contains есть в python, java…
                          +1
                              for (int i = sourceOffset + fromIndex; i <= max; i++) {
                                      /* Look for first character. */
                                      if (source[i] != first) {
                                          while (++i <= max && source[i] != first);
                                      }
                          
                                      /* Found first character, now look at the rest of v2 */
                                      if (i <= max) {
                                          int j = i + 1;
                                          int end = j + targetCount - 1;
                                          for (int k = targetOffset + 1; j < end && source[j] ==
                                                   target[k]; j++, k++);
                          
                                          if (j == end) {
                                              /* Found whole string. */
                                              return i - sourceOffset;
                                          }
                                      }
                                  }
                          


                          это фрагмент метода indexOf класса String из jre.
                          Какие из данных алгоритмов, кроме алгоритма прямого поиска, встроены в современных языках программирования?
                            0
                            афигеть
                            а я думал там КМП…
                            вот это они лоханулись конечно…
                              +1
                              КМП требует дополнительной памяти для хранения вычисленной префикс-функции образца. Видимо, поэтому он и не вошел в стандартные библиотеки.
                                0
                                КМП — подготовка к поиску занимает какое-то время. Выделение памяти. Как правило поисковые строки короткие с минимумом самоповторений. Линейное сравнение использует SIMD-инструкции. Строки влезают в кэш L1 — повторное сравнение быстрое. Так что на практике КМП выигрывает в специфических условиях.
                                  0
                                  ну функция могла бы выбирать в зависимости от длины стро и т.п. нужный алгоритм
                                  вот memset же использует sse2
                                  а если в процессоре нет sse2 очевидно что memset не упадет :)
                                    0
                                    В зависимости от архитектуры проще — можно выбрать при запуске программы. В зависимости от длины — замедление потенциально видимое на очень коротких строках.
                        0
                        Думаю, нужно еще рассмотреть алгоритм Ахо-Корасика и Укконена — там, где применяется бор. В интернете очень сложно найти их хорошее описание с доказательством работы.
                          +6
                          В описании алгоритма Кнутта-Морриса-Пратта отстутсвует упоминание о префикс-функции (которая вычисляет, насколько нужно сдвинуть курсор поиска). Контр-пример для вашего описания:

                          ABABABCABABAB
                          ABABC
                            0
                            Пожалуй, имеет смысл упомянуть об http://volnitsky.com/project/str_search/. Автор утверждает, что создал самый быстрый среди существующих алгоритм поиска подстроки в строке.
                            • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Большой список алгоритмов поиска подстроки algolist.ru/search/esearch/index.php
                                0
                                <картинка про жпег и пнг />
                                  +1
                                  Есть же метод поиска подстроки в строке при помощи конечного автомата.
                                  Там, безусловно, тратится время и память на построение непосредственно автомата, если мне не изменяет память надо М*М операций (М — длина искомой строки), после чего поиск происходит линейно.
                                  Т.е. общая сложность, если не считать дополнительные расходы по памяти, получается М*М + N.

                                  Вроде регэкспы работают именно так?

                                  Как я помню, это очень выгодный вариант поиска в двух случаях:

                                  1. М << N.
                                  2. Он легко адаптируется к поиску К подстрок в строке N, почти без дополнительных телодвижений (усложняется лишь этап построения автомата).

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

                                  Самому пришлось как-то искать порядка 50ти фиксированных и известных заранее подстрок в большом потоке, и именно это решение для меня оказалось оптимальным, т.к. однажды просчитав автомат я его сохранил для дальнейшего использования.
                                    0
                                    еще наверное актуально написать про Z-функцию
                                      0
                                      суфиксные деревья — поиск самый быстрый
                                      www.youtube.com/watch?v=q9bPAVSmzfA

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

                                      Самое читаемое