Федеральне міністерство за освітою
Державна освітня установа вищої професійної освіти
«Вятський державний гуманітарний університет»
Факультет інформатики
Кафедра інформатики і методики
навчання інформатики Курсова робота Алгоритми пошуку
підрядка в рядку
Виконав
студент 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 Рядок, її довжина, підрядок.
Тут ми наводимо ряд визначень, які будемо використовувати у викладі матеріалу [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]
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)
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);
|
|