Федеральне міністерство з освіти
Державна освітня установа вищої професійної освіти
В«Вятський державний гуманітарний університетВ»
Факультет інформатики
Кафедра інформатики і методики навчання інформатики
Курсова робота
Алгоритми пошуку підрядка в рядку
Виконав
студент 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, входження з найменшою довжиною свого лівого крила називають першим або головним входженням. Для позначення входження використовують позначення XY.
Приклад : слова hrf і fhr є підрядками слова abhrfhr, gfsfdgfro.
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 відповідно. Можна порівняти зі слов...
