Простейший алгоритм
Суть метода, о котором пойдет речь ниже, заключается в следующем: мы проверяем, совпадают ли m символов текста (начиная с выбранного) с символами нашей строки, пытаясь примерить шаблон куда только возможно. Естественно, реализовать описанный алгоритм проще всего (код на языке Pascal):
Program SimpleSearch;
Var T: array[1..40000] of char; {выполняет роль текста}
S: array[1..10000] of char; {выполняет роль строки; как и текст, может быть достаточно велика}
i,j: longint;
m,n: longint;
Begin
{Ввод текста и образца}
…
for i:=1 to n-m+1 do
begin
j:=0;
while (j<m) and (S[j+1]=T[i+j]) do {По очереди сравниваем все символы начиная с i-ого}
j:=j+1;
if j=m then {если все символы совпадали}
writeln('Образец входит в текст начиная с ',i,'-ого символа'); {сообщение о нахождении строки в тексте}
end;
End.
Просто и элегантно, вроде так и надо. Действительно, это несложно в исполнении, но и не очень эффективно на практике. Давайте оценим скорость работы этой программки. В ней присутствуют два цикла (один вложенный), время работы внешнего большей степенью зависит от n, а внутренний в худшем случае делает m операций. Таким образом, время работы всего алгоритма есть O((n-m+1)m). Для маленьких строк поиск проработает быстро, но если в каком-то многомегабайтном файле вы будете искать последовательность длинной 100 Кб, то, боюсь, придется вам ждать ну очень долго. Впрочем, как я уже говорил, многим хватает и этого.
Как вы уже, наверное, поняли, основной недостаток вышеизложенного метода состоит в том, что приходится выполнять много лишней работы. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату. Следующий метод работает намного быстрее простейшего, но, к сожалению, накладывает некоторые ограничения на текст и искомую строку.
Алгоритм Рабина-Карпа
Идея, предложенная Рабином и Карпом, подразумевает поставить в соответствие каждой строке некоторое уникальное число, и вместо того чтобы сравнивать сами строки, сравнивать числа, что намного быстрее. Проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка Dm, где D - количество различных символов), и работать с ними будет так же неудобно. Ниже вы узнаете, как найти выход из этого положения, а пока смотрите реализацию для текста, состоящего только из цифр, и строки длиной до 8 символов.
Program RabinKarpSearch;
Var T: array[1..40000] of 0..9;
S: array[1..8] of 0..9;
i,j: longint;
n,m: longint;
v,w: longint; {v - число, характеризующее искомую строку, w характеризует строку длинны m в тексте}
k: longint;
const D: longint = 10; {количество разных символов (10 различных цифр)}
Begin
{Ввод текста и образца}
…
v:=0;
w:=0;
for i:=1 to m do
begin
v:=v*D+S[i]; {вычисление v, строка представляется как число}
w:=w*D+T[i]; {вычисление начального значения w}
end;
k:=1;
for i:=1 to m-1 do {k нужно для многократного вычисления w и имеет значение Dm-1}
k:=k*D;
for i:=m+1 to n+1 do
begin
if w=v then {если числа равны, то строки совпадают, а значит, образец найден в тексте}
writeln('Образец входит в текст начиная с ',i-m,'-ого символа');
if i<=n then
w:=d*(w-k*T[i-m])+T[i]; {вычисление нового значения w}
end;
End.
Этот алгоритм выполняет линейный проход по строке (m шагов) и линейный проход по всему тексту (n шагов), стало быть, общее время работы есть O(n+m). Это время линейно зависит от размера строки и текста, стало быть программа работает быстро. Но какой интерес работать только с короткими строками и цифрами? Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы. Как вы заметили, мы ставили в соответствие строке ее числовое представление, но возникала проблема больших чисел. Ее можно избежать, если производить все арифметические действия по модулю какого-то простого числа (постоянно брать остаток от деления на это число). Таким образом, находится не само число, характеризующие строку, а его остаток от деления на некое простое число. Теперь мы ставим число в соответствие не одной строке, а целому классу, но так как классов будет довольно много (столько, сколько различных остатков от деления на это простое число), то дополнительную проверку придется производить редко.
Var T: array[1..40000] of char;
S: array[1..10000] of char;
i,j: longint;
n,m: longint;
v,w: longint;
k: longint;
const P: longint = 7919; {1000-е простое число}
D: longint = 256; {количество разных символов (количество всех возможных значений символьного типа char)}
Begin
{Ввод текста и образца}
…
v:=0;
w:=0;
for i:=1 to m do {вычисление v и w}
begin
v:=(v*D+ord(S[i])) mod P; {ord преобразует символ в число}
w:=(w*D+ord(T[i])) mod P;
end;
k:=1;
for i:=1 to m-1 do
k:=k*D mod P; {k имеет значение Dm-1 mod P}
for i:=m+1 to n+1 do
begin
if w=v then {если числа равны, то строки принадлежат одному классу, и надо проверить совпадают ли они}
begin
j:=0;
while (j<m) and (S[j+1]=T[i-m+j]) do
j:=j+1;
if j=m then {окончательная проверка}
writeln('Образец входит в текст начиная с ',i-m,'-ого символа');
end;
if i<=n then
w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;
end;
End.
Итак, нам все-таки приходится производить сравнение строк посимвольно, но так как «холостых» срабатываний будет немного (в 1/P случаях), то ожидаемое время работы малое. Строго говоря, время работы есть O(m+n+mn/P), mn/P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа. Этот алгоритм значительно быстрее предыдущего и вполне подходит для работы с очень длинными строками.
Еще один важный метод, о котором я хочу рассказать, - алгоритм Кнута-Морриса-Пратта, один из лучших на нынешний момент, работает за линейное время для любого текста и любой строки.
Алгоритм Кнута-Морриса-Пратта
Метод использует предобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки S[1..i] строки S наибольшей подстроки S[1..j] (j<i), присутствующей одновременно и в начале, и в конце подстроки (как префикс и как суффикс). Например, для подстроки abcHelloabc такой подстрокой является abc (одновременно и префиксом, и суффиксом). Смысл префикс-функции в том, что мы можем отбросить заведомо неверные варианты, т.е. если при поиске совпала подстрока abcHelloabc (следующий символ не совпал), то нам имеет смысл продолжать проверку продолжить поиск уже с четвертого символа (первые три и так совпадут). Вот как можно вычислить эту функцию для всех значений параметра от 1 до m:
…
var S: array[1..10000] of char;
P: array[1..10000] of word; {массив, в котором хранятся значения префикс-функции}
i,k: longint;
m: longint;
…
Procedure Prefix; {процедура, вычисляющая префикс-функцию}
Begin
P[1]:=0; {префикс строки из одного символа имеет нулевую длину}
k:=0;
for i:=2 to m do {вычисляется для префиксов строки длинной от 2 до m символов}
begin
while (k>0) and (S[k+1]<>S[i]) do
k:=P[k]; {значение функции может быть получено из ранее сделанных вычислений}
if S[k+1]=S[i] then
k:=k+1;
P[i]:=k; {присвоение префикс-функции}
end;
End;
…
Теперь разберемся, почему же данная процедура вычисляет префикс-функцию правильно. Используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Так как в цикле while она уменьшается (P[k]<k), но не становится меньше 0, то уменьшаться она может не чаще, чем возрастать. Переменная k возрастает на 1 не более m раз. Значит, переменная k меняется всего не более 2m раз. Выходит, что время работы всей процедуры есть O(m). А сейчас мы переходим к самой программе, ищущей строку в тексте.
Program KnutMorrisPrattSearch;
…
{Описание процедуры Prefix и связанных с нею переменных}
…
var n: longint;
T: array[1..40000] of char;
Begin
{Ввод текста и образца}
…
Prefix; {Вычисление префикс-функции}
k:=0; {количество символов, совпавших на данный момент}
for i:=1 to n do
begin
while (k>0) and (S[k+1]<>T[i]) do
k:=P[k];
if S[k+1]=T[i] then
k:=k+1;
if k=m then {если совпали все символы}
begin
writeln('Образец входит в текст начиная с ',i-m+1,'-ого символа');
k:=P[k];
end;
end;
End.
Доказать что эта программа работает за линейное время, можно точно так же, как и для процедуры Prefix. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.
Напоследок хочу заметить, что простейший алгоритм и алгоритм Кнута-Морриса-Пратта помимо нахождения самих строк считают, сколько символов совпало в процессе работы. И еще: алгоритм Кнута-Морриса-Пратта немногим более громоздок, чем простейший, зато работает намного быстрее. Так что делайте выводы.
P.S. Все программы проверены на работоспособность, достаточно вставить соответствующие сегменты кода вместо многоточий.
Читайте также:
Описание алгоритмов сортировки, часть 1
Описание алгоритмов сортировки, часть 2
Алгоритмы поиска данных
Автор: Владимир Ткачук - mycоmр.cоm.uа
