Алгоритми пошуку підрядка в рядку 2

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Федеральне міністерство за освітою

Державна освітня установа вищої професійної освіти
«Вятський державний гуманітарний університет»
Факультет інформатики
Кафедра інформатики і методики навчання інформатики
Курсова робота
Алгоритми пошуку підрядка в рядку
Виконав
студент III курсу математичного факультету
Бєлов Денис Володимирович
Перевірив викладач кафедри інформатики та методики навчання інформатики
Іванов С. Ю.
Кіров, 2006 р.

Зміст.

Введення. 3
Частина 1. Теоретичні відомості про алгоритми пошуку підрядка в рядку. 5
1.1. Основні поняття. 5
1.1.1 Рядок, її довжина, підрядок. 5
1.1.2. Поняття про складність алгоритму. 6
1.2. Алгоритми засновані на методі послідовного пошуку. 7
1.2.1. Алгоритм послідовного (прямого) пошуку (The Brute Force Algorithm). 7
1.2.2. Алгоритм Рабіна. 7
1.3. Алгоритм Кнута - Морріса - Пратта (КМП). 10
1.4. Алгоритм Бойєра - Мура і деякі його модифікації. 13
1.4.1. Алгоритм Боейера - Мура. 13
1.4.2. Модифікації БМ. 15
1.5. Пошук підрядків за допомогою кінцевого автомата. 17
1.5.1. Структура автомата. 17
1.5.2. Приклад побудови кінцевого автомата. 19
Частина 2. Експериментальний аналіз алгоритмів. 21
2.1. Суть експерименту. 21
2.2. Результати та аналіз експерименту. 22
Висновок. 24
Бібліографічний список. 25


Введення

Ті, кому доводиться часто працювати з текстовими редакторами, знають ціну функції знаходження потрібних слів у тексті, істотно полегшує редагування документів і пошук потрібної інформації. Дійсно, сучасні програми обробки тексту привчили нас до такої зручної можливості, як пошук і заміна фрагментів, і якщо ви розробляєте подібну програму, користувач має право очікувати, що ви надасте в його розпорядження відповідні команди.
Звичайно, зараз функції пошуку інкапсульовані в багато мов програмування високого рівня - щоб знайти рядок у невеликому тексті ви, напевно, використовуєте вбудовану функцію. Але якщо такого роду пошук є ключовим завданням вашої програми, знати принципи організації функцій пошуку буде зовсім не зайве. При цьому. в готових підпрограмах далеко не завжди все написано кращим чином. По-перше, в стандартних функціях не завжди використовуються найефективніші алгоритми, а по-друге, цілком можливо, що вам знадобиться змінити стандартну поведінку цих функцій (наприклад, передбачити можливість пошуку за шаблоном). Нарешті, область застосування функції пошуку не обмежується одними лише текстовими редакторами. Слід відзначити використання алгоритмів пошуку при індексації сторінок пошуковим роботом, де актуальність інформації безпосередньо залежить від швидкості знаходження ключових слів у тексті html - сторінки [9, с. 10]. Робота найпростішого спам - фільтра, полягає в знаходженні в тексті листа фраз таких, як «Мільйон за годину» або «Розкрутка сайту». Все вищесказане свідчить про актуальність проблеми, зачепленої роботою.
Поставимо задачу пошуку підрядка в рядку. Нехай у нас є рядок, що складається з деякої кількості символів. Нам потрібно перевірити, чи входить інша задана рядок в даний текст, і якщо входить, то починаючи з якого символу тексту.
У даній роботі ми ставимо за мету, виявити найбільш оптимальний алгоритм, вирішальний поставлене завдання пошуку.
Завдання даної роботи:
· Розглянути основні алгоритми, що вирішують завдання пошуку;
· Систематизувати алгоритми згідно використовуваним в них прийомів;
· Виявити ефективні, з точки зору часу виконання, алгоритми.
Робота містить дві основні частини. У першій будуть розглянуті алгоритми, їх теоретичне обгрунтування, алгоритмічна модель, буде проведена спроба їх класифікації. У другій частині роботи будуть наведені дані про практичне застосування алгоритмів. У висновку буде зроблено висновок про найбільш ефективний (з тимчасовою точки зору) алгоритмі.

Частина 1. Теоретичні відомості про алгоритми пошуку підрядка в рядку.

1.1. Основні поняття.

1.1.1 Рядок, її довжина, підрядок.

