Реферат з програмування:
Пошук зразка в рядку
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 m-n+1 do
if copy(s, k, n)=x then writeln(k).
Нагадаємо, що з виклику copy(s, 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 підказує, що зразок не може починатися в рядку з позиції 5-3=2. Отже, за s[n]? x[n] можна перейти одразу до порівняння x[n] із s[n+(n-p[s[n]])].
Якщо s[n]=x[n], то можна порівняти попередні символи рядка з відповідними символами зразка, рухаючися від його кінця до початку. Якщо всі відповідні символи рівні, то зразок є підрядком, що починається з першої позиції рядка. Після цього можна переходити до аналізу другої позиції s, порівнюючи x[n] із s[n+1].
Якщо за деякого k>0 s[k]? x[k], то серед x[k-1], … , 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+(n-p[s[n]])
else
begin
k:=n-1; ok:=true;
while (k>0) and ok do
if x[k]=s[last-n+k] then k:=k-1 else ok:=false;
if k=0 then {s[last-n+1]…s[last]=x}
begin
повідомити про те, що з last-n+1 починається зразок;
last:=last+1
end else
begin
відшукати серед x[1]…x[k-1] найближчий до x[k]
символ x[j], рівний s[last-n+k]; якщо такого немає, то j:=0
last:=last+(k-j)
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[j-1]=x[j-1], 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], тобто