ПОШУК ЗРАЗКА В РЯДКУ
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.
ДОДАТОК
Службові слова стандарту мови Паскаль
And
|
False
|
Mod
|
Set
|
Array
|
File
|
Nil
|
Then
|
Begin
|
For
|
Not
|
To
|
Case
|
Forward
|
Of
|
True
|
Const
|
Function
|
Or
|
Type
|
Div
|
Goto
|
Packed
|
Until
|
Do
|
If
|
Procedure
|
Var
|
Downto
|
In
|
Program
|
While
|
Else
|
Label
|
Record
|
With
|
End
|
Maxint
|
Repeat
| |
Додаткові слова в Турбо Паскаль
Absolute
|
Implementation
|
Object
|
Unit
|
Constructor
|
Inline
|
Shl
|
Uses
|
Destructor
|
Interface
|
Shr
|
Virtual
|
External
|
Interrupt
|
String
|
Xor
|