Лекція №13
З курсу: «Застосування засобів ООП в лінгвістичних задачах»
11. Алгоритми пошуку в тексті.

11.1. Простий алгоритм Пошуку в тексті
(Задача точного пошуку)

Першим з таких завдань буде завдання про пошук з точним збігом. Це
завдання вирішується, наприклад, в текстовому редакторові, коли
користувач розшукує в редагованому тексті зразок, але практичне її
використання даним прикладом не обмежується. Тому в науковій літературі
завданню про пошук приділяється дуже велика увага.
Найпростішим алгоритмом пошуку підстрічки в стрічці можна вважати
наступний (псевдокод на Pascal):
{пошук всіх входжень підстрічки P в стрічку T}
<Ввести значення стрічки T і підстрічки P>
n := length(t);
m := length(p);
for s := 0 to n - m do
begin
j := 1;
while ( j<=m ) and ( p[j] = t[j+s] ) do
inc(j);
if j > m then
writeln(s); {рядок Р входить в T із зсувом s}
end;
Цей алгоритм хоч і правильний, але дуже неефективний. Складність
цього алгоритму у найгіршому випадку – O(m(n-m+1)). Ми розглянемо
клас алгоритмів швидкого пошуку підстрічок, що мають істотно менший
порядок складності. Всі реалізації алгоритмів приводитимемо на мові
Pascal.

Почнемо з визначень. Задача пошуку підстрічок полягає в
наступному: існує деякий текст T[1..n] і текст який треба знайти P[1..m]
(m.n). Потрібно знайти всі входження тексту P в текст Т. Текст який треба
знайти далі будемо називати «зразком». Будемо казати, що зразок P
входить в T з зсувом s (або те ж саме, що s – допустимий зсув), якщо
P[1..m] = T[s+1...s+m] (0 . s . n-m). У задачі потрібно знайти всі
допустимі зсуви s. Робота простого алгоритму, код якого показано вище,
показана на мал. 1.
Малюнок 1.
Зразок P «рухається» вправо зовнішнім циклом по s. Далі, циклом по
j порівнюється кожна буква зразка P з відповідною буквою тексту T. Якщо
j>m, означає повний збіг , і поточне значення s – і є допустимим зсувом.


11.1. Алгоритм Кнута, Моріса і Пратта (КМП).

Цей алгоритм одержав свою назву від імен його авторів. Він
складається з двох етапів: підготовчого (побудови префікс-функції) і
основного (власне пошуку).
Підготовчий етап. Для довільного слова X розглянемо всі його
префікси, що одночасно є його суфіксами, і серед них виберемо
щонайдовший (не рахуючи самого X). Його позначатимемо L(X), і далі в
тексті його називатимемо найбільшим префікс-суфіксом. Наприклад,
L(abcab)= ab, L(cabcabc) = cabc. Через f(X) позначимо довжину
найбільшого префікс-суфікса Х (тобто довжину L(X)). Функцію f(X)

називатимемо префікс-функцією. Наприклад, f(abcab)= 2, тому що
L(abcab) = ab; f(cabcabc) = 4, тому що L(cabcabc) = cabc.
На підготовчому етапі КМП-алгоритму нам треба обчислити значення
f() для всіх префіксів P[1..k] (k=1..M). Відповідь на питання «для чого?»
дамо пізніше. Спершу про те, як це зробити. Дані визначимо так:
const
MAXPLEN = 24;
var
m: integer; { довжина зразка }
p: string; { зразок }
f: array[1..MAXPLEN] of integer; { префікс-функція}
Тут f[k] означатиме f(P[1..K]). Якщо розглянути послідовність слів
X, L(X), L(L(X)), L(L(L(X))), ... то бачимо, що кожен наступний її елемент
буде префікс-суфіксом попереднього, і ця послідовність закінчується
порожнім рядком. Послідовність чисел length(X), f(X), f(f(X)), f(f(f(X))).
(відповідна вищезгаданою) убуває і закінчується нулем. Алгоритм
обчислення f[k] буде наступним. Припустимо, ми вже обчислили f[1], ...,
f[k-1]. На k-м кроці нам треба обчислити f[k].
Малюнок 2.
Розглянемо P[k]. Символи, які ми порівнюватимемо, позначені темно-
сірим кольором (мал. 2). Якщо P[k]= P[f[k-1]+1], то f[k]= f[k-1]+1
(оскільки P[1..f[k-1]] – суфікс P[1..k-1], і отже P[1..f[k-1]+1] – суфікс
P[1..k]). Якщо ж P[k]<> P[f(k-1)+1], то порівнянний P[k] з P[f[f[k-
1]]+1]. Якщо останні рівні, то f[k]= f[f[k-1]]+1. І так далі. Таким чином
ми дійдемо f[k]= f (q)[k-1]+1 (індекс q означає номер ітерації) або до