Тут ми наводимо ряд визначень, які будемо використовувати у викладі матеріалу [5, 11].
Визначення 1. Рядок (слово) - це послідовність знаків (званих літерами) з деякого кінцевого безлічі, званого алфавітом.
Визначення 2. Довжина рядка - кількість знаків у рядку.
Слова будемо позначати літерами латинського алфавіту, напр. X = x [1] x [2] ... x [n] - слово довгою n, де x [i] (i-а літера слова) належить алфавітом. Lentgh (X) = = N - позначення довжини рядка.
Визначення 3. Слово не містить жодної букви називається порожнім.
Порожнє слово зазвичай позначають буквою L. Length (L) = 0.
Визначення 4. Слово X називається префіксом слова Y, якщо є таке слово Z, що Y = XZ. Причому саме слово є префіксом для самого себе (тому що знайдеться нульове слово L, що X = LX.
Приклад: слово ab є префіксом слова abcfa.
Визначення 5. Слово X називається суфіксом слова Y, якщо є таке слово Z, що Y = ZX. Аналогічно, слово є суфіксом самого себе.
Приклад: слово bfg є суфіксом слова vsenfbfg.
Визначення 6. Слово X називається підрядком рядка Y, якщо знайдуться такі рядки Z 1 і Z 2, що Y = Z 1 XZ 2. При цьому Z 1 називають лівим, а Z 2 - правим крилом підрядка. Підрядком може бути й саме слово. Іноді при цьому слово X називають входженням в слово Y. Серед всіх входжень слова X в слово Y, входження з найменшою довжиною свого лівого крила називають першим або головним змістом. Для позначення входження використовують позначення X Y.
Приклад: слова hrf і fhr є підстроками слова abhrfhr, gf sfdgfro.

1.1.2. Поняття про складність алгоритму.

Метою нашої роботи є знайти ефективний алгоритм, проте нічого поки що не було сказано про метод оцінки алгоритмів.
Традиційно в програмуванні поняття складності алгоритму пов'язано з використанням ресурсів комп'ютера: наскільки багато процесорного часу вимагає програма для свого виконання, наскільки багато при цьому витрачається пам'ять машини? Облік пам'яті зазвичай ведеться за обсягом даних і не береться до уваги пам'ять, що витрачається для запису команд програми. Час розраховується у відносних одиницях так, щоб ця оцінка, по можливості, була однаковою для машин з різною тактовою частотою. [11, с. 38-40]
У даній роботі будуть розглянуті дві характеристики складності алгоритмів - тимчасова і емкостная. Ми не будемо обговорювати логічну складність розробки алгоритму - скільки «людино-днів» потрібно витратити на створення програми, оскільки не представляється можливим дати об'єктивні кількісні характеристики.
Тимчасову складність будемо підраховувати у виконуваних командах: кількість арифметичних операцій, кількість порівнянь, пересилань (залежно від алгоритму). Ємнісна складність буде визначатися кількістю змінних, елементів масивів, елементів записів або просто кількістю байт [6, 7, 10, 11].
Ефективність алгоритму також буде оцінюватися за допомогою підрахунку часу виконання алгоритмом конкретно поставленої задачі, тобто з допомогою експерименту, докладніше про це в частині 2 даної роботи.

1.2. Алгоритми засновані на методі послідовного пошуку.

1.2.1. Алгоритм послідовного (прямого) пошуку (The Brute Force Algorithm).

Найбільш очевидний алгоритм. Позначимо S - слово, у якому шукається зразок X. Нехай m і n - довжини слів S і X відповідно. Можна порівняти зі словом X всі подслова S, які починаються з позицій 1,2 ,..., m-n +1 в слові S; у разі рівності виводиться відповідна позиція (Лістинг 1). [1, 2]
Лістинг 1
ref SHAPE \ * MERGEFORMAT
Function Search (S: String; X: String; var Place: Byte): Boolean;
{Функція повертає результат пошуку в слові S}
{Подслова X. Place - місце першого входження}
var Res: Boolean; i: Integer;
Begin
Res: = FALSE;
i: = 1;
While (i <= Length (S)-Length (X) +1) And Not (Res) do
If Copy (S, i, Length (X)) = X then
begin
Res: = TRUE;
Place: = i
end
else i: = i +1;
Search: = Res
End;

Дуже просто, але дуже нерозумно. Адже максимальне, кількість порівнянь дорівнюватиме O ((m-n +1) * n +1), хоча більшість з них насправді зайві. Наприклад, знайшовши рядок aabc і виявивши невідповідність у четвертому символі (співпало тільки aab), алгоритм буде продовжувати порівнювати рядок, починаючи з наступного символу, хоча це однозначно не призведе до результату.
Наступний метод працює набагато швидше найпростішого, але, на жаль, накладає деякі обмеження на текст і шуканий рядок.

1.2.2. Алгоритм Рабіна.

Алгоритм Рабіна представляє собою модифікацію лінійного алгоритму; він заснований на досить простій ідеї, яку викладемо, слідуючи книзі [13 ,172-173].
«Уявімо собі, що в слові A, довжина якого дорівнює m, ми шукаємо зразок X довжини n. Виріжемо "віконечко" розміром n і будемо рухати його з вхідного слова. Нас цікавить, не збігається слово в "віконечку" із заданим зразком. Порівнювати по буквах довго. Замість цього фіксуємо деяку числову функцію на словах довжини n, тоді завдання зведеться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" та на зразку різні, то збігу немає. Тільки якщо значення однакові, необхідно перевіряти послідовно збіг по буквах. »(Лістинг 2)
Лістинг 2
ref SHAPE \ * MERGEFORMAT
Function Search (S: String; X: String; var Place: Byte): Boolean;
{Функція повертає результат пошуку в слові S}
{Подслова X. Place - місце першого входження}
Var Res: Boolean; i: Byte; h, NowH, LenX: Integer; HowMany: Integer;
Begin
Res: = FALSE;
i: = 1;
h: = Hash (x); {Обчислення хеш-функції для шуканого слова}
NowH: = Hash (Copy (S, 1, Length (x)));
HowMany: = Length (S)-Length (X) +1;
LenX: = Length (X);
While (i <= HowMany) And Not (Res) do
If (h = NowH) and (Copy (S, i, Length (X)) = X) then
Begin
Res: = TRUE;
Place: = i
End
else
Begin
i: = i +1;
NextHash (s, i, NowH, LenX); {Обчислення наступного значення хеш-функції}
End;
Search: = Res
End;

Цей алгоритм виконує лінійний прохід по рядку (n кроків) і лінійний прохід по всьому тексту (m кроків), отже, загальний час роботи є O (n + m). При цьому ми не враховуємо тимчасову складність обчислення хеш-функції, так як, суть алгоритму в тому і полягає, щоб дана функція була настільки легко обчислюється, що її робота не впливала на загальну роботу алгоритму. Тоді, час роботи алгоритму лінійно залежить від розміру рядка і тексту, стало бути програма працює швидко. Адже замість того, щоб перевіряти кожну позицію на предмет відповідності зі зразком, ми можемо перевіряти тільки ті, які «нагадують» зразок. Отже, для того, щоб легко встановлювати явна невідповідність, будемо використовувати функцію, яка повинна:
1. Легко обчислюватися.
2. Як можна краще розрізняти неспівпадаючі рядки.
3. hash (y [i +1, i + m]) повинна легко обчислюватися за hash (y [i, i + m-1].
Під час пошуку х будемо порівнювати hash (x) з hash (y [i, i + m-1]) для i від 0 до nm включно. Якщо виявляємо збіг, то перевіряємо посимвольно.
Приклад (зручною для обчислення функції) [13, 172]. Замінимо всі букви в слові і зразку їх номерами, що представляють собою цілі числа. Тоді зручною функцією є сума цифр. (При зсуві "віконечка" потрібно додати нове число і відняти "зникле".)
Однак, проблема в тому, що шукана рядок може бути довгою, рядків в тексті теж вистачає. А так як кожному рядку потрібно зіставити унікальне число, то і чисел має бути багато, а стало бути, числа будуть великими (порядку D * n, де D - кількість різних символів), і працювати з ними буде так само незручно. Але який інтерес працювати тільки з короткими рядками і цифрами? Розробники алгоритму придумали, як поліпшити цей алгоритм без особливих втрат у швидкості роботи.
Приклад (сімейства зручних функцій) [13, 172-173]. Виберемо деякий число p (бажано просте) і деякий вирахування x за модулем p. Кожне слово довжини n будемо розглядати як послідовність цілих чисел (замінивши літери їх кодами). Ці числа будемо розглядати як коефіцієнти многочлена ступеня n-1 і обчислимо значення цього многочлена з модулю p в точці x. Це і буде одна з функцій сімейства (для кожної пари p і x виходить своя функція). Зсув "віконечка" на 1 відповідає вирахуванню старшого члена, множенню на x і додаванню вільного члена. Наступне міркування говорить на користь того, що збігу не дуже вірогідні. Нехай число p фіксоване і до того ж воно є простим, а X і Y - два різних слова довжини n. Тоді їм відповідають різні многочлени (ми припускаємо, що коди всіх букв різні - це можливо при p, більшому числа літер алфавіту). Збіг значень функції означає, що в точці x ці два різних многочлена збігаються, тобто їх різниця звертається до 0. Різниця є многочлен ступеня n-1 і має не більше n-1 коренів. Таким чином, якщо n багато менше p, то випадковим значенням x мало шансів потрапити в "невдалу" крапку.
Строго кажучи, час роботи всього алгоритму в цілому, є O (m + n + mn / P), mn / P досить невелика, так що складність роботи майже лінійна. Зрозуміло, що просте число слід вибирати великим, чим більше це число, тим швидше буде працювати програма.
Алгоритм Рабіна і алгоритм послідовного пошуку є алгоритмами з найменшими трудовитратами, тому вони годяться для використання при вирішенні деякого класу задач. Однак ці алгоритми не є найбільш оптимальними (хоча б тому, що іноді виконують явно марну роботу, про що було сказано вище), тому ми перейдемо до наступного класу алгоритмів. Ці алгоритми з'явилися в результаті ретельного дослідження алгоритму послідовного пошуку. Дослідники хотіли знайти способи більш повно використовувати інформацію, отриману під час сканування (алгоритм прямого пошуку її просто викидає). Розглянемо алгоритм Кнута - Морріса - Пратта.

1.3. Алгоритм Кнута - Морріса - Пратта (КМП).

Спочатку розглянемо деякі допоміжні затвердження. Для довільного слова X розглянемо всі його початку, що одночасно є його кінцями, і виберемо з них найдовше (не рахуючи, звичайно, самого слова X). Позначимо його n (X). Така функція носить назву префікс - функції [13].
Приклади.
n (aba) = a, n (n (aba)) = n (a) = L;
n (abab) = ab, n (n (abab)) = n (ab) = L;
n (ababa) = aba, n (n (ababa)) = n (aba) = a, n (n (n (ababa))) = n (a) = L; n (abc) = L.
Доведемо кілька використовуваних згодом фактів, а саме пропозиція (за [Шень, 1995, с.165-166]):
(1) Послідовність слів n (X), n (n (X)), n (n (n (X ))),... "Обривається" (на порожньому слові L).
(2) Усі слова n (X), n (n (X)), n (n (n (X ))),..., L є началами слова X.
(3) Будь-яке слово, що одночасно є початком і кінцем слова X (крім самого X), входить в послідовність n (X), n (n (X )),...., L.
Доказ.
(1) Тривіально, тому що кожне слово, яке коротше попереднього.
(2) Кожне з них (за визначенням) є початком попереднього. З тієї ж причини всі вони є кінцями слова X.
(3) Нехай слово Y є одночасно початком і кінцем X. Слово n (X) - найдовше з таких слів, так що Y не довше n (X). Обидва ці слова є началами X, тому більш короткий з них є початком більш довгого: Y є початок n (X). Аналогічно, Y є кінець n (X). Міркуючи по індукції, можна припускати, що затвердження завдання вірно для всіх слів коротше X, зокрема, для слова n (X). Так що слово Y, що є кінцем і початком n (X), або дорівнює n (X), або входить в послідовність n (n (X)), n (n (n (X ))),...,, L .
Пропозиція доведено.
Метод КМП використовує предобработку шуканого рядка, а саме: на її основі створюється префікс-функція. При цьому використовується наступна ідея: якщо префікс (він же суфікс) рядки довгою i довше одного символу, то він одночасно і префікс підрядка довгою i-1 (Лістинг 3). Таким чином, ми перевіряємо префікс попередньої підрядка, якщо ж той не підходить, то префікс її префікса, і т.д. Діючи так, знаходимо найбільший шуканий префікс. Наступне питання, на який варто ref SHAPE \ * MERGEFORMAT
Procedure PrefFunc (P: String; Var Fl: TMas);
Var n, i, j: Integer;
Begin
n: = Length (P);
Fl [1]: = 0;
For i: = 2 To n Do
Begin
j: = Fl [i-1];
While (j <> 0) And (P [j] <> P [i-1]) Do j: = Fl [j];
Fl [i]: = j +1;
End;
End;
відповісти: чому час роботи процедури лінійно, адже в ній присутній вкладений цикл? Ну, по-перше, присвоєння префікс-функції відбувається чітко m разів, решту часу змінюється мінлива k. Так як у циклі while вона зменшується (P [k] <k), але не стає менше 0, то зменшуватися вона може не частіше, ніж зростати. Змінна k зростає на 1 не більше m разів. Значить, мінлива k змінюється всього не більше 2m ​​разів. Виходить, що час роботи всієї процедури є O (m) [1, 2].
Лістинг 3
А зараз ми переходимо до самого алгоритму, що шукає підрядок в рядку (Лістинг 4).
Лістинг 4
ref SHAPE \ * MERGEFORMAT
Function KMPSearch (S, P: String): Integer;
{Алгоpитм Кнута-Моpіса-Пpатта, що встановлює}
{Входження непорожній стpок P в стpок S}
Var Fl: TMas;
i, j, n, m: Integer;
Begin
n: = Length (S);
m: = Length (P);
PrefFunc (P, Fl);
j: = 1;
For i: = 1 To n Do
begin
While (j <> 0) And (P [j] <> S ​​[i]) do j: = Fl [j];
If j = m Then Break;
j: = j +1
end;
If (j = m) then Result: = i-j +1 Else Result: = 0;
End;

Довести що ця програма працює за лінійний час, можна точно так само, як і для префікс - функції. Стало бути, загальний час роботи програми є O (n + m), тобто лінійний час.
Наостанок зауважимо, що алгоритм послідовного пошуку та алгоритм КМП крім знаходження самих рядків вважають, скільки символів збіглося в процесі роботи.

1.4. Алгоритм Бойєра - Мура і деякі його модифікації.

1.4.1. Алгоритм Боейера - Мура.

Алгоритм Бойєра-Мура, розроблений двома вченими - Бойером (Robert S. Boyer) і Муром (Strother Moore), вважається найбільш швидким серед алгоритмів загального призначення, призначених для пошуку підрядка в рядку.
Найпростіший варіант алгоритму Бойєра-Мура складається з наступних кроків. На першому кроці ми будуємо таблицю зміщень для шуканого зразка. Процес побудови таблиці буде описано нижче. Далі ми поєднуємо початок рядка і зразка і починаємо перевірку з останнього символу зразка. Якщо останній символ зразка та відповідний йому при накладенні символ рядка не збігаються, зразок зрушується щодо рядка на величину, отриману з таблиці зміщень, і знову проводиться порівняння, починаючи з останнього символу зразка. Якщо ж символи збігаються, проводиться порівняння передостаннього символу зразка і т. д. Якщо всі символи зразка збіглися з накладеними символами рядки, значить ми знайшли підрядок і пошук закінчено. Якщо ж якийсь (не останній) символ зразка не співпадає з відповідним символом рядка, ми зрушуємо зразок на один символ вправо і знову починаємо перевірку з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнуто кінець рядка.
Величина зрушення у разі неспівпадання останнього символу обчислюється виходячи з таких міркувань: зрушення зразка повинен бути мінімальним, таким, щоб не пропустити входження зразка в рядку. Якщо цей символ рядка зустрічається у зразку, ми зміщуємо зразок таким чином, щоб символ рядка збігся з найбільш правим входженням цього символу у зразку. Якщо ж зразок взагалі не містить цього символу, ми зрушуємо зразок на величину, що дорівнює його довжині, так що перший символ зразка накладається на наступний за перевіряється символ рядка.
Величина зміщення для кожного символу зразка залежить тільки від порядку символів у зразку, тому зсуву зручно обчислити наперед і зберігати у вигляді одновимірного масиву, де кожному символу алфавіту відповідає зміщення відносно останнього символу зразка. Пояснимо все вищесказане на простому прикладі. Нехай у нас є алфавіт з п'яти символів: a, b, c, d, e і ми хочемо знайти входження зразка "abbad" в рядку "abeccacbadbabbad". Наступні схеми ілюструють всі етапи виконання алгоритму. Таблиця зсувів буде виглядати так.

Початок пошуку.

Останній символ зразка не співпадає з накладеним символом рядка. Зрушуємо зразок вправо на 5 позицій:

Три символу зразка збіглися, а четвертий - ні. Зрушуємо зразок вправо на одну позицію:

Останній символ знову не збігається з символом рядка. Відповідно до таблиці зміщень зрушуємо зразок на 2 позиції:

Ще раз зрушуємо зразок на 2 позиції:



Тепер, згідно з таблицею, зрушуємо зразок на одну позицію, і отримуємо шукане входження зразка:

Реалізуємо вказаний алгоритм на мові Pascal.
Перш за все слід визначити тип даних «таблиця зсувів». Для кодової таблиці, що складається з 256 символів, визначення цього типу буде виглядати так:
Type
TBMTable = Array [0 .. 255] of Integer;
Далі наводиться процедура, що обчислює таблицю зміщень для зразка p (Лістинг 5).
Лістинг 5
ref SHAPE \ * MERGEFORMAT
Procedure MakeMBTable (var Bmt: TBMTable; Const p: string);
Var i: Integer;
Begin
For i: = 0 to 255 do Bmt [i]: = Length (p);
For i: = Length (p) Downto 1 Do
If Bmt [Byte (p [i])] = Length (p) Then
Bmt [Byte (p [i])]: = Length (p) - i;
End;

Тепер напишемо функцію, що здійснює пошук (Лістинг 6).
Параметр StartPos дозволяє вказати позицію в рядку s, з якою слід починати пошук. Це може бути корисним у тому випадку, якщо ви захочете знайти всі входження p в s. Для пошуку з самого початку рядка слід задати StartPos рівним 1. Якщо результат пошуку не дорівнює нулю, то для того, щоб знайти наступне входження p в s, потрібно задати StartPos рівним значенням «попередній результат плюс довжина зразка».

1.4.2. Модифікації БМ.

Швидкий пошук (Класифікація Thierry Lecroq [2]).

Зрушення поганого символу, який використовується в алгоритмі Боуер - Мура, не дуже ефективний для маленького алфавіту, але, коли розмір алфавіту велику у порівнянні з довжиною зразка, як це часто має місце з
ref SHAPE \ * MERGEFORMAT
function bmsearch (startpos: integer; const s, p: string;
const bmt: tbmtable): integer;
var
pos, lp, i: integer;
begin
lp: = length (p);
pos: = startpos + lp -1;
while pos <length (s) do
if p [lp] <> s [pos] then pos: = pos + bmt [s [pos]]
else for i: = lp - 1 downto 1 do
if p [i] <> s [pos - lp + i] then
begin
inc (pos);
break;
end
else if i = 1 then
begin
result: = pos - lp + 1;
exit;
end;
result: = 0;
end;

таблицею ASCII і при звичайному пошуку в текстовому редакторі, він стає надзвичайно корисний. Використання в алгоритмі тільки його одного може бути досить ефективним.
Після спроби поєднання x і y [i, i + m-1], довжина зсуву - не менше 1. Таким чином, символ y [i + m] обов'язково буде залучений в наступну спробу, а значить, може бути використаний в поточній спробі для зрушення поганого символу. Модифікуємо функцію поганого символу, щоб прийняти до уваги останній символ х:
bc [a] = min {j | 0 j m і x [m - 1 - j] = a}, якщо a зустрічається в x,
bc [a] = m в протилежному випадку.
Порівняння тексту і зразка можуть проводитися у будь-якому порядку.

Лістинг 6
Турбо БМ (Класифікація Thierry Lecroq [2]).

Турбо - БМ є також є поліпшенням алгоритму Боуер - Мура. Ми будемо запам'ятовувати сегмент тексту, який зійшовся з суфіксом зразка під час минулої спроби (і тільки, якщо стався зсув хорошого суфікса).
Це дасть нам дві переваги:
1. Можливість перескочити через цей сегмент
2. Можливість застосування «турбо - зсуву»
«Турбо - зрушення» може відбутися, якщо ми виявимо, що суфікс зразка, який збігається з текстом, коротше, ніж той, який був запам'ятати раніше.
Нехай u - запомненний сегмент, а v - cуффікс, який співпав під час поточної спроби, такий що uzv - суфікс x. Тоді av - суфікс x, два символи а і b зустрічаються на відстані p в тексті, і суфікс x довжини | uzv | має період довжини p, а значить не може перекрити обидва появи символів а і b у тексті. Найменший можливий зсув має довжину | u | - | v | (його ми і називаємо «турбо - зрушенням»).

1.5. Пошук підрядків за допомогою кінцевого автомата.

1.5.1. Структура автомата.

За визначенням, кінцевий автомат є п'ятірку М = (Q, q 0, A, , ), Де:
Q - кінцеве безліч станів;
q 0 Q - початковий стан;
А Q - кінцеве безліч допускають станів;
- Кінцевий вхідний алфавіт;
- Функція Q х Q, звана функцією переходів автомата.
Спочатку кінцевий автомат знаходиться в стані q 0. Потім він по черзі читає символи з вхідного рядка. Перебуваючи в стані q і читаючи символ а, автомат переходить в стан (Q, a). Якщо автомат знаходиться в стані q A говорять, що він допускає прочитану частина вхідного рядка. Якщо q А, то прочитана частина рядка відкинута.
З кінцевим станом М пов'язана функція , Звана функцією кінцевого стану, що визначається таким чином: є стан, в який прийде автомат (з початкового стану), прочитавши рядок w. Автомат допускає рядок w тоді і тільки тоді, коли А
Для кожного зразка Р можна побудувати кінцевий автомат, що шукає цей зразок у тексті. Першим кроком у побудові автомата, відповідного рядку-зразку Р [1 .. m], є побудова за Р допоміжної суфікс-функциии (як у алгоритмі КМП). Тепер визначимо кінцевий автомат, відповідно до моделі Р [1 .. m], наступним чином:
· Його безліч станів Q = {0,1 ,..., m}. Початковий стан q 0 = 0. Єдине допускає стан m;
· Функція переходів визначена співвідношенням (q - стан, - Символ): (Q, a) = (P q a). (1)
Пояснимо це співвідношення. Потрібно сконструювати автомат таким чином, щоб при його дії на рядок Т співвідношення
i) = i)
було інваріантом (тоді рівність i) = m буде рівносильно тому, що Р входить в Т зі зрушенням i - m, і автомат тим самим знайде всі допустимі зрушення). Однак у цьому випадку обчислення переходу за формулою (1) необхідно для підтримки істинності інваріанту, що випливає з теорем, наведених нижче. [3]
Теорема. Нехай q = (Х), де х - рядок. Тоді для будь-якого символу а має місце (Ха) = (P q a).
Теорема. Нехай - Функція кінцевого стану автомата для пошуку підрядка Р [1 .. m]. Якщо Т [1 .. n] - довільний текст, то i) = i) для i = 0,1 ,..., n. [14]
З викладеного випливає, що завдання пошуку підрядка складається з двох частин:
побудова автомата за зразком (визначення функції переходів для заданого зразка);
застосування цього автомата для пошуку входжень зразка в заданий текст.

