Алгоритм послідовного (прямого) пошуку

Звіт

про виконання лабораторної роботи № 11

Тема:

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

З курсу: Теорія алгоритмів

 

Виконала:

ст. групи КН-23

Нарушинська О.О.

Прийняв:

Денисюк П.Ю.

 

Львів - 2011

Теоретичні відомості

Основні визначення

Алгоритими пошуку рядка (англ. string searching algorithms) — важливий клас рядкових алгоритмів, що намагаються знайти місце де один або декілька текстових рядків (зразків, англ. pattern) входять у довший рядок або текст.

Визначення. Рядок (слово) - це послідовність знаків (званих літерами) з деякого кінцевого безлічі, званого алфавітом.

Визначення. Довжина рядка - кількість знаків у рядку.Слова позначаються літерами латинського алфавіту, напр. 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 ₁ і Z _2, що Y = Z ₁ XZ _2. При цьому Z ₁ називається лівим, а Z ₂ - правим крилом підрядка. Підрядком може бути й саме слово. Іноді при цьому слово X називають входженням в слово Y. Серед всіх входжень слова X в слово Y, входження з найменшою довжиною свого лівого крила називають першим або головним змістом. Для позначення входження використовують позначення X Y.

Приклад: слова hrf і fhr є підстроками слова abhrfhr, gf sfdgfro.

У програмуванні поняття складності алгоритму пов'язано з використанням ресурсів комп'ютера: наскільки багато процесорного часу вимагає програма для свого виконання, наскільки багато при цьому витрачається пам'ять машини? Облік пам'яті зазвичай ведеться за обсягом даних і не береться до уваги пам'ять, що витрачається для запису команд програми. Час розраховується у відносних одиницях так, щоб ця оцінка, по можливості, була однаковою для машин з різною тактовою частотою.

Існує дві характеристики складності алгоритмів - тимчасова і емкостная.

Тимчасова складність буде обчислюватися в виконуваних командах: кількість арифметичних операцій, кількість порівнянь, пересилань (залежно від алгоритму). Ємнісна складність буде визначатися кількістю змінних, елементів масивів, елементів записів або просто кількістю байт.

Ефективність алгоритму також буде оцінюватися за допомогою підрахунку часу виконання алгоритмом конкретно поставленої задачі, тобто з допомогою експерименту, докладніше про це у розділі 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), алгоритм буде продовжувати порівнювати рядок, починаючи з наступного символу, хоча це однозначно не призведе до результату.

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

Алгоритм Рабіна представляє собою модифікацію лінійного алгоритму.

У слові A, довжина якого дорівнює m, шукається зразок X довжини n. Виріжемо "віконечко" розміром n воно рухається по вхідному слову. Чи збігається слово в "віконечку" із заданим зразком? Фіксується деяка числова функція на словах довжини n, тоді завдання зводиться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" та на зразку різні, то збігу немає. Тільки якщо значення однакові, необхідно перевіряти послідовно збіг по буквах.

Цей алгоритм виконує лінійний прохід по рядку (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 включно. Якщо буде виявлено збіг, то перевіряється посимвольно. Реалізація цього алгоритму представлена ​​у додатку 2.

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

Однак, проблема в тому, що шукана рядок може бути довгою, рядків в тексті теж вистачає. А так як кожному рядку потрібно зіставити унікальне число, то і чисел має бути багато, а стало бути, числа будуть великими (порядку D * n, де D - кількість різних символів), і працювати з ними буде так само незручно. Але який інтерес працювати тільки з короткими рядками і цифрами? Вище розглянутий алгоритм можна поліпшити.

Приклад (сімейства зручних функцій). Вибирається деяке число 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.4.Алгорітм Кнута - Морріса - Пратта (КМП)

Метод використовує предобработку шуканого рядка, а саме: на її основі створюється так звана префікс-функція. Суть цієї функції в знаходженні для кожної підрядка S [1.. i] рядка S найбільшою підрядка S [1.. j] (j <i), присутньої одночасно і на початку, і в кінці підрядка (як префікс і як суфікс). Наприклад, для підрядка abcHelloabc такий підрядком є abc (одночасно і префіксом, і суфіксом). Сенс префікс-функції в тому, що можна відкинути свідомо невірні варіанти, тобто якщо при пошуку збіглася підрядок abcHelloabc (наступний символ не збігся), то має сенс продовжувати перевірку продовжити пошук вже з четвертого символу (перші три і так співпадуть). Спочатку розглядаються деякі допоміжні затвердження. Для довільного слова 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.

Справедливо наступну пропозицію:

(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.

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

Наступне питання, на який варто відповісти: чому час роботи процедури лінійно, адже в ній присутній вкладений цикл? Ну, по-перше, присвоєння префікс-функції відбувається чітко m разів, решту часу змінюється мінлива k. Так як у циклі while вона зменшується (P [k] <k), але не стає менше 0, то зменшуватися вона може не частіше, ніж зростати. Змінна k зростає на 1 не більше m разів. Значить, мінлива k змінюється всього не більше 2m разів. Виходить, що час роботи всієї процедури є O (m).

Алгоритм Бойєра - Мура

Алгоритм Бойєра-Мура, розроблений двома вченими - Бойером і Муром, вважається найбільш швидким серед алгоритмів загального призначення, призначених для пошуку підрядка в рядку.

Найпростіший варіант алгоритму Бойєра-Мура складається з наступних кроків. На першому кроці будується таблиця зміщень для шуканого зразка. Процес побудови таблиці буде описано нижче. Далі поєднується початок рядка і зразка і починається перевірка з останнього символу зразка. Якщо останній символ зразка та відповідний йому при накладенні символ рядка не збігаються, зразок зрушується щодо рядка на величину, отриману з таблиці зміщень, і знову проводиться порівняння, починаючи з останнього символу зразка. Якщо ж символизбігаються, проводиться порівняння передостаннього символу зразка і т. д. Якщо всі символи зразка збіглися з накладеними символами рядки, значить знайшлася підрядок і пошук закінчено. Якщо ж якийсь (не останній) символ зразка не співпадає з відповідним символомрядка, зсувається зразок на один символ вправо і знову починається перевірку з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнуто кінець рядка.

Величина зрушення у разі неспівпадання останнього символу обчислюється виходячи з таких міркувань: зрушення зразка повинен бути мінімальним, таким, щоб не пропустити входження зразка в рядку. Якщо цей символ рядка зустрічається у зразку, зміщується зразок таким чином, щоб символ рядка збігся з найбільш правим входженням цього символу у зразку. Якщо ж зразок взагалі не містить цього символу, зсувається зразок на величину, що дорівнює його довжині, так що перший символ зразка накладається на наступний за перевіряється символ рядка.

Величина зміщення для кожного символу зразка залежить тільки від порядку символів у зразку, тому зсуву зручно обчислити наперед і зберігати у вигляді одновимірного масиву, де кожному символу алфавіту відповідає зміщення відносно останнього символу зразка.