f[k]=0, якщо не існує префікс-суфікса для слова P[1..k]. Код, що
обчислює f[k], виглядає так:
procedure ComputeF;
var
i, len: integer;
begin
i:=1; f[1]:= 0;
for i:=2 to m do
begin
len := f[i-1];
while (p[len+1]<> p[i]) and (len>0) do
len := f[len];
if p[len+1]= p[i] then
f[i]:= len + 1
else f[i]:= 0;
end;
end;
Основний етап. На цьому етапі ми для кожного T[1..i] шукатимемо
найбільший префікс P[1..k], який є суфіксом T[1..i]. Якщо виявиться, що
k=m, це значити зразок P входить в текст із i-m. Префікс-функція f()
визначає те, де в зразку P повторно зустрічаються префікси. Ця інформація
необхідна для уникнення свідомо неприпустимих зсувів s. Наприклад,
розглянемо пошук зразка P = abcabc в тексті (мал. 3).
Малюнок 3.


Припустимо, перші 5 символів abcab співпали, а шостий – ні. У разі
простого алгоритму пошуку ми б зробили зсув зразка вправо на одну
позицію, але завдяки знайденій функції префікса f() ми можемо
інкрементувати s на величину 5 – f[5]= 3, не опасаючись, що пропустимо
допустимий зсув. Проте в алгоритмі зручніше оперувати не зсувом s, а
поточним значенням найбільшого префікса P[1..len], що є суфіксом
T[1..i]. Код алгоритму виглядає так:
len := 0;
for i := 1 to n do
begin
while (len>0) and (t[i]<>p[len+1]) do len := f[len];
if t[i] = p[len+1] then inc(len);
if len = m then
begin {зразок знайдений}
writeln(fr, i - m); { результат = зміщення i - m}
{ штучно зменьшуєм len, так як співпадіння довжини len+1 не
може бути, але при читанні наступного символа можуть
співпасти f[len]+1 символів }
len := f[len];
end;
end;

Тут len – поточне значення найбільшого префікса зразка P,
що є кінцем прочитаної частини T. На кожному кроці ми читаємо один
символ (цикл по i). Далі, порівнюємо його з P[f[i-1]+1], P[f[f[i-1]]+1] ...
і т.д., поки не знайдемо той префікс, який буде суфіксом T[1..i]. Якщо
довжина цього префікса – m (len=m), означає, ми знайшли входження
зразка. Повний початковий код – файл KMP.dpr.

{$APPTYPE CONSOLE}
program KMP;
const
MAXPLEN = 24;
var
fp, fr: textfile; ft: file; {файлові змінні для зразка, текста та результату}
p: string; {зразок який шукаємо}
m: integer; {довжина зразка}
n: integer; {довжина тексту}
t: array[1..1048576+1] of char; {частина тексту що зчитується}
f: array[1..MAXPLEN] of integer; {префікс-функція}
c: char; {поточний символ}
len: integer; {поточне значення найбільшого префіксу}
blockReadSize: integer; {зчитаних байт в блоці}
i: integer;
{обчислення префікс-функції}
procedure ComputeF;
var
i, len: integer;
begin
i:=1; f[1] := 0;
for i:=2 to m do
begin
len := f[i-1];
while (p[len+1] <> p[i]) and (len>0) do

