рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
КМП-алгоритм пошуку рядка в тексті

Реферат Курсовая Конспект

Выберите учебное заведение

КМП-алгоритм пошуку рядка в тексті

КМП-алгоритм пошуку рядка в тексті - раздел Образование, ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ У 1970 Р. Д. Кнут, Дж. Морріс І В. Пратт Запропонували Алгори...

У 1970 р. Д. Кнут, Дж. Морріс і В. Пратт запропонували алгоритм пошуку рядка в тексті, так званий КМП-алгоритм або КМП-пошук, фактично потребуючий тільки N порівнянь, навіть у найгіршому випадку.

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

Рядок (текст)	. . .	A	B	C	D	E	F	A	. . .
Образ		A	B	C	D	E	A
Зсув образа						A	B	. . .

Рис. 5.1. Зсув образу ABCDEА

Після розбіжності символів "F" і "A" продовжити порівняння можна, змістивши образ на п’ять позицій. Очевидно, що зсув образу-рядка залежить від вмісту самого рядка. Так в прикладі рис. 5.2 після розбіжності символів ”В” та ”А” можна продовжити порівняння, змістивши образ тільки на один символ.

Рядок (текст)	. . .	A	A	A	A	A	А	В	. . .
Образ		A	A	A	A	A	B
Зсув образу		A	A	A	A	A	B

Рис. 5.2. Зсув образа AAAAAB

Оскільки зміщення образу, залежить тільки від самого образу, Д. Кнут, Дж. Морріс і В. Пратт запропонували до початку пошуку формувати масив d, у якому записувати значення зсувів для кожного символу образу-рядка, якщо розбіжність буде саме на цьому символі. У програмному прикладі 5.8 наведений приклад пошуку згідно з алгоритмом КМП.

{===== Програмний приклад 5.8 =====}

іnt KMPSearch (char s[N], char p[M])

{ іnt d[M], lp=strlen(p), ls=strlen(s);

//формування масиву d

іnt j=0; k=–1; d[0]=–1;

whіle (j<lp) //lp – фактична довжина образу

{ whіle((k>=0)&&(p[j]!=p[k]))k=d[k];

j++;k++;

іf (p[j]==p[k]) d[j]=d[k]; else d[j]=k;

}

//алгоритм пошуку

whіle((j<lp)&&(і<ls)) //ls – фактична довжина тексту

{ whіle((j>=0)&&(s[і]!=p[j])) j=d[j];

і++; j++;

}

іf (j==lp) return і–lp; else return –1;

}

Якщо (j == lp), отже образ у тексті знайдений, починаючи з номера і – lp.

В таблиці 5.1 наведено приклади значень образу-рядка і масиву d.

Таблиця 5.1

Образ і відповідний йому вмісту масиву

Значення образу	Вміст масиву d
ABCDE AAAAA AAAAB AABCD	-1 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 1 0 0

Аналіз КМП-пошуку. Точний аналіз КМП-пошуку, як і сам його алгоритм, дуже складний. Автори доводять, що в середньому потрібно порядка М+N порівнянь символів, що значно краще, ніж М*N порівнянь у алгоритмі прямого пошуку.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ

ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ... НАД СТАТИЧНИМИ І СТРУКТУРАМИ R...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: КМП-алгоритм пошуку рядка в тексті

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

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

Прямий пошук рядка в тексті
Часто доводиться зіштовхуватися зі специфічним пошуком, так названим пошуком рядка в тексті. Його можна визначити таким способом. Нехай заданий масив s з

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

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

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

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

Проблема колізій у хешованих таблицях
Колізії (друга назва - конфлікт) – основна проблема для хешованих таблиць. Вдало підібрана функція хешування може мінімізувати число колізій, але не може гарантувати їхньої повної в

Сортування
Для самого загального випадку задача сортування може формулюватися так: мається деяка неупорядкована вхідна множина ключів, необхідно одержати вихідну множину тих же ключів, упорядк

Сортування вибіркою
Сортування простою вибіркою. Даний метод реалізує практично "дослівно" сформульовану вище стратегію вибірки. Порядок алгоритму простої вибірки – O(N2

Сортування включенням
Сортування простими вставками. Цей метод – "дослівна" реалізація стратегії включення. У програмному прикладі 5.19 наведена підпрограма сортування простими вставками.

Сортування розподілом
Порозрядне цифрове сортування. Алгоритм вимагає представлення ключів сортованої послідовності у вигляді чисел у деякій системі обчислення P. Число

Сортування злиттям
Алгоритми сортувань злиттям, як правило, мають порядок O(N*log(N)), але відрізняються від інших алгоритмів більшою складністю і вимагають великого числа пересилань. Алгоритми злиття

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