Паскаль. Прикладне програмне забезпечення


Пошук зразка в рядку

1. Оцінка кількості порівнянь

Задача. У рядку відшукати всі позиції, починаючи з яких інший рядок Зразок Входить в рядок, тобто є його підрядком. Наприклад, у рядку

ABRACADABRA

Зразок ABR входить як підрядок з позицій 1 і 8, зразок A – з позицій 1, 4, 6, 8 і 11, а зразок ARA не входить.

Позначимо через S рядок, у якому шукається зразок X. Нехай M і N – довжини рядків S і X. Можна порівняти з X усі підрядки S довжини N, які починаються з позицій 1, 2, , M N+1. У разі рівності друкується відповідна позиція:

For k:=1 To mn+1 Do

If copys, k, n=x Then writelnk.

Нагадаємо, що з виклику copys, k, n повертається підрядок рядка S, що починається в його позиції K та має довжину N. Дуже просто, але дуже нерозумно! Адже загальна кількість порівнянь символів є M N+1 N. Наприклад, за M=255, N=128 порівнянь символів буде 1282=16384, хоча Більшість їх насправді зайва. Ми переконаємося в цьому, розглянувши далі зовсім інші способи пошуку зразка.

Але спочатку оцінимо зверху кількість порівнянь символів. Зафіксуємо довжину рядка M. Нехай довжина зразка N довільна в межах між 1 та M. Тоді M N+1 N M n. Як бачимо, різниця N2 N між M n та M N+1 N мала за значень N, близьких до 1, і велика за N, близьких до M. За малих значень N величиною N2 N можна нехтувати. Таким чином, наша оцінка

M N+1 N = O M n

Є досить точною за малих значень N і грубою – за великих. Припустивши, що зразки з великою довжиною – явище дуже рідкісне, можна вважати цю оцінку цілком прийнятною.

2. Метод БойєраМура спрощений варіант

Один із способів суттєво зменшити кількість порівнянь належить Бойєру та Муру [BoMo]. Розглянемо спрощений варіант їх алгоритму. Нехай символи рядка й зразка належать деякому алфавіту. Нехай зразок X= X[1] X[2] X[ N]. Спочатку для кожного символу Z алфавіту визначається номер позиції P[ Z] його Останньої появи в рядку X. Якщо символ Z відсутній в X, то P[ Z]=0. Наприклад, у зразку 'ababc' P['a']=3, P['b']=4, P['c']=5, а для решти символів Z алфавіту P[ Z]=0.

Обчислення масиву P очевидне:

Для всіх символів Z алфавіту p[ Z]:=0;

For k:=1 To n Do p[ X[k]]:=k.

Інформація про останню появу символів у зразку використовується так. Порівняємо одразу S[ N] та X[ N]. Якщо S[ N] X[ N], то найближчим до кінця зразка символом, якому рівний S[ N], є символ X[ P[ S[ N]]]. Таким чином, можна не порівнювати S[ N] із жодним із символів зразка між X[ P[ S[ N]]] та X[ N]. А це означає, що можна не перевіряти рівність зразка з підрядками, що починаються з позицій 2, 3, , N P[ S[ N]]. Наприклад, якщо X='ababc', а рядок S починається символами aaaba, то P[ S[5]]=3 підказує, що зразок не може починатися в рядку з позиції 53=2. Отже, за S[ N] X[ N] можна перейти одразу до порівняння X[ N] із S[ N+ N P[ S[ N]]].

Якщо S[ N]= X[ N], то можна порівняти попередні символи рядка з відповідними символами зразка, рухаючися від його кінця до початку. Якщо всі відповідні символи рівні, то зразок є підрядком, що починається з першої позиції рядка. Після цього можна переходити до аналізу другої позиції S, порівнюючи X[ N] із S[ N+1].

Якщо за деякого K0 S[ K] X[ K], то серед X[ K1], , X[1] треба відшукати найближчий до X[ K] символ X[ J]= S[ K]. Ця рівність означає, що зразок, можливо, має кінець у рядку в позиції K+ N J, тобто N+ K J. Тоді можна знову починати все з кінця зразка, порівнюючи X[ N] із S[ N+ K J].

Нехай змінна last позначає позицію кінця зразка в рядку S. Спочатку last= N, а його наступним значенням може бути лише, як показує попередній аналіз, або N+1, або N+ N P[ S[ N]], або N+ K J. За будьякого з цих значень змінної last наступним її значенням буде так само або last+1, або last+last P[ S[ N]], або last+ K J. На основі цих міркувань записується такий спрощений варіант алгоритму БойєраМура:

Last:=n;

While last=m Do

If x[n]s[last] Then last:=last+np[s[n]]

Else

Begin

K:=n1; ok:= True;

While k0 And ok Do