len := f[len];
if p[len+1] = p[i] then
f[i] := len + 1
else f[i] := 0;
end;
end;
begin
assignfile(fp, 'p.txt'); reset(fp); {відкриваємо всі файли}
assignfile(ft, 't.txt'); reset(ft, 1);
assignfile(fr, 'KMP.out'); rewrite(fr);
readln(fp, p); m := length(p); {зчитуємо зразок}
n := FileSize(ft); blockread(ft, t, n);
ComputeF; {обчислюємо префікс-функцію}
len := 0;
for i := 1 to n do
begin
while (len>0) and (t[i]<>p[len+1]) do len := f[len];
if t[i] = p[len+1] then inc(len);
if len = m then
begin {зразок знайдений}
writeln(fr, i - m); {результат = зміщення i - m}
{ штучно зменьшуємо len, у зв’язку з тим що співпадіння довжени
len+1 не може бути, але при читанні наступного символу можут співпасти
f[len]+1 символів }
len := f[len];
end;

end;
closefile(fp); closefile(ft); closefile(fr);
end.

11.1.2. Аналіз КМП-алгоритму.

Складність підготовчого етапу алгоритму – O(m). Цей висновок
можна зробити з наступного міркування:
f[i]<= f[i-1] – (число операцій на i-му кроці) + 1
(тому що кожна ітерація while зменшує len як мінімум на 1). Склавши
всі такі нерівності по i = 2..m, отримаємо, що спільне число операцій не
більше сm, де с – деяка константа. До того ж результату можна було
прийти через амортизаційний аналіз (метод потенціалів), взявши за
потенціал значення len при вході в цикл, і озброївшись фактом, що
вартість роботи циклу while компенсується зменшенням потенціалу як
мінімум на кількість ітерацій while. Таким чином, облікова вартість i-й
ітерації for не перевершує О(1).
Застосувавши аналогічні міркування до основного етапу, отримаємо,
що загальна складність алгоритму рівна O(m+n), що набагато менше, ніж
O(m(n-m+1)), як у разі найпростішого алгоритму. Кількість пам'яті,
необхідне для алгоритму – O(m) (для запам'ятовування функції префікса).
Відмітимо ще одну важливу деталь: на кожному кроці ми аналізуємо
черговий символ тексту T[i] і більше не повертаємося до попередніх
символів T. Це дає дуже велику перевагу в порівнянні з іншими
алгоритмами: ми можемо застосовувати КМП для пошуку підрядка у файлі,

причому зовсім не обов'язково читати його в пам'ять цілком: можна
зробити зчитування блоками, як це і реалізовано Automat_buffer.dpr.
11.2. Пошук підстрічок за допомогою скінченних автоматів.

Алгоритм також складається з двох етапів: побудова автомата за
зразком P і посимвольної обробки тексту T автоматом. Почнемо з
визначень. У загальному випадку скінченним автоматом називається об'єкт
M = (Q, q0, A, ., .), де Q –скінченна безліч станів, q0 – початковий стан, А
– безліч допускаючих станів, . – алфавіт символів, – функція переходів.
Пояснимо ці терміни на прикладі стрічки ababaca m=6 (приклад на рис.4
узята з книги Т. Кормен, Ч. Лейзерсон, Р. Рівест «Алгоритми. Побудова і
аналіз»).
Малюнок 4. Скінчений автомат для зразка «ababaca»
Стани Q позначені колами q0 = 0 – початковий стан A= {m} –
допустимий стан, . задана дугами: .(q,x) то стан, в який перейде автомат
після зчитування(прочитування) символа знаходиться перед цим в стані q.
Припустимо, автомат у нас вже є (його побудову розглянемо пізніше).
Входження P в текст T шукатимемо таким чином. Автомат, знаходячись в
одному з своїх станів Q і отримавши на вхід черговий символ T[i],
переходить в інший стан згідно функції .. Якщо автомат опинився в одному
з допускаючих станів A (стані m=6 для нашего прикладу), то ми знайшли

допустимий зсув (i-m). Реалізація виглядає так (з врахуванням
прочитування тексту з файлу по частинам):
var
automat: array[0..MAXPLEN { стан}, char{ символ}] of integer{ стан};
begin
...
{ знаходимо всі вхождения зразка}
i:= 0; { порядковий номер прочитуваного символу}
state:= 0; { початкове стан}
while not eof(ft) do {ft: file of char}
begin
blockread(ft, t, BLOCKSIZE, blockReadSize); { чергова порція тексту}
forj := 1 to blockReadSize do
begin
inc(i);
state := automat[state, t[j]]; {перехід}
if state = m then { якщо попали в допускаючий стан}
writeln(fr,i-m); { означає знайшли входження зразка}
end;
end;

Як бачимо, алгоритм працює за O(n) кроків (О(1) операцій для
кожного символу T[i]). Залишається лише побудувати автомат для зразка.
Для того, щоб зрозуміти, як будується автомат, слід з'ясувати зміст
поняття «стан». Під станом мається на увазі довжина найбільшого
префікса зразка P, який є кінцем прочитаної частини тексту T. У
автомата є лише один допускаючий стан – m, оскільки «префікс P довжини
m, що являється кінцем T[1..n]» – це те ж саме, що «P входить в Т з з
сувом (i-m)».
Поняття «побудова автомата» еквівалентно побудові функції
переходів, задану масивом automat (як показано вище). Відмітимо, що для

побудови автомата не потрібне знати текст T, а досить лише зразка P.
Найпростіший спосіб побудувати автомат виглядає так (псевдокод):
обнулити массив automat
for q= 0 to m do { для всіх станів}
begin
for с := #0 to #255 do {для всіх символів}
begin
до :=min(m+1, q+2);
repeat dec(k)
until(P[1..k] є суффиксом P[1..q] с);
automat[q,c]:= k;
end;
end;

Ми будуємо автомат у відповідності із принципом його роботи: кожен
перехід здійснюється в той стан, який рівний довжині найбільшого
префікса P, що є кінцем прочитаної частини T.
Пояснимо це детальніше. Припустимо, у даний момент часу ми
считали i символiв текста i знаходимося в стані q (що еквівалентно
«P[1..q] є кінцем прочитаної частини T[1..i]»). Прицьому наступний
символ T[i+1] може бути яким завгодно то для всіляких символів с з
множини . нам треба знати наступне: у який стан повинен перейти
автомат після зчитування символу с при умові, що він знаходився в стані
q?. Останне питання еквівалентне наступному: якщо до T[1..i] приписати
символ справа, то який найбільший префікс P буде суфіксом слова
T[1..i]с?. Розглянемо приклад
Поточний крок:
i=12,
P=abcaba
T[1..12]=abcabcabacabca, q= 4
Наступний крок:

i=12,
P=abcaba
T[1..12]=abcabcabacabca*
Если* =a, то
P=abcaba
T[1..12]=abcabcabacabcaa, q=1
Если* = b, то
P=abcaba
T[1..12]=abcabcabacabcab,q=5
...
Наступний після q стан не може бути більшим, ніж q+1 (T[1..i]
закінчувався на P[1..q]= abca, означає T[1..i]с може закінчуватися
максимум на P[1..q+1]=abcab). На підставі цього факту ми робимо
наступний висновок: стан на наступному кроці є довжина найбільшого
префікса P, що є суфіксом P[1..q]с.
З псевдокоду бачимо, що складність алгоритму побудови автомата
складає О(...m3). Однако існує оптимізований метод побудови функції
переходів автомата за час О(m...), що базується на функції префікса f() з
попереднього розділу. Для знаходження найбільшого префікс-суфікса
P[1..q]с нам треба перебирати не всі значення k, а лише ті, які належать
послідовності f[q],f[f[q]], ... 0. І як тільки для деякого wP[fw(q)+1]=c,
так відразу automat[q,c]: =fw(q)+1. Код побудови автомата виглядатиме
так:

Procedure ComputeAutomat;
var q, len: integer;
c: char;
begin
fillchar(automat, sizeof(automat), 0);
automat[0, p[1]]:= 1;
{ переходи для всіх станів, окрім останнього}
for q:=1 to m-1 do
for c := #0 to #255 do
begin
len := q;
while (p[len+1]<>c) and (len>0) do
len := f[len];
if p[len+1]= c then
automat[q, c]:= len+1
else automat[q, c]:= 0;
end;
{ переходи для останнього стану}
for c := #0 to #255 do
begin
len:= f[m];
while (p[len+1]<>c) and (len>0) do
len := f[len];
ifp[len+1]= c then
automat[m, c]:= len+1
else automat[m, c]:= 0;
end;
end;

Окремий випадок з переходом для останнього стану виділений у
зв'язку з тим, що попадання в останній стан вже еквівалентно
знаходженню допустимого зсуву і немає стану з більшим номером, ніж m.
Повна реалізація алгоритму –файл Automat1.dpr.


{$APPTYPE CONSOLE}
program Automat1;
const
MAXPLEN = 24;
var
p: string; {зразок для пошуку}
m: integer; {довжина зразка}
t: array[1..1048576+1] of char; {текст}
f: array[1..MAXPLEN] of integer; {префікс-функція}
automat: array[0..MAXPLEN, char] of integer; {функція переходів}
{робочі змінні}
fp, fr: textfile; ft: file; {файлові змінні для зразка, тексту і результату}
c: char; {текучий символ}
state: integer; {текучий стан автомату}
blockReadSize: integer;{зчитаних байт в блоці}
i, n: integer;
{обчислення префікс-функції}
procedure Computef;
var
i, len: integer;
begin
i:=1; f[1] := 0;
for i:=1 to m-1 do
begin
len := f[i];
while (p[len+1] <> p[i+1]) and (len>0) do
len := f[len];
if p[len+1] = p[i+1] then
f[i+1] := len + 1
else f[i+1] := 0;
end;
end;

{обчислення функції переходів автомату}
procedure ComputeAutomat;
var q, len: integer; c: char;
begin
fillchar(automat, sizeof(automat), 0);
automat[0, p[1]] := 1;
{переходи для всіх станів, окрім останнього}
for q:=1 to m-1 do
for c := #0 to #255 do
begin
len := q;
while (p[len+1] <> c) and (len>0) do
len := f[len];
if p[len+1] = c then
automat[q, c] := len+1
else automat[q, c] := 0;
end;
{переходи для останнього стану}
for c := #0 to #255 do
begin
len := f[m];
while (p[len+1] <> c) and (len>0) do
len := f[len];
if p[len+1] = c then
automat[m, c] := len+1
else automat[m, c] := 0;
end;
end;
begin
assignfile(fp, 'p.txt');
reset(fp);
assignfile(ft, 't.txt');
reset(ft, 1); {відкриття всіх файлів}
assignfile(fr, 'automat.out');
rewrite(fr);

readln(fp, p);
m := length(p); {зчитування зразка}
n := FileSize(ft); blockread(ft, t, n);
Computef; {обчислення префікс-функції}
ComputeAutomat; {будуємо атвомат}
{знаходимо всі входження зразка}
i := 0; {порядковий номер зчитуваємого символа}
state := 0; {текучий стан}
for i := 1 to n do
begin
state := automat[state, t[i]]; {перехді в новий стан}
if state = m then {якщо стан допустимий,}
writeln(fr, i - m); {значить знайшли входження}
end;
closefile(fp);
closefile(ft);
closefile(fr);
end.

11.4. Аналіз алгоритму пошуку підрядків за допомогою
скінчених автоматів

Загальна складність алгоритму складається з складності побудови
префікс-функції O(m), складності побудови функції переходів O(m...) і
складності обробки тексту автоматом O(n). Отже, сумарна складність –
O(...m+n). В порівнянні з КМП цей алгоритм на перший погляд здається
менш ефективним із-за ...m. Але сдругой сторони, якщо текст – дуже
великий, то константа ... при m не відіграє такої ролі, як та константа с
при n, що виходить засчет внутрішнього while - циклу в основній частині
KMП-алгоритму. Об'єм необхідної пам'яті для алгоритму – O((... +1)m).
Як і в КМП, позитивною властивістю є необхідність розглядати тільки
подальший символ тексту T[i], що дає можливість робити пошук як в

пам'яті, так і у файлі з використанням буферизированного вводу
(Automat_buffer.dpr). У алгоритму є і негативна властивість: у разі юникода
для побудови автомата буде потрібно на порядок більше пам'яті і часу для
обчислення функції переходів.

{$APPTYPE CONSOLE}
program Automat_buffer;
const
MAXPLEN = 24;
BLOCKSIZE = 1024; {розмір блока текста що зчитувається }
var
p: string; {зразок який щукаємо}
m: integer; {довжина зразка}
t: array[1..BLOCKSIZE] of char; {частина тексту який зчитувається}
f: array[1..MAXPLEN] of integer; {префікс-функція}
automat: array[0..MAXPLEN, char] of integer;
{робочі змінні}
fp, fr: textfile; ft: file; {файлові змінні для зразка, тексту і результат}
c: char; {текучий символ}
state: integer; {текуий стан автомата}
blockReadSize: integer;{кількість зчитаних байт в блоці}
i, j: integer;
{обчислення префікс-функціі}
procedure ComputeF;
var
i, len: integer;
begin
i:=1; f[1] := 0;
for i:=2 to m do
begin
len := f[i-1];
while (p[len+1] <> p[i]) and (len>0) do
len := f[len];
if p[len+1] = p[i] then
f[i] := len + 1
else f[i] := 0;
end;
end;
{обчислення функції переходів автомата}
procedure ComputeAutomat;
var i, len: integer;
c: char;
begin
fillchar(automat, sizeof(automat), 0);

automat[0, p[1]] := 1;
{переходи для всех станів, крім останнього}
for i:=1 to m-1 do
for c := #0 to #255 do
begin
len := i;
while (p[len+1] <> c) and (len>0) do
len := f[len];
if p[len+1] = c then
automat[i, c] := len+1
else automat[i, c] := 0;
end;
{переходи для останнього стану}
for c := #0 to #255 do
begin
len := f[m];
while (p[len+1] <> c) and (len>0) do
len := f[len];
if p[len+1] = c then
automat[m, c] := len+1
else automat[m, c] := 0;
end;
end;
begin
assignfile(ft, 't.txt'); reset(ft, 1); {відкриваємо всі файли}
assignfile(fp, 'p.txt'); reset(fp);
assignfile(fr, 'automat_buffer.out'); rewrite(fr);
readln(fp, p); m := length(p); {зчитування зразка}
Computef; {обчислення префікс-функції}
ComputeAutomat; {будуємо атвомат}
{знаходимо всі входження зразка}
i := 0; {порядковий номер зчитуваного символа}
state := 0; {текучий стан}
while not eof(ft) do
begin
blockread(ft, t, BLOCKSIZE, blockReadSize); {наступна частина тексту}
for j := 1 to blockReadSize do

begin
inc(i);
state := automat[state, t[j]]; {перехід в новий стан}
if state = m then {якщо стан допускаючий,}
writeln(fr, i - m); {значить знайшли входження}
end;
end ;
closefile(fp); closefile(ft); closefile(fr);
end.