Введення Мета курсової роботи: Вивчити і проаналізувати алгоритми пошуку підрядка в рядку, і розглянути ряд практичних завдань на дану тематику.
Завдання курсової роботи: вивчити завдання пов'язані з проблемою пошуку підрядка в рядку, дати основні визначення; розглянути застосування різних алгоритмів пошуку підрядка в рядку на практиці; написати програмний код, що реалізовує один з алгоритмів пошуку підрядка в рядку.
Тема моєї курсової роботи є актуальною і на сьогоднішній день, ті, кому доводиться часто працювати з текстовими редакторами, знають ціну функції знаходження потрібних слів в тексті, істотно полегшує редагування документів і пошук потрібної інформації. Дійсно, сучасні програми обробки тексту привчили нас до такої зручної можливості, як пошук і заміна фрагментів, і якщо розробляти подібну програму, користувач має право очікувати, що в його розпорядженні будуть відповідні команди.
Звичайно, зараз функції пошуку інкапсульовані в багато мов програмування високого рівня, тому щоб знайти рядок у невеликому тексті використовується вбудована функція. Але якщо такого роду пошук є ключовим завданням програми, знати принципи організації функцій пошуку буде корисним. У готових підпрограмах далеко не завжди все написано кращим чином. По-перше, в стандартних функціях не завжди використовуються найефективніші алгоритми, а по-друге, цілком можливо, що знадобиться змінити стандартну поведінку цих функцій (наприклад, передбачити можливість пошуку за шаблоном). Нарешті, область застосування функції пошуку не обмежується одними лише текстовими редакторами. Слід відзначити використання алгоритмів пошуку при індексації сторінок пошуковим роботом, де актуальність інформації безпосередньо залежить від швидкості знаходження ключових слів у тексті html. Робота найпростішого спам-фільтра, полягає в знаходженні в тексті листа фраз таких, як В«Мільйон за годинуВ» або В«Розкрутка сайтуВ». Це все говорить про актуальності проблеми пошуку.
Робота містить три основних глави. У першій будуть розглянуті алгоритми, їх теоретичне обгрунтування, алгоритмічна модель, буде проведена спроба їх класифікації. У другому розділі буде розглянута практична частина курсової роботи. Реалізовано програмний код пошуку підрядка в рядку за допомогою алгоритму послідовного пошуку. У третьому розділі роботи будуть наведені дані про практичному застосуванні алгоритмів. У висновку буде зроблено висновок про найбільш ефективному (з тимчасової точки зору) алгоритмі.
Глава 1. Теоретичні відомості про алгоритми пошуку підрядка в рядку
1.1. Основні поняття
Визначення. Рядок (Слово) - це послідовність знаків (званих літерами) з деякого кінцевого безлічі, званого алфавітом.
Визначення. Довжина рядки - кількість знаків у рядку.
Слова позначаються літерами латинського алфавіту, напр. X = x [1] x [2] ... x [n] - слово довгою n, де x [i] (i-ая буква слова) належить алфавітом. Lentgh (X) == n - позначення довжини рядка.
Визначення. Слово не містить жодної букви називається порожнім.
Пусте слово зазвичай позначається буквою L. Length (L) = 0.
Визначення. Слово X називається префіксом слова Y, якщо є таке слово Z, що Y = XZ. Причому саме слово є префіксом для самого себе (тому знайдеться нульове слово L, що X = LX.
Приклад: слово ab є префіксом слова abcfa.
Визначення. Слово X називається суфіксом слова Y, якщо є таке слово Z, що Y = ZX. Аналогічно, слово є суфіксом самого себе.
Приклад: слово bfg є суфіксом слова vsenfbfg.
Визначення. Слово X називається підрядком рядки Y, якщо знайдуться такі рядки Z 1 і Z 2 , що Y = Z 1 XZ 2 . При цьому Z 1 називається лівим, а Z 2 - правим крилом підрядка. Підрядком може бути і саме слово. Іноді при цьому слово X називають входженням в слово Y. Серед всіх входжень слова X в слово Y, входження з найменшою довжиною свого лівого крила називають першим або головним входженням. Для позначення входження використовують позначення XY.
Приклад: слова hrf і fhr є підрядками слова abhrfhr, gfsfdgfro.
У програмуванні поняття складності алгоритму пов'язано з використанням ресурсів комп'ютера: наскільки багато процесорного
часу вимагає програма для свого виконання, наскільки багато при цьому витрачається пам'ять машини? Облік пам'яті зазвичай ведеться за обсягом даних і не береться до уваги пам'ять, витрачається для запису команд програми. Час розраховується у відносних одиницях так, щоб ця оцінка, по можливості, була однаковою для машин з різної тактовою частотою.
Існує дві характеристики складності алгоритмів - тимчасова і ємнісна.
Часова складність буде підраховуватися у виконуваних командах: кількість арифметичних операцій, кількість порівнянь, пересилань (в залежності від алгоритму). Ємнісна складність буде визначатися кількістю змінних, елементів масивів, елементів записів або просто кількістю байт.
Ефективність алгоритму також буде оцінюватися за допомогою підрахунку часу виконання алгоритмом конкретно поставленої задачі, тобто за допомогою експерименту, докладніше про це в главі 2 даної роботи.
1.2. Алгоритм послідовного (прямого) пошуку
Найочевидніший алгоритм. Позначення S - слово, в якому шукається зразок X. Нехай m і n - довжини слів S і X відповідно. Можна порівняти зі словом X всі подслова S, які починаються з позицій 1,2, ..., m-n +1 в слові S; у випадку рівності виводиться відповідна позиція. Реалізація цього алгоритму представлена ​​в додатку 1.
Це не ефективний алгоритм тому максимальне, кількість порівнянь буде одно O ((m-n +1) * n +1), хоча більшість з них насправді зайві. Оцінимо швидкість роботи цього програмного коду. В ній присутні два цикли (один вкладений), час роботи зовнішнього більшим ступенем залежить від n, а внутрішній в гіршому випадку робить m операцій. Таким чином, час роботи всього алгоритму є O ((n-m +1) m). Для маленьких рядків пошук пропрацює швидко, але якщо в якомусь багатомегабайтного файлу буде шукатися послідовність довжиною 100 Кб, то доведеться чекати ну дуже довго. Втім багатьом вистачає і цього. Наприклад, знайшовши рядок aabc і виявивши невідповідність в четвертому символі (співпало тільки aab), алгоритм буде продовжувати порівнювати рядок, починаючи з наступного символу, хоча це однозначно не призведе до результату.
1.3. А лгорітм Рабіна
Алгоритм Рабіна являє собою модифікацію лінійного алгоритму.
У слові A, довжина якого дорівнює m, шукається зразок X довжини n. Виріжемо "віконечко" розміром n воно рухається по вхідному слову. Чи збігається слово в "віконечку" із заданим зразком? Фіксується деяка числова функція на словах довжини n, тоді задача зводиться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" та на зразку різні, то збігу немає. Тільки якщо значення однакові, потрібно перевіряти послідовно збіг по буквах.
Цей алгоритм виконує лінійний прохід по рядку (n кроків) і лінійний прохід по всьому тексту (m кроків), стало бути, загальний час роботи є O (n + m). При цьому не враховується тимчасова складність обчислення хеш-функції, так як, суть алгоритму в тому і полягає, щоб дана функція була настільки легко обчислюється, що її робота не впливала на загальну роботу алгоритму. Тоді, час роботи алгоритму лінійно залежить від розміру рядка і тексту, стало бути програма працює швидко. Адже замість того, щоб перевіряти кожну позицію на предмет відповідності зі зразком, можна перевіряти тільки ті, які В«нагадуютьВ» зразок. Отже, для того, щоб легко встановлювати явна невідповідність, буде використовуватися функція, яка повинна: ​​
1. Легко обчислюватися.
2. Як можна краще роз...