If x[k]=s[lastn+k] Then k:=k1 Else ok:= False;

If k=0 Then {s[lastn+1]s[last]= X}

Begin

Повідомити про те, що з lastn+1 починається зразок;

Last:=last+1

End else

Begin

Відшукати серед x[1]x[k1] найближчий до x[k]

Символ x[j], рівний s[lastn+k]; якщо такого немає, то j:=0

Last:=last+kj

End

End.

Зауважимо, що цей спрощений варіант в деяких випадках не рятує від необхідності здійснювати O M n порівнянь символів. Справжній алгоритм БойєраМура забезпечує, що кількість порівнянь символів за будьяких рядків довжини M і N оцінюється як O M+ N, тобто її можна вважати пропорційною сумі довжин рядка й зразка. Ідея цього методу приблизно така сама, як і методу з наступного підрозділу.

3. Метод КнутаМоррісаПратта

Цей метод уперше описано Моррісом і Праттом у [MorPr]. Він наведений також у книзі [АХУ].

Почнемо порівнювати символи зразка X= X[1] X[ N] із символами рядка S= S[1] S[ M] із початку. Нехай S[1]= X[1], , S[ J1]= X[ J1], S[ J] X[ J], де J n. Зрозуміло, що зразок не входить у рядок із першої позиції. Можна, звичайно, спробувати почати перевірку з другої позиції, але зовсім не обов'язково. Наприклад, за зразка X='ababb' й рядка S='ababababbab' після того, як виявилося, що S[5]='a' 'b'= X[5], є сенс починати наступну перевірку лише з S[3], оскільки саме там є входження початку зразка. Символами S[3] S[4]='ab' водночас закінчується й починається частина зразка X[1] X[2] X[3] X[4], і наступне входження зразка можливе, коли X[1] X[2] займуть місце X[3] X[4], тобто зразок зсунеться відносно рядка одразу на дві позиції. Після цього можна продовжити перевірку від символу S[5], тобто Без повернення назад у рядку s.

Далі виявляється S[7] X[5], і зразок можна зсунути одразу на дві позиції, щоб X[1] X[2] знову зайняли місце X[3] X[4], збігаючися при цьому з S[5] S[6]. Тепер S[7]= X[3], S[8]= X[4], S[9]= X[5], і входження починаючи з позиції 5 знайдено.

Отже, нехай перевіряється входження зразка від позиції I J, X[1] X[ J]= S[ I J] S[ I1], а X[ J+1] не збігається з черговим символом рядка S[ I]. У такому разі треба відшукати такий Найдовший початок x[1]x[k] зразка, що водночас є кінцем підрядка x[1]x[j]. Він є також і кінцем підрядка S[1] S[ I1]!

Перехід від перевіреного початку зразка довжини J до перевіреного початку довжини K означає зсув зразка відносно рядка S одразу на J K позицій. Але на меншу кількість позицій зсувати зразок немає сенсу, оскільки X[1] X[ K] – це Найдовший початок зразка, що збігається з кінцем підрядка s[1] S[ I1].

Якщо X[ K+1]= S[ I], то можна продовжувати порівняння від символу S[ I+1]. Якщо X[ K+1] S[ I], то треба відшукати найдовший початок X[1] X[ K1] зразка, що збігається з кінцем X[1] X[ K] і з кінцем S[1] S[ I1], і порівняти X[ K1+1] із S[ I] тощо.

Наприклад, якщо S='abababc', а X='ababc', то при спробі прикласти зразок починаючи з першого символу рядка маємо X[1]= S[1], X[2]= S[2], x[3]= S[3], x[4]= S[4], X[5] S[5], тобто J=4. Відповідним значенням K буде 2, оскільки 'ab' є найдовшим початком рядка 'abab', що є водночас його кінцем. Звідси випливає, що немає сенсу пробувати прикласти зразок до рядка, починаючи з його другої позиції, а слід пересунути його одразу на J K=2 позиції. При цьому гарантується рівність X[1] X[ K] і S[ I K] S[ I1], тобто назад від позиції S[ I] в рядку можна не повертатися.

Отже, Якщо для кожної позиції j зразка відома найбільша довжина fjj такого початку зразка x[1]x[fj], що збігається з кінцем x[1]x[j], то перше входження зразка знаходиться без повернень у рядку s. Для визначення можливого початку наступного входження треба знати лише F N і продовжувати пошук зновутаки без повернень у рядку! Саме Відсутність повернень у рядку дозволяє оцінити загальну кількість порівнянь як Om+n, що суттєво менше, ніж Om n. Ми доведемо це далі.

Функція F J, що виражає довжину такого найдовшого початку рядка X[1] X[ J], що є водночас його кінцем, називається Функцією відступів. Вона показує, до якого символу X[ F J] треба Відступити в зразку, коли X[ J+1] не збігається з черговим символом рядка, щоб продовжувати пошук із порівняння чергового символу з символом X[ F J+1]. Цей відступ рівносильний зсуву рядка на найменшу можливу кількість позицій J F J. Займемося тепер обчисленням цієї функції за зразком.

Очевидно, F1=0. Нехай всі значення F1, , F J1 уже обчислено, причому F J1= K. Якщо X[ J]= X[ K+1], то кінець рядка X[1] X[ J1] X[ J] збігається з його ж початком довжини K+1, тому F J= K+1. Якщо X[ J] X[ K+1], то наступним кандидатом у кінці рядка X[1] X[ J1] X[ J] є рядок X[1] X[ F K] X[ F K+1], оскільки саме X[1] X[ F K] є найдовшим кінцем X[1] X[ K]. Якщо й він не годиться, то наступним є X[1] X[ F F K+1] тощо. Отже, ми або знайдемо початок довжини P, такий, що X[1] X[ P] є кінцем X[1] X[ J], і тоді F J= P, або не знайдемо, і F J=0.

Наведені обчислення описуються таким алгоритмом подамо функцію F масивом:

F[1]:= 0;

For j:= 2 To n Do

Begin

K:= f[j1];

While x[j] x[k+1] And k0 Do

K:= f[k];

If x[j] x[k+1] And k=0 Then f[j]:= 0

Else f[j]:= k+1;

End;

Оцінимо загальну кількість порівнянь символів, виконуваних за цим алгоритмом. Позначимо через W J кількість виконань тіла циклу за відповідного значення J=2, , N. Помітимо, що кожне виконання тіла циклу while зменшує значення K не менше, ніж на 1. Звідси F[ J]= F[ J1] W J+1, тобто W J= F[ J1] F[ J]+1. Тоді

W2+ W3++ W N F[1] F[2]+1+ F[2] F[3]+1++ F[ N1] F[ N]+1 =

= F[1] F[ N]+ N1 N1.

За кожного J порівнянь символів відбувається на 2 більше, ніж виконань тіла циклу – одне додаткове при обчисленні умови в заголовку циклу і одне в умовному операторі. Звідси загальна кількість порівнянь символів не більше 3 N1, тобто прямо пропорційна N. Таким чином, загальну кількість порівнянь символів при побудові функції відступів можна оцінити як O N.

Тепер, нарешті, наведемо алгоритм пошуку входжень зразка в рядок. Нехай T позначає номер поточної позиції в рядку, J – номер поточної позиції в зразку, спочатку вони рівні 1. Далі, поки T m, виконуємо наступні дії. Порівнюємо символи X[ J] і S[ T]. Якщо вони рівні, маємо входження X[1] X[ J] в кінці рядка S[1] S[ T]. Якщо при цьому J= N, то можна повідомити про входження зразка починаючи з позиції T J+1 і приступати до пошуків наступного входження, поклавши J= F N. Якщо ж J N, то переходимо до наступної пари символів, збільшивши T і J на 1. За нерівності S[ T] і X[ J] при J1 міняємо значення J на F[ J1]+1, а при J=1 збільшуємо T на 1. Втім, зміни J не мають сенсу, коли T= M. Ось і все. Наведемо цей алгоритм також і в мові Паскаль:

T:=1; j:=1;

While t=m Do

Begin

If x[j]=s[t] Then

If j=n Then

Begin writelntj+1; j:=f[j] End

Else

Begin t:=t+1; j:=j+1 End

Else { x[j]s[t] }

If tm Then

If j1 Then j:=f[j1]+1 Else t:=t+1

Else t:=t+1

End.

Оцінимо тепер кількість порівнянь символів при виконанні цього алгоритму. Помітимо, що при кожному виконанні тіла циклу збільшується T на 1 або зменшується J принаймні на 1 присвоюванням F[ J] чи F[ J1]+1. Позначимо через B T початкове значення J при черговому значенні T=1, 2, , M, а через W T – кількість зменшень J при відповідному значенні T. Оскільки при збільшенні T значення J або не міняється, або збільшується на 1, то маємо, що B T B T1 W T+1 за T1, звідки W T B T1 B T+1. Тоді

W1+ W2++ W M 1+ B[1] B[2]+1+ B[2] B[3]+1++ B[ M1] B[ M]+1 =

= M+ B[1] B[ M] M+1.

З алгоритму очевидно, що порівнянь символів відбувається рівно стільки, скільки збільшень t та зменшень J разом. Оскільки T збільшується M1 разів, загальна кількість порівнянь символів не більше 2 M, тобто пропорційна M, і оцінюється як O M.

З урахуванням побудови функції відступів загальна кількість порівнянь символів за будьяких рядків довжини M і N оцінюється як O N+ O M, або O M+ N.