Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Лекція
Предмет:
Об’єктно-орієнтоване програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
НУ „Львівська політехніка”
Лекція №1 4
з курсу: «Застосування засобів об’єктно-орієнтованого програмування в лінгвістичних задачах»
Львів - 2010
11.5. Алгоритм Рабина-Карпа (РК).
Якщо два попередні алгоритми схожі, то цей алгоритм, названий на
честь його розробників, працює за іншою схемою. Розглянемо P і T як
великі числа, записані в системі числення d=256. Кожну букву P[i] і T[i]
вважатимемо «цифрою» від 0 до 255. Тоді P=P[1]dm-1+P[2]dm-2+P[m].
Позначимо Ts=T[s+1]dm-1+T[s+2]dm-2+T[s+m] – частина числа T
завдовжки m d-кових цифр починаючи з зсуву s. Ми шукаємо ті зсуви s, де
Ts=P. Число P можна наперед підрахувати за O(m) ітерацій,
використовуючи схему Горнера: P=P[m]+d(P[m-1]+d(P[m-2]
+....d(P[2]+dP[1])))1. T0 аналогічно обчислюється за O(m) кроків. Далі,
маючи Ts, за O(1) ітерацій можна обчислити Ts+1:Ts+1=(Ts–T[s+1]dm-
1)d+T[s+1+m] («відібравши» старший розряд зліва і «приписавши»
молодший розряд зсправа).
При цьому ми не враховували того, що числа Ts і P настільки великі,
що не помістяться в стандартні типи змінних integer int64 і т.д. Внаслідок
цього доведеться реалізовувати «арифметику з великими числами», де
складність операцій множення, додавання порівняння буде більше, ніж
O(1). Вихід є – виконувати всі обчислення по модулю фіксованого числа q.
Недолік: рівність Ts=P ще незначит, що стрічки P[1..m] і T[s+1..s+m]
рівні, оскільки Ts=P по модулю q. І тому доведеться на кожному кроці
спочатку перевіряти, чи виконується Ts=P, і у випадку позитивного
результату перевіряти посимволам P[1..m]=T[s+1..s+m]. Обчислення
Ts+1 будуть наступними:
Ts+1= d * Ts mod q – h * T[s+1] mod q + T[s+1+m] mod q
1 В.П.Дьяков, Справочник по алгоритмам и програмам, 1987г. стр. 61, Схема Горнера
використовується для обчислення степеневих багаточленів P(Z)(поліномів)
Де h = dm mod q. Основна вимога до вибору q наступне: h d<q. Ця
нерівність необхідна для того, щоб h*T[s+1] < hd неперевищує q.
З першого погляду алгоритм нескладний, але є одна проблема, при
його реалізації з урахуванням буферизированного введення з файлу: треба
завжди пам'ятати m останніх символів тексту T для того, щоб правильно
реалізувати перехід між сусідніми буферами, из-за чого код збільшився
більше, ніж в двох попередніх алгоритмах. Реалізацію з буферизованим
прочитуванням з файлавы можете знайти в RK_buffer.dpr, а для кращого
розуміння матеріалу ми розглянемо код для випадку, коли весь текст
находитсяв пам'яті (RK.dpr):
{$APPTYPE CONSOLE}
program RK;
const
MAXPLEN= 24; { максимальна довжина зразка}
q= 8388593; { максимальне просте число таке, що q*256<2^31-1}
d= 256; { вважаємо, що використовуються всі символи}
var
p: string; { зразок}
n,m: integer; { довжина зразка}
h: integer; {h =d^m mod q}
t:array[1..1048576+1] of char; { весь текст}
p0, t0: integer;
i, s k:integer;
fp,fr:textfile;ft:file; { файлові змінні для зразка, тексту і результату}
begin
assignfile(fp,'p.txt');
reset(fp);
assignfile(ft,'t.txt');
reset(ft, 1);
assignfile(fr,'res_EasyRK.txt');
rewrite(fr);
readln(fp,p);
m :=length(p); { прочитуємо зразок}
n :=FileSize(ft);
blockread(ft, t, n); { і текст}
h := 1;
for i:=1 to m do
h := h*d mod q; {h = d^(m-1) mod q}
p0 := 0; t0 :=0;
for i := 1 to m do
begin
p0:= (d*p0 + byte(p[i])) mod q;
t0:= (d*t0 + byte(t[i])) mod q;
end;
for s := 0 ton-m do
begin
if p0 =t0 then{ якщо передбачається збіг, то}
begin
k:= 1;{ перевіримо, чи співпадають рядки насправді}
while (k<=m) and (p[k]= t[s+k]) do inc(k);
if k>m then { якщо співпадають, то}
writeln(fr,s); { виводимо зсув}
end;
{ обчислюємо наступне Ts}
t0 := ( d * t0 mod q - h * byte(t[s+1]) mod q + byte(t[s+1+m])) mod q; {*}
if t0<0 then t0 := t0 + q; {**}
end;
closefile(fp);
closefile(ft);
closefile(fr);
end.
В якості q беруть найбільше просте число з урахуванням обмежень
qd<231-1 і qh<231-1 для правильності обчислень в рядку, поміченому {*}.
Умова простоти зменшує вірогідність повторів значень в послідовності {Ts}.
Найбільше число q, що задовольняє всім цим умовам – константа
q=8388593. Його обчислення вимагало написання окремого нескладного
алгоритму. Слід звернути особливу увагу на рядок, помічений {**}, який
необхідний для повернення величині Ts+1 математичного сенсу (з погляду
математики -7 mod 5= 3, а для Pascal - 7 mod 5 = -2 (mod Залишок від
ділення) ).
11.6. Оцінка алгоритму Рабина-Карпа.
У найгіршому випадку алгоритм вимагає час O(n(n-m+1)), як і
простий алгоритм. Такий результат досягається при P=am, T = an, оскільки
для всіляких зсувів s доведеться робити посимвольну перевірку P[1..m] і
T[s+1...s+m]. У загальному випадку слід чекати, що допустимих зсувів
буде небагато. Якщо допустити, що значення Ts рівноімовірні, то
вірогідність P=Ts рівна 1/q. Припустимо, зразок P входить в текст T v
разів. Тоді очікуваний час роботи алгоритму дорівнює
O(n)+O(m(v+n/q)). Якщо v=O(1), m<<q, то очікуваний час роботи
алгоритму – O(n+m).
11.7. Алгоритм Бойера-Мура (БМ).
Оригінальність цього алгоритму полягає в тому, що рядки він
порівнює не зліва направо, а справа наліво. Він дуже схожий на простий
алгоритм, за винятком того, що змішення зразка робляться не на одну, а
відразу на декілька позицій управо. Величина зміщення (і відповідно,
ефективність модифікації алгоритму) залежить виключно від зразка і
визначається різними типами евристик. Розглянемо такий приклад. Ми
шукаємо рядок override (довжина m=8) в рядку, і допустимий, зразок вже
знаходиться в положенні, як це показано на мал. 5 (у другій стрічці).
Let us consider the following
example
Override
Override
Override
Малюнок 5
Починаємо порівнювати символи з кінця. Співпадають e, d, i, стоп. У
тексті на j=4-м місці справа йде символ s, а в тексті який шукаємо – r. Яке
найбільше зміщення зразка вправо можна зробити, щоб непропустити
жодного допустимого зміщення? Тут вступає в силу так звана евристика
стоп-символа. Стоп-символ – це перший справа символ в тексті, відмінний
від відповідного символу в зразку (позначений червоним кольором; у
нашому випадку це s). Згідно цій евристиці, в зразку треба відшукати стоп-
символ, і змістити зразок так, щоб напроти стоп-символа в тексті виявився
таким же. Ми бачимо, що s в зразку не зустрічається, це означає ми
спокійно можемо змістит зразок на m–j+1=5 позицій управо. Далі, знову
починаємо порівнювати зразок з текстом. Символ е співпав, далі втексте
йде h, якого в зразку – немає. І знову ми робимо значне зміщення вправо
(4-й рядок малюнка).
Евристика стоп-символа працюватиме за умови, що ми знаємо для
кожного символу алфавіту . те саме праве місце в зразку .(с), де він
стоїть. Одержати цю інформацію нескладно:
var
Lambda: array[char] of integer;
{ евристика стоп-символа}
Procedure ComputeLastOccurenceFunction;
var
с: char;
i:integer;
begin
fillchar(Lambda,sizeof(Lambda), 0);
for i := 1 to m do
Lambda[P[i]]:= i;
end;
Далі, маючи функцію .(с), трохи модифікуємо простий алгоритм і
одержуємо алгоритм Бойера і Мура:
ComputeLastOccurenceFunction;
s := 0;
while s<= n-m do
begin
j := m;
while (j>0) and (P[j]= t[s+j]) do { поки символи співпадають}
dec(j); { рухаємося назад}
if j=0 then { якщо є збіг}
begin
writeln(fr, s); { виводимо результат}
s := s + (m + 1 -Lambda[t[s+m+1]]); {зсув зразка}
end else begin
if j- Lambda[t[s+j]]<= 0 then {якщо зсув непозитивний}
inc(s) { тоді зрушуємо зразок управо на 1}
else{ інакше зміщення і відповідності з евристикою стоп-
символа}
s := s + j -Lambda[t[s+j]];
end;
end;
Слід звернути увагу на строчку if j-Lambda[t[s+j]] <= 0 then. Річ
у тому, що найправіше входження t[s+j] в зразок може знаходитися
правіше, ніж j. Для того, щоб неробити зміщення вліво, ми зміщуємо на
одну позицію вправо.
Деякі модифікації цього алгоритму враховують декілька евристик.
Наприклад, в книзі Кормена (згаданої вище) розповідається про евристику
безпечного суфікса, яка полягає в наступному: якщо P[j]<>T[s+j], де
j<m, то ми можемо безпечно збільшити зміщення
.(j)= m–max {k: 0 . k . m и P[j+1..m] ~Pk}
(A~B означає, що одне із слів A і B буде суфіксом іншого). Потім,
маючи дві евристики, з них вибирають ту, яка дає більший зсув. Проте на
практиці додаткові евристики не завжди дають настільки більшого
приросту швидкості алгоритму. Позначаються додаткові витрати на
обчислення евристичних функцій (зокрема, для .(j) потрібно обертати
зразок і двічі шукати префікс-функцію).
Реалізацію алгоритму у файлі BM.dpr.
{$APPTYPE CONSOLE}
Program BM;
const
MAXPLEN = 24;
var
p: string; {зразок}
t: array[1..1048576+1] of char; {текст}
m, n: integer;
Lambda: array[char] of integer;
{робочі змінні}
fp, fr: textfile; ft: file; {файлові змінні для зразка, тексту і результату}
j, s: integer;
{евристика стоп-символа}
procedure ComputeLastOccurenceFunction;
var
c: char; i: integer;
begin
fillchar(Lambda, sizeof(Lambda), 0);
for i := 1 to m do
Lambda[P[i]] := i;
end;
begin
assignfile(fp, 'p.txt'); reset(fp);
assignfile(ft, 't.txt'); reset(ft, 1);
assignfile(fr, 'BM.out'); rewrite(fr);
readln(fp, P); m := length(P);
n := FileSize(ft); blockread(ft, t, n);
ComputeLastOccurenceFunction;
s := 0;
while s <= n-m do
begin
j := m;
while (j>0) and (P[j] = t[s+j]) do {поки символи співпадають}
dec(j); {просуваємося назад}
if j=0 then {якщо є співпадіння}
begin
writeln(fr, s); {виводимо результат}
s := s + (m + 1 - Lambda[t[s+m+1]]); {сміщення зразка}
end else begin
if j - Lambda[t[s+j]] <= 0 then {якщо зміщення відємне}
inc(s) {тоді сзуваємо зразок вправо на 1}
else {інакше зсув у відповідності з еврістікою стоп-символа}
s := s + j - Lambda[t[s+j]];
end;
end;
closefile(fp); closefile(ft); closefile(fr);
end.
11.8. Аналіз алгоритму БМ.
Час роботи Compute Last Occurrence Function – O(...+m). У гіршому
разі (T=an, P=am) алгоритм завершить роботу за час O(...+m(n-m+1)).
На практиці алгоритм виявляється набагато швидшим за будь-який інший,
оскільки часто змішення виходять дуже великими. Кнут продемонстрував,
що для локалізації всіх входжень зразків текст алгоритму Бойера-Мура
потрібна O(n+rm) операцій, де r – кількість входжень зразка в текст. Ми
не займатимемося обчисленням очікування складності цього алгоритму, а
лише приведемо готовий результат (тут A(n) – кількість порівнянь для
випадкового рядка довгі n):
Недолік алгоритму: для нього дуже складно реалізувати пошук через
буферизоване введення з файлу. Тому він найбільш ефективний у разі,
коли текст повністю знаходиться в пам'яті.
11.9. Алгоритм Shift-And.
Винахідники цього алгоритму – Сан Ву (Sun Wu) і Вудь Манбер (Udi
Manber), два учених з університету, Арізони. У ньому шукаються
входження всіх префіксів P[1..k] зразка P (зокрема, і самого P) в текст T.
В процесі роботи алгоритму будується бітова таблиця Table1[1..M,1..N]
(мал. 6).
a
p
p
x
l
E
a
p
y
a
P
p
l
e
a
1
0
0
0
0
0
1
0
0
1
0
0
0
0
p
0
1
0
0
0
0
0
1
0
0
1
0
0
0
p
0
0
1
0
0
0
0
0
0
0
0
1
0
0
l
0
0
0
0
0
0
0
0
0
0
0
0
1
0
e
0
0
0
0
0
0
0
0
0
0
0
0
0
1
Малюнок 6.
Процес побудови йде по рядках зліва направо (на кожній ітерації
дописується стовпець). Одиниця на перетині к-й рядка і i-го стовпця
означає, що T[i-k+1..i]=P[1..k], тобто P[1..k] є суфіксом T[1..i]. Нас
цікавить останній рядок, оскільки він показує такі позиції i в тексті, що
P[1..M] є суфіксом T[1..i], тобто допустимі зміщення i-m. Останній рядок
можна одержати тільки за наявності всіх попередніх. Тут вступає в силу
принцип динамічного програмування: Table[k, i]= 1 тоді, коли Table[k-1,
i-1]= 1 і T[i]= P[k], тобто тоді, коли k-1 попередніх символів тексту
співпали з префіксом P[1..k-1], і наступний символ T[i] співпадає з
наступним символом зразка P[k].
З того, що наступний стовпець таблиці виходить з попереднього,
витікає, що нам воднораз часу потрібно знати лише поточний стовпець. За
умови M . 32 його можна представити у вигляді 32-бітового числа (однієї
змінної типу cardinal), в якій к-й зліва (!) біт буде рівний 1 на i-й ітерації
(P[1..k] є суфіксом T[1..i]) якщо на (i-1) -ій ітерації (k-1) -й зліва біт був
рівний 1 і T[i]=P[k].
Все вищесказане можна здійснити за допомогою операцій AND і OR,
маючи заздалегідь обчислені характеристичні вектори для кожного символу
c:
var
cv: array[char] of cardinal;
На прикладі P = abcacb матимемо: cv[‘a’]= 100100, cv[‘b’]=
010001, cv[‘c’]=001010. Тобто, загальне правило: одиниця в
характеристичному векторі cv[c] стоїть там, де в зразку P стоїть символ с.
Далі, для отримання наступного стовпця (наступного значення вектора)
нам треба змістит попередній «вниз» (тобто вправо) і «приклеїти»
оператором OR до нього cv[t[i]]. Код алгоритму виглядає так:
var
cv: array[char] of cardinal; { характеристичні вектори для
всіх}
bit: array[1..32] of cardinal; {bit[i]=2^(i-1); i=1..M}
vector bit0: cardinal; {vector - поточне значення вектора; bit0
= 2^(m-1)}
{ побудова характеристичних векторів}
procedure BuildCV;
var i: integer;
begin
fillchar(bit, sizeof(bit), 0);
fillchar(cv, sizeof(bit), 0);
for i := 1 to m do
bit[i]:= 1 shl (m - i);
for i := 1 to m do
cv[p[i]]:= cv[p[i]] or bit[i];
end;
begin
< читаємо значення p і t >
BuildCV;
vector := $FFFFFFFF; { початкове значення}
bit0 := bit[1];
for i:=1 to n do
begin
vector := (vector shr 1 or bit0) and cv[t[i]];
if boolean(vector and 1) then
writeln(fr, i-m);
end;
...
end.
У алгоритму є особливість, яка може збити з пантелику: біти
нумеруються навпаки (зліва направо), а не так, як прийнято. Крім того,
при зрушенні вниз (тобто, управо) вектора vector його перший (!) біт
рівний 0, а повинен стати рівний 1, інакше «and cv[t[i]]» не спрацює
навіть при збігу P[1] з t[i]. Тому рядок
vector := (vector shr 1 or bit0) and cv[t[i]];
повинна бути саме такий, а не такий:
vector := (vector shr 1) and cv[t[i]];
Повний код реалізації ви знайдете у файлі Bit1.dpr.
{$APPTYPE CONSOLE}
program Bit1;
var
m, n, i: integer;
p: string; {зразок}
t: array[1..1024*1024+1] of char; {текст}
cv: array[char] of cardinal; {характеристичні вектори для всіх с}
bit: array[1..32] of cardinal; {bit[i]=2^(i-1); i=1..M}
vector, bit0: cardinal; {vector - текуще значення вектора; bit0 = 2^(m-1)}
fp, fr: textfile; ft: file;
{побудова характеристичних векторів}
procedure BuildCV;
var i: integer;
begin
fillchar(bit, sizeof(bit), 0);
fillchar(cv, sizeof(bit), 0);
for i := 1 to m do
bit[i] := 1 shl (m - i);
for i := 1 to m do
cv[p[i]] := cv[p[i]] or bit[i];
end;
begin
assignfile(fp, 'p.txt'); reset(fp);
assignfile(ft, 't.txt'); reset(ft, 1); {відкриваємо всі файли}
assignfile(fr, 'bit.out'); rewrite(fr);
readln(fp, p); m := length(p); {читаємо зразок}
n := FileSize(ft); blockread(ft, t, n);
BuildCV; {будуємо характеристичні вектори для кожного символа}
vector := $FFFFFFFF; {початкове значення}
bit0 := bit[1];
for i:=1 to n do
begin
vector := (vector shr 1 or bit0) and cv[t[i]];
if boolean(vector and 1) then
writeln(fr, i-m);
end;
closefile(fp);
closefile(ft);
closefile(fr);
end.
11.10. Аналіз алгоритму Shift-And.
Складність алгоритму, як легко бачити, O(n+m) у будь-якому
випадку. Об'єм необхідної пам'яті – O(m). Алгоритм повністю придатний
для пошуку у файлі з буферизированным введенням.
За рахунок «апаратної орієнтації» алгоритм особливо ефективний для
зразків, довжина яких не перевищує розрядність процесора (32, 64, ...). З
іншого боку, ця особливість є і обмеженням, бо при великій довжині зразка
вже не вийшло б запам'ятовувати весь стовпець в одній змінній, і довелося
б оперувати масивами, що істотно понизило б його ефективність.
Ще одна позитивна межа цього алгоритму – розширюваність до
алгоритму нечіткого пошуку.
11.11. Тестування алгоритмів.
Отже, ми розглянули п'ять швидких алгоритмів пошуку зразка в
тексті. Тепер прийшов час перевірити їх ефективність на практиці. Для
цього за допомогою нескладної програми я згенерував 2 тексти розміром в
1 МБ і зразок довгої 24 символи так, щоб цей зразок повторювався в
текстах близько 10000 разів. Зразок складається з символів a...d, тексти
відрізнялися тільки тим, що в одному з них зустрічалися символи а ...d, у
другому – a...z (мета цього буде показана пізніше). Далі, в реалізацію
кожного алгоритму я додав код, замеряющий час до і після основної
частини алгоритму (тобто, без урахування операцій з файлами). Для
достовірності вимірів виведення результатів (writeln) теж довелося
закоментувати. На моєму Athlon XP 1600+ всі алгоритми видавали
результат миттєво, і тому для точних вимірювань я поставив основні
частини в цикл, що повторює їх по 1000 разів.
Результат тестування був наступний:
Алгоритм
Тест 1,
сек. . 10-3
Тест 2,
сек. . 10-3
Кінцевий
автомат
7.10
7.10
Shift-AND
8.693
8.693
БМ
11.446
3.615
КМП
13.229
8.772
Простий
14.471
10.205
алгоритм
РК
117.19
117.139
Перший тест (файл з символами а...d) – дуже штучний, і вірогідність
появи такого на практиці дуже низька. За рахунок великої вірогідності
повторень частин зразка алгоритм БМ опустився на третє місце, тоді як в
реальнішому тесті (де зустрічаються символи а..z) БМ-алгоритм удвічі
обігнав своїх суперників, і це при тому, що в ньому була закладена всього
лише одна евристика. А якщо їх були б декілька, то при великому тексті
алгоритм працював би ще швидше.
Як бачимо, на кінцевий автомат, як і на Shift-AND вміст тексту взагалі
не впливає: обидва дуже стабільні і швидкі. Трохи відстає від них КМП, і те
за рахунок того, що КПМ – не що інше, як «недороблений автомат» в тому
сенсі, що замість того, щоб підрахувати переходи наперед, в КМП це
робиться «на льоту» циклом:
while (len>0) and (t[i]<>p[len+1]) do len := f[len];
Тому при зразках з частими повтореннями (такими, як наш) і текстом
з великою кількістю повторень частин, цей цикл працює майже удвічі
довше.
З алгоритмами Рабина-коропа і простим все зрозуміло. РК теоретично
ефективний, але на практиці сильно програв всім алгоритмам за рахунок
громіздких обчислень з діленням по модулю.
Висновки
Все вищесказане у жодному випадку не можна сприймати за еталон.
Будь-який тест може показати переваги і недоліки конкретних реалізацій, а
не самих алгоритмів. Який з них вибирати – вирішувати вам залежно від
завдань. Якщо текст «нормального» змісту, плюс ще і зразок такої ж, то я
порекомендував би скористатися БМ. Якщо як текст і зразок може бути що
завгодно, скористайтеся Shift-AND або скінченим автоматом, тим паче, що
останній нескладно модифікувати для пошуку довільної кількості зразків
одночасно.
17.02.2013 23:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора