Сторінка
1
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], тобто без повернення назад у рядку 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[i-1], а x[j+1] не збігається з черговим символом рядка s[i]. У такому разі треба відшукати такий найдовший початок x[1]…x[k] зразка, що водночас є кінцем підрядка x[1]…x[j]. Він є також і кінцем підрядка s[1]…s[i-1]! Перехід від перевіреного початку зразка довжини j до перевіреного початку довжини k означає зсув зразка відносно рядка s одразу на j-k позицій. Але на меншу кількість позицій зсувати зразок немає сенсу, оскільки x[1]…x[k] – це найдовший початок зразка, що збігається з кінцем підрядка s[1]…s[i-1]. Якщо x[k+1]=s[i], то можна продовжувати порівняння від символу s[i+1]. Якщо x[k+1]¹ s[i], то треба відшукати найдовший початок x[1]…x[k1] зразка, що збігається з кінцем x[1]…x[k] (і з кінцем s[1]…s[i-1]), і порівняти 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[i-1], тобто назад від позиції s[i] в рядку можна не повертатися. Отже, якщо для кожної позиції j зразка відома найбільша довжина f(j)<j такого початку зразка x[1]…x[f(j)], що збігається з кінцем x[1]…x[j], то перше входження зразка знаходиться без повернень у рядку s. Для визначення можливого початку наступного входження треба знати лише f(n) і продовжувати пошук знову-таки без повернень у рядку! Саме відсутність повернень у рядку дозволяє оцінити загальну кількість порівнянь як O(m+n), що суттєво менше, ніж O(m´ n). Ми доведемо це далі. Функція f(j), що виражає довжину такого найдовшого початку рядка x[1]…x[j], що є водночас його кінцем, називається функцією відступів. Вона показує, до якого символу x[f(j)] треба відступити в зразку, коли x[j+1] не збігається з черговим символом рядка, щоб продовжувати пошук із порівняння чергового символу з символом x[f(j)+1]. Цей відступ рівносильний зсуву рядка на найменшу можливу кількість позицій j-f(j). Займемося тепер обчисленням цієї функції за зразком. Очевидно, f(1)=0. Нехай всі значення f(1), … , f(j-1) уже обчислено, причому f(j-1)=k. Якщо x[j]=x[k+1], то кінець рядка x[1]…x[j-1]x[j] збігається з його ж початком довжини k+1, тому f(j)=k+1. Якщо x[j]¹ x[k+1], то "наступним кандидатом у кінці" рядка x[1]…x[j-1]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[j-1]; while (x[j] <> x[k+1]) and (k>0) 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[j-1]-w(j)+1, тобто w(j)<=f[j-1]-f[j]+1. Тоді w(2)+w(3)+…+w(n) £ f[1]-f[2]+1+f[2]-f[3]+1+…+f[n-1]-f[n]+1 =
Завантажити реферат