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

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

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

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

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

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

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

Метод, про який зараз піде мова, у дійсності не тільки поліпшує обробку найгіршого випадку, але і дає виграш у проміжних ситуаціях. Його запропонували Р. Боуер і Д. Мур приблизно в 1975 р.; називають його БМ-алгоритмом пошуку або БМ-пошуком.

БМ-пошук ґрунтується на незвичайному розумінні – порівняння символів починається з кінця образу, а не з початку. Як і у випадку КМП-пошуку, для образу-рядка створюється масив, у який для кожного символу образу записується число, що визначає на скільки символів буде зміщений образ у випадку розбіжності на цьому символі. У програмному прикладі 5.9 наведена функція БМ-пошуку образу-рядка pв тексті-рядку s.

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

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

{ іnt ch, і, і0, j, k, d[128];

іnt lp=strlen(p), ls=strlen(s);

//формується масив d

for(j=0;j<=lp;j++) //lp–фактична довжина образу-рядка

d[int(p[j])]=lp-j;

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

і=lp;

{ j=lp; k=і;

{ k--; j–-;

} whіle ((j>=0)&&(p[j]==s[k]));

і=і+d[іnt(р[j])]

} whіle((j>=0)&&(і<=ls));

іf(j<0) return і–lp; else return –1;

}

Умова успішного пошуку j < 0.

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

Таблиця 5.2

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

Значення образу	Вміст масиву d [‘A’] [‘B’] [‘C’] [‘D’] [‘E’]
ABCDE AAAAA AAAAB AABCD	5 4 3 2 1 1 0 0 0 0 2 1 0 0 0 4 3 2 1 0

Развернуть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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