В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке.
Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска.
По традиции шаблон поиска или образец обычно обозначают иглой (англ.
«игла»), а линию, в которой ведется поиск, называют стогом сена (англ.
«haystack»).
В Python примитивный алгоритм выглядит так:
Обозначим n=|стог сена|, m=|игола|.index = -1 for i in xrange(len(haystack)-len(needle)+1): success = True for j in xrange(len(needle)): if needle[j]<>haystack[i+j]: success = False break if success: index = i break print index
Самый простой алгоритм поиска, даже в лучшем случае, выполняет n–m+1 сравнений; если имеется много частичных совпадений, скорость снижается до O(n*m).
Хотя рассматриваемый ниже алгоритм имеет низкую скорость на «хороших» данных, это компенсируется отсутствием регрессии на «плохих» данных.
Алгоритм Кнута-Морриса-Пратта — один из первых алгоритмов с линейной оценкой наихудшего случая.
Прежде чем перейти к описанию алгоритма, необходимо рассмотреть понятие префиксной функции.
Строковая префиксная функция π(S,i) — это длина наибольшего префикса строки S[1.i], который не совпадает с этой строкой и одновременно является ее суффиксом.
Проще говоря, это длина самого длинного начала строки, которое одновременно является ее концом.
Для строки S удобно представить префиксную функцию в виде вектора длины |S|-1. Мы можем рассмотреть префиксную функцию длины |S| установив π(S,1)=0. Пример префиксной функции для строки «abcdabcabcdabcdab»:
| С [я] | а | б | с | д | а | б | с | а | б | с | д | а | б | с | д | а | б |
| π(S,i) | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 4 | 5 | 6 |
- Если S[i+1]=S[k+1], то π(S,i+1)=k+1.
- S[1.π(S,k)] — суффикс строки S[1.i].
Действительно, если строка S[1.i] заканчивается строкой S[1. π(S,i)]=S[1.k], а строка S[1.k] заканчивается строкой строку S[1.π (S,k)], то строка S[1.i] заканчивается строкой S[1.π(S,k)].
- ∀ jε(k,i), S[1.j] не является суффиксом строки S[1.i].
В противном случае предположение π(S,i)=k было бы неверным, поскольку j> k.
Пусть π(S,i)=k. Необходимо вычислить π(S,i+1).
- Если S[i+1]=S[k+1], то π(S,i+1)=k+1.
- В противном случае, если k=0, то π(S,i+1)=0.
- В противном случае установите k:=π(S,k) и перейдите к шагу 1.
Алгоритм вычисления префиксной функции в Python: def prefix(s):
v = [0]*len(s)
for i in xrange(1,len(s)):
k = v[i-1]
while k > 0 and s[k] <> s[i]:
k = v[k-1]
if s[k] == s[i]:
k = k + 1
v[i] = k
return v
Покажем, что время работы алгоритма равно O(n), где n=|S|.
Обратите внимание, что асимптотическое поведение алгоритма определяется общим количеством итераций цикла while. Это верно, поскольку без цикла while каждая итерация цикла for выполняется менее чем за постоянное время.
На каждой итерации цикла for k увеличивается не более чем на единицу, что означает максимально возможное значение k=n–1. Поскольку значение k уменьшается только внутри цикла while, то получается, что суммарно k нельзя уменьшить более чем в n–1 раз.
Это означает, что цикл while в конечном итоге будет выполнен не более n раз, что дает окончательную оценку времени работы алгоритма O(n).
Рассмотрим алгоритм Кнута-Морриса-Пратта, основанный на использовании префиксной функции.
Как и в алгоритме примитивной подстроки, шаблон «перемещается» по строке слева направо, чтобы найти совпадение.
Однако ключевое отличие состоит в том, что с помощью префиксной функции мы можем избежать заведомо бесполезных сдвигов.
Пусть S[0.m–1] – выборка, T[0.n–1] – строка, в которой осуществляется поиск.
Рассмотрим сравнение строк в позиции i, то есть образец S[0.m–1] сравнивается с частью строки T[i.i+m–1].
Предположим, что первое несовпадение произошло между символами S[j] и T[i+j], где i < j < m. Let us denote P = S[0.j–1] = T[i.i+j–1].
When shifting, we can expect that the prefix S will converge with some suffix of the string P. Since the length of the longest prefix, which is also a suffix, is the prefix function of the string S for index j, we arrive at the following algorithm:
- Построим префиксную функцию выборки S, обозначим ее F.
- Установите k = 0, i = 0.
- Сравните символы S[k] и T[i].
Если символы равны, увеличьте k на 1. Если при этом k станет равным длине шаблона, то вхождение шаблона S в строку T найдено, индекс вхождения равен i – |S | + 1. Алгоритм завершается.
Если символы не равны, мы используем префиксную функцию для оптимизации сдвигов.
Пока k > 0, положим k = F[k–1] и перейдем к началу шага 3.
- В то время как я < |T|, increase i by 1 and go to step 3.
def kmp(s,t):
index = -1
f = prefix(s)
k = 0
for i in xrange(len(t)):
while k > 0 and s[k] <> t[i]:
k = f[k-1]
if s[k] == t[i]:
k = k + 1
if k == len(s):
index = i - len(s) + 1
break
return index
Теги: #Алгоритмы #поиск подстроки в строке #Алгоритмы
-
Википедия – 100% Надежный Источник?
19 Oct, 24 -
Intel 8086 — Процессор, Открывший Эпоху
19 Oct, 24 -
Советы По Правильной Настройке Телевизора
19 Oct, 24
