Новости

Алгоритм Прямого поиска. Алгоритм Бойера-Мура

Работа добавлена:






Алгоритм Прямого поиска. Алгоритм Бойера-Мура на http://mirrorref.ru

Строка1 (количество знаков 1001) .

Подстрока1  (количество знаков 14) .

Строка 2(количество знаков 100 000).

Подстрока2 (количество знаков 100).

Алгоритм Прямого поиска.

Идея алгоритма:1. I=1,2. сравнить I-й символ массива T с первым символом массива W,3. совпадение → сравнить вторые символы и так далее,4. несовпадение → I:=I+1 и переход на пункт 2,Условие окончания алгоритма:1. подряд М сравнений удачны,2. I+M>N, то есть слово не найдено.Сложность алгоритма: Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).Недостатки алгоритма:1. высокая сложность — O(N*M), в худшем случае – Θ((N-M+1)*M);2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

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

Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером и Муром, считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

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

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

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

Пример. Пусть есть алфавит из пяти символов: a, b, c, d, e и надо найти вхождение образца “abbad” в строке “abeccacbadbabbad”. Следующие схемы иллюстрируют все этапы выполнения алгоритма. Таблица смещений будет выглядеть так.

Начало поиска.

Последний символ образца не совпадает с наложенным символом строки. Сдвигается образец вправо на 5 позиций:

Три символа образца совпали, а четвертый – нет. Сдвигается образец вправо на одну позицию:

Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигается образец на 2 позиции:

Еще раз сдвигается образец на 2 позиции:

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

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

Метод использует предобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки 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).

Алгоритм последовательного поиска и алгоритм КМП помимо нахождения самих строк считают, сколько символов совпало в процессе работы.

Алгоритм Рабина-Карпа (РК-поиск)

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.Пример. Пусть образец имеет вид W = 3 1 4 1 5Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …k1=37(mod 13) – вхождение образца,14157(mod 13) – холостое срабатывание.k2=67399Из равенства ki= kj (mod q) не следует, что ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W[1…m] и T[s+1…s+m] на самом деле.Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики. В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).Пример: Сколько холостых срабатываний k сделает алгоритм РК, если q= 11, 13, 17. Пусть W={2 6}26 mod 11=4 k =3 холостых срабатывания,26 mod 13=0 k =1 холостое срабатывание,26 mod 17=9 k =0 холостых срабатываний.Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.

Алгоритм Прямого поиска. Алгоритм Бойера-Мура на http://mirrorref.ru


Похожие рефераты, которые будут Вам интерестны.

1. Реферат Алгоритм поиска минимального и максимального элементов в массиве

2. Реферат Алгоритм поиска необходимой информации в электронном каталоге

3. Реферат Алгоритм жазу жолдарымен құрылымымен таныстыру. Алгоритм құруға үйрету

4. Реферат Алгоритм стиснення з втратами. Фрактальний алгоритм

5. Реферат IDEA (англ. International Data Encryption Algorithm, международный алгоритм шифрования данных) — симметричный блочный алгоритм шифрования данных

6. Реферат Алгоритм AES

7. Реферат Алгоритм Прима

8. Реферат Алгоритм Сугено

9. Реферат Алгоритм самообучения

10. Реферат Алгоритм Мамдани