1.5.2. Приклад побудови кінцевого автомата

Побудуємо кінцевий автомат, що допускає рядок ababaca. Оскільки довжина зразка m = 7 символів, то в автоматі буде m + 1 = 8 станів.
Знайдемо функцію переходів . Відповідно до визначення (1), (Q, a) = q а), де - Префікс-функція, а - довільний символ з алфавіту , Q - номер стану. Таким чином, необхідно для кожного префікса P q = P [0 .. q], q = 0 .. m зразка Р і для всіх символів а вхідного алфавіту знайти довжину максимального префікса Р, який буде суфіксом рядка Р q а. Довжина цього префікса і буде значенням функції переходів (Q, a). Якщо а = P [q + 1] (черговий символ тексту збігся з наступним символом зразка), то Р q а = Р q +1 та (Q, a) = q +1.
Такий випадок відповідає успішним етапам пошуку. Інакше, (Q, a) q. Наприклад, для префікса Р [0 .. 5] = ababa і символу b максимальним суфіксом рядка Р [0 .. 5] b = ababab, який одночасно є префіксом Р, буде abab. Його довжина дорівнює 4, тому значення функції переходів (5, b) = 4.
Запишемо побудовану таким чином функцію переходів у вигляді таблиці (Табл. 1):
0
1
2
3
4
5
6
7
a
1
1
3
1
5
1
7
1
b
0
2
0
4
0
4
0
2
c
0
0
0
0
0
6
0
0
Рядки відповідають вхідним символам, стовпці - станам автомата. Осередки, відповідні успішним етапам пошуку (вхідний символ збігається з наступним символом зразка), виділені сірим кольором.
Побудуємо за таблицею граф переходів автомата (Мал. 1), що розпізнає зразок ababaca. Перебуваючи в стані q і прочитавши черговий символ а, автомат переходить в стан (Q, a). Звернемо увагу, що його кістяк позначений символами зразка (ці переходи виділені жирними стрілками).
Рис. 1

Тут 0 - початковий стан, 7 - єдине допускає стан (затемнена). Якщо з вершини i у вершину j веде стрілка, позначена буквою а, то це означає, що (I, a) = j. Відзначимо, що переходи, для яких (I, a) = 0, на графі переходів для його спрощення не позначені. Жирні стрілки, що йдуть зліва направо, відповідають успішним етапам пошуку підрядка Р - наступний вхідний символ збігається з черговим символом зразка. Стрілки, що йдуть справа наліво, відповідають невдач - наступний вхідний символ відрізняється від чергового символу зразка.
Нижче наведено результат застосування автомата до тексту Т = abababacaba. Під кожним символом Т [г] записано стан автомата після прочитання цього символу (іншими словами, значення i)) (Табл. 2).

Знайдено одне входження зразка (починаючи з позиції 3). Знайдений зразок у тексті позначено сірим кольором. Чорним кольором позначено допускає стан автомата (стан з номером 7).

Частина 2. Експериментальний аналіз алгоритмів.

2.1. Суть експерименту.

Ми розглянули кілька алгоритмів, провели оцінку їх часової та ємнісної складності. Однак, як уже говорилося, дані критерії оцінки не дозволяють нам напевно сказати, який з алгоритмів буде швидше працювати. Тому, для додаткової оцінки проведемо їх експериментальний аналіз, тобто виміряємо час, за який алгоритм виконує конкретно поставлене завдання.
Є кілька текстових файлів, що містять 10000 записів види:
рядок
підрядок (наявна в цьому рядку)
місце входження
довжина підрядка
з різними максимальними довжинами рядків і підрядків.
Алфавітом є 66 російських великих і малих літер.
Нехай це будуть рядка довжиною не більше 10, 100, 250 символів.
Проведемо пошук підрядків в рядках для кожного з алгоритмів і виміряємо час роботи програми. При цьому будемо враховувати наступне:
· Строки попередньо завантажуємо в оперативну пам'ять (у вигляді масиву), причому час зчитування в масив не враховується. Передобробка (створення таблиць переходу) входить в загальний час.
· Кожен алгоритм запускається 5 разів, час вибирається найменше.
Стенд для експерименту.
Процесор Intel Pentium IV 2,66 Ггц
1024 Мб ОЗУ
Компілятор Borland Delphi Enterprise, version 6.0 (Build 6.163)
Фрагмент коду програми, що тестується наведемо в лістингу 7.
ref SHAPE \ * MERGEFORMAT

LoadFromFile ('C: \ String_250.txt');
{Відбувається завантаження в масив}
Tick: = GetTickCount;
{Запам'ятовуємо текцщее значення змінної Tick}
Poisk;
{Процедура в якій відбувається пошук 10000 разів}
Tick: = GetTickCount-Tick;
{Отримуємо різницю - час в мілісекундах}
WriteLn ('Za vremja', Tick, 'ms');

Зрозуміло, що такий вимір часу дасть нам дуже розпливчасті результати, оскільки безпосередньо залежить від характеристик і завантаження процесора. Тому під час проведення експерименту, відключалися всі сторонні та фонові програми, які не впливають на роботу програми. При запуску однієї і тієї ж задачі ми можемо отримати різний час, тому відбувається кілька запусків, з яких вибирається найкращий результат.

2.2. Результати та аналіз експерименту.

Експеримент проводився для чотирьох алгоритмів - представників класів алгоритмів. Так як всі алгоритми ставилися в однакові умови, то можна провести їх порівняльний аналіз. Зауважимо, що даний аналіз застосуємо тільки для даних параметрів пошуку, і за інших умов може відрізнятися.
Результати експерименту занесемо до таблиці (Табл. 3).
Алгоритм
Час виконання
Довжина ≤ 10
Довжина ≤ 100
Довжина ≤ 250
Послід. пошук
15
93
234
Алгоритм Рабіна
(Хеш - сума кодів)
15
63
93
КМП
5
30
50
БМ
31
31
32
Як і передбачалося, алгоритм Бойєра - Мура впорався з експериментальною завданням швидше за інших. Слід, однак, зауважити, що його ефективність зростає лише зі збільшенням довжини рядка і, відповідно, довжини зразка. Так при довжині рядка меншою або рівною 10 символів, він показав себе гірше, ніж послідовний пошук. Аналогічні результати показує і алгоритм КМП, як для коротких, так і для довгих слів. Його можна використовувати як універсальний, коли невідомі довжини рядка й зразка.
Алгоритм Рабіна, при його схожості з послідовним працює швидше, а його простота і малі трудовитрати на реалізацію, роблять його привабливим для використання у неспеціальних програмах.
Найгірший результат показав алгоритм послідовного пошуку. Як передбачалося лише при невеликому збільшенні довжини рядка, він працює в рази повільніше інших алгоритмів.
У даний експеримент не включений алгоритм пошуку за допомогою кінцевого автомата, тому що ми використовуємо алфавіт, що складається з 66 букв російського алфавіту, і побудований автомат був би занадто громіздкий. Ефективність цього алгоритму зростає при малій кількості букв в алфавіті.

Висновок.

Ми розглянули різні алгоритми пошуку підрядка в рядку, зробили їх аналіз. Результати можна представити в таблиці (Табл. 4).
Алгоритм
Час на перед. обробку
Середній час пошуку
Гірший час пошуку
Витрати пам'яті
Час роботи (мс) при довжині рядка ≤ 250
Примітки
Алгоритми засновані на алгоритмі послідовного пошуку
Алгоритм прямого пошуку
Ні
O ((m-n +1) * n +1) / 2
O ((m-n +1) * n +1)
Ні
234
Mалие трудовитрати на програму, мала ефективність.
Алгоритм Рабіна
Ні
O (m + n)
O ((m-n +1) * n +1)
Ні
93
Алгоритм Кнута-Морріса-Пратта
КМП
O (m)
O (n + m)
O (n + m)
O (m)
31
Універсальний алгоритм, якщо невідома довжина зразка
Алгоритм Бойєра-Мура
БМ
O (m + s)
O (n + m)
O (n * m)
O (m + s)
32
Алгоритми цієї групи найбільш ефективні в звичайних ситуаціях. Швидкодія підвищується при збільшенні зразка або алфавіту.
Виходячи з отриманих результатів, видно, що алгоритм Бойєра - Мура є провідним за всіма параметрами, здавалося б, знайдено найбільший ефективний алгоритм. Але, як показує експеримент, алгоритм Кнута - Моріса - Пратта, перевершує алгоритм БМ на невеликих довжинах зразка. Тому я не можу зробити висновок, що якийсь з алгоритмів є найоптимальнішим. Кожен алгоритм дозволяє ефективно діяти лише для свого класу завдань, про це ще говорять різні вузькоспрямовані поліпшення. Алгоритм пошуку підрядка в рядку слід вибирати тільки після точної постановки завдання, які повинна виконувати програма.
Зробивши такий висновок, ми виконали мета даної роботи, тому що для різних класів задач був виділений свій ефективний алгоритм.

Бібліографічний список.

1). Kurtz, St. Fundamental Algorithms For A Declarative Pattern Matching System [Текст]. - Bielefeld:. Universität Bielefeld, 1995. - 238 с.
2). Lecro, T. Exact string matching algorithms [Електронний ресурс]. Режим доступу http://algolist.manual.ru/
3). Ахметов І. Пошук підрядків за допомогою кінцевих автоматів [Текст]: Курсова робота .- З-П державний університет інформаційних технологій, механіки й оптики.
4). Ахо, Альфред Структура даних і алгоритми [Текст]. - М.: Видавничий дім «Вільямс», 2000. - 384 с.
5). Бєлоусов А. Дискретна математика [Текст]. - М.: Видавництво МГТУ ім. Н.Е. Баумана, 2001. - 744 с.
6). Брайан, К. Практика програмування [Текст] .- СПб:. Невський діалект, 2001. - 381 с.
7). Вірт, М. Алгоритми і структури даних [Текст] .- М:. Світ, 1989. - 360 с.
8). Гілл, Арт. Введення в теорію кінцевих автоматів [Текст]. - М., 1966. - 272 с.
9). Глушаков С. Програмування Web - сторінок [Текст]. - М.: ТОВ «Видавництво АСТ», 2003. - 387 с.
10). Кнут, Д. Мистецтво програмування на ЕОМ [Текст]: Том 3. - М:. Світ, 1978. - 356 с.
11). Матрос Д. Елементи абстрактної та комп'ютерної алгебри: Учеб. посібник для студ. педвузів [Текст]. - М.: Видавничий центр «Академія», 2004. - 240 с.
12). Успенський В. Теорія алгоритмів: основні відкриття та використання [Текст]. - М.: Наука, 1987. - 288 с.
13). Шень, А. Програмування: теореми і задачі [Текст]. - М.: Московський центр безперервної математичної освіти, 1995.
14). Кормен, Т. Алгоритми: побудова та аналіз [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест - М. МЦНМО, 2002. М. МЦНМО, 2002.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
116.6кб. | скачати


Схожі роботи:
Алгоритми пошуку підрядка в рядку
Алгоритми пошуку підрядка в рядку 2 лютого
Пошук підрядка в рядку за допомогою хеш-функції
Алгоритми сортування пошуку найкоротшого шляху в графі та пошуку покриття близького до найкоротшому
Алгоритми сортування пошуку найдовшого шляху в зваженому графі та пошуку покриття близького до найкоротшому
Алгоритми пошуку кістяка Прима та Крускала
Алгоритми пошуку найкоротших покриттів булевих матриць
Пошук зразка в рядку
Розробка модуля перевірки діапазону вихідних даних і знаходження номера першого символу в рядку
© Усі права захищені
написати до нас