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

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

скачати

Введення

Мета курсової роботи: Вивчити та проаналізувати алгоритми пошуку підрядка в рядку, і розглянути низку практичних завдань на дану тематику.

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

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

Звичайно, зараз функції пошуку інкапсульовані в багато мов програмування високого рівня, тому щоб знайти рядок у невеликому тексті використовується вбудована функція. Але якщо такого роду пошук є ключовим завданням програми, знати принципи організації функцій пошуку буде корисним. У готових підпрограмах далеко не завжди все написано кращим чином. По-перше, в стандартних функціях не завжди використовуються найефективніші алгоритми, а по-друге, цілком можливо, що знадобиться змінити стандартну поведінку цих функцій (наприклад, передбачити можливість пошуку за шаблоном). Нарешті, область застосування функції пошуку не обмежується одними лише текстовими редакторами. Слід відзначити використання алгоритмів пошуку при індексації сторінок пошуковим роботом, де актуальність інформації безпосередньо залежить від швидкості знаходження ключових слів у тексті 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, входження з найменшою довжиною свого лівого крила називають першим або головним змістом. Для позначення входження використовують позначення X Y.

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

У програмуванні поняття складності алгоритму пов'язано з використанням ресурсів комп'ютера: наскільки багато процесорного

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

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

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

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

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. Таким чином, перевіряється префікс попередньої підрядка, якщо ж той не підходить, то префікс її префікса, і т.д. Діючи так, знаходиться найбільший шуканий префікс. (Див. додаток 3).

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

Алгоритм послідовного пошуку та алгоритм КМП крім знаходження самих рядків вважають, скільки символів збіглося в процесі роботи. Реалізація цього алгоритму представлена ​​в додатку 4.

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

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

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

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

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

Приклад. Нехай є алфавіт з п'яти символів: a, b, c, d, e і треба знайти входження зразка "abbad" в рядку "abeccacbadbabbad". Наступні схеми ілюструють всі етапи виконання алгоритму. Таблиця зсувів буде виглядати так.

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

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

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

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

Ще раз зсувається зразок на 2 позиції:

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

Перш за все слід визначити тип даних «таблиця зсувів». Для кодової таблиці, що складається з 256 символів, визначення цього типу буде виглядати так:

Type

TBMTable = Array [0 .. 255] of Integer;

Реалізація процедури, що обчислює таблицю зміщень для зразка p, представлена ​​в додатку 5.

Тепер пишеться функція, яка здійснює пошук (див. Додаток 6).

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

Глава 2. Практична частина.

Дан деякий текст, в якому слід знайти фрагмент цього тексту.

Дану задачу можна інтерпретувати як пошук підрядка в рядку.

Це завдання я реалізував за допомогою алгоритму послідовного (прямого) пошуку. Програмний код завдання реалізував на мові програмування Turbo Pascal 7.1 і він представлений в додатку 7.

Опис роботи програми.

Після запуску програма запитує введення тексту:

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

Далі програма запитує введення рядка (підрядка) для пошуку:

Наприклад, вводимо фрагмент тексту: "алгоритм"

Після введення, програма шукає рядок в тексті, якщо рядок існує то програма виводить текст на екран, виділяє рядок червоним кольором і видає з якого символу починається рядок:

Якщо фрагмента немає в тексті, то програма видасть повідомлення про те, що цього рядка в тексті не існує:

Глава 3. Аналіз алгоритмів

У курсовій роботі я розглянув декілька алгоритмів. Була проведена оцінка їх часової та ємнісної складності. Експериментальний аналіз полягав у вимірі часу, за який алгоритм виконує конкретно поставлене завдання.

Завдання: Є кілька текстових файлів, що містять 10000 записів види:

  • рядок

  • підрядок (наявна в цьому рядку)

  • місце входження

  • довжина підрядка,

причому з різними максимальними довжинами рядків і підрядків.

Алфавіт кирилиці містить 32 літери, тому довжина рядка буде не більше 10, 100, 250 символів.

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

  • рядки попередньо завантажуємо в оперативну пам'ять (у вигляді масиву), причому час зчитування в масив не враховується. Передобробка (створення таблиць переходу) входить в загальний час.

  • кожен алгоритм запускається 5 разів, час вибирається найменше.

Експеримент проходив на ПК:

Процесор Intel Pentium IV 2,66 Ггц

1024 Мб ОЗУ

Компілятор Turbo Pascal 7.1

Фрагмент коду програми, що тестується наводиться в Додатку 8.

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

Експеримент проводився для чотирьох алгоритмів - представників класів алгоритмів. Так як всі алгоритми ставилися в однакові умови, то можна провести їх порівняльний аналіз. Зауважимо, що даний аналіз застосуємо тільки для даних параметрів пошуку, і за інших умов може відрізнятися.

Результати експерименту занесені в таблицю 1.

Алгоритм

Час виконання (мс)


Довжина ≤ 10

Довжина ≤ 100

Довжина ≤ 250

Послід. Пошук

15

93

234

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

15

63

93

КМП

5

30

50

БМ

31

31

32

З таблиці видно, що алгоритм Бойєра - Мура впорався з експериментальною завданням швидше за інших. Слід, однак, зауважити, що його ефективність зростає лише зі збільшенням довжини рядка і, відповідно, довжини зразка. Так при довжині рядка меншою або рівною 10 символів, він показав себе гірше, ніж послідовний пошук. Аналогічні результати показує і алгоритм КМП, як для коротких, так і для довгих слів. Його можна використовувати як універсальний, коли невідомі довжини рядка й зразка.

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

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

Висновок

У процесі виконання курсової роботи були розглянуті різні алгоритми пошуку підрядка в рядку та проведено їх порівняльний аналіз, результати якого представлені в таблиці 2 (див. додаток 9).

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

Тільки після цього етапу необхідно переходити до реалізації програмного коду.

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

Список використовуваної літератури:

1) Альсведе Р., Вегенер І. "Завдання пошуку", 1982р, Видавництво "Світ"

2). Ахо, Альфред Структура даних і алгоритми [Текст]. - М.: Видавничий дім «Вільямс», 2000. - 384 с.

3). Бєлоусов А. Дискретна математика [Текст]. - М.: Видавництво МГТУ ім. Н.Е. Баумана, 2001. - 744 с.

4). Брайан, К. Практика програмування [Текст] .- СПб:. Невський діалект, 2001. - 381 с.

5). Вірт, М. Алгоритми і структури даних [Текст] .- М:. Світ, 1989. - 360 с.

6) Кнут, Д. Мистецтво програмування на ЕОМ [Текст]: Том 3. - М:. Світ, 1978. - 356 с.

7). Кормен, Т. Алгоритми: побудова та аналіз [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест - М. МЦНМО, 2002. М. МЦНМО, 2002.

8). Успенський В. Теорія алгоритмів: основні відкриття та використання [Текст]. - М.: Наука, 1987. - 288 с.

9). Шень, А. Програмування: теореми і задачі [Текст]. - М.: Московський центр безперервної математичної освіти, 1995.

Електронні джерела.

1) http://www.ipkro.isu.ru/informat/methods/findsort/

2) http://www.delphikingdom.com/asp/viewitem.asp?catalogid=65

3) http://revolution.allbest.ru/programming/00013926_0.html

4) http://ric.uni-altai.ru/fundamental/pascal1/lab15/l15-teor.htm

5) http://www.rsdn.ru/article/alg/textsearch.xml

Додаток 1

Реалізація алгоритму послідовного пошуку

Додаток 2

Реалізація алгоритму Рабіна

Додаток 3

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

Знаходження найбільшого шуканого префікса.

Додаток 4

Реалізація алгоритму Кнута-Морріса-Пратта

Додаток 5

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

Реалізація процедури, що обчислює таблицю зміщень для зразка p.

Додаток 6

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

Функція, яка здійснює пошук.

Додаток 7

Реалізація програмного коду


Додаток 8

Фрагмент коду програми, що тестується

Додаток 9

Загальні результати з аналізів розглянутих алгоритмів


Примітки

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

Малі трудовитрати на програму, мала ефективність

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

Універсальний алгоритм, якщо невідома довжина зразка

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

Алгоритми цієї групи найбільш ефективні в звичайних ситуаціях. Швидкодія підвищується при збільшенні зразка або алфавіту.

Час роботи (мс) при довжині рядка ≤ 250


234

93


31


32

Витрати пам'яті


немає

немає


O (m)


O (m + s)

Гірший час пошуку


O ((m-n +1) * n +1)

O ((m-n +1) * n +1)


O (n + m)


O (n * m)

Середній час пошуку


O ((m-n +1) * n +1) / 2

O (n + m)


O (n + m)


O (n + m)

Час на перед. обробку


немає

немає


O (m)


O (m + s)

Алгоритм


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

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


КМП


БМ

5


Додати в блог або на сайт

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

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


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