Наивный алгоритм поиска фрагмента в тексте — КиберПедия 

Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...

История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...

Наивный алгоритм поиска фрагмента в тексте

2017-12-11 248
Наивный алгоритм поиска фрагмента в тексте 0.00 из 5.00 0 оценок
Заказать работу

Суть данного алгоритма иллюстрируется рамкой длины n, движущейся по слову X. Если фрагмент слова X, находящийся в рамке, совпадает со словом Y, это означает, что очередное вхождение слова Y в X найдено.

procedure SFT_TRIVIAL(X; m; Y; n; var f);

begin

for i:= 1 to n-1 do f[i]:= 0;

for i:= n to m do begin

s:= 1;

while (Y[s] =X[i-(n-s)]) &(s<n) do s:= s+1;

if (s=n)& (Y[n] =X[i]) then f[i]:= n else f[i]:= 0;

end;

end;

 

Временная сложность наивного алгоритма есть O(n×m).

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

В общем виде алгоритм Кнута-Морриса-Пратта (см. [4], [5]) строит функцию откатов fY: {1, 2, …,n}®{0, 1, 2, …, n-1} для поданного на его вход слова Y = Y1 Y2 … Yn. Таким образом, fY[i] является длиной наибольшего собственного суффикса слова Y = Y1 Y2 Yn, который является также и его префиксом.

 

procedure KMP(Y; n; var fY);

begin

i:= 1; fY[1]:= 0;

while i<n do begin

j:= fY[i];

while (Y[j+1] ¹ Y[i+1]) &(j>0) do j:= fY[j];

if Y[j+1] = Y[i+1] then f[i+1]:= j+1 else f[i+1]:= 0;

i:= i+1;

end;

end;

 

Тогда исходную задачу поиска всех вхождений слова Y = Y1 Y2 … Yn в слово (текст) X = X1 X2 … Xm решит построение функции откатов fZ для слова Z=Y#X, где # является произвольной буквой, не принадлежащей алфавиту A. В этом случае искомую функцию f можно найти, положив f[i]=fZ[i+n+1], i = 1, …, m. Сохраняя неизменной суть данного построения функции f, удается организовать его так, чтобы не было необходимости вводить в алфавит новую букву. Таким образом, алгоритм Кнута-Морриса-Пратта поиска всех вхождений слова Y=Y1 Y2 … Yn в X=X1 X2 … Xm можно представить в следующем виде.

 

procedure SFT_KMP(X; m; Y; n; var f);

begin

KMP(Y, n, fY);

i:= 1; if Y[1]=X[1] then f[1]:= 1 else f[1]:= 0;

while i<m do begin

j:= f[i];

if j=n then j:= fY[j];

while (Y[j+1] ¹ X[i+1]) & (j>0) do j:= fY[j];

if Y[j+1] = X[i+1] then f[i+1]:= j+1 else f[i+1]:= 0;

i:= i+1;

end;

end;

 

Временная сложность алгоритма Кнута-Морриса-Пратта есть O(n+m).

Задания для лабораторной работы № 4

1. Написать программу, реализующую тривиальный алгоритм и алгоритм Кнута-Морриса-Пратта поиска фрагмента в тексте, основываясь соответственно на псевдокодах процедур SFT_TRIVIAL и SFT_KMP.

2. Написать программу, реализующую оба алгоритма, для проведения экспериментов, в которых можно выбирать:

· количество букв в алфавите,

· способ независимого друг от друга задания слов X и Y из числа следующих:

· непосредственный ввод слова,

· образование слова выбранной длины, составленного из выбранных букв алфавита, встречающихся равновероятно,

· образование слова вида (B1 B2 … Bs)k на основе ввода числа k и слова B1B2 … Bs.

3. Выходом данной программы должно быть время работы T1 тривиального алгоритма и время работы T2 алгоритма Кнута-Морриса-Пратта в секундах.

4. Провести эксперименты на основе следующих данных:

4.1. Y=(ab)k и X=(ab)1000*k, k = 1, …,1001 с шагом 10 (нарисовать графики функций T1(k) и T2(k));

4.2. A={a,b}, Y=(a)m, слово X состоит из 106+1 букв алфавита A, встречающихся равновероятно, m = 1, …,106+1 с шагом 104 (нарисовать графики функций T1(m) и T2(m));

4.3. Y=aaaaa и X=(aaaaab)h, h = 1, …,106+1 с шагом 104 (нарисовать графики функций T1(h) и T2(h)).

5. Сформулировать и обосновать (на основе псевдокодов алгоритмов и практических данных, для получения которых можно провести дополнительные эксперименты) вывод о том, в каких случаях целесообразно применять тривиальный алгоритм, а в каких ― алгоритм Кнута-Морриса-Пратта.

Сортировка

Постановка задачи

Упорядочить массив a[1..n] по неубыванию в соответствии с линейным порядком (£), заданным на элементах данного массива, путем перестановки его элементов. (Отношение строгого порядка (<), как обычно, определяется следующим образом: b<c, если b£c и b ≠ c.)

Сортировка с помощью d-кучи

Реализация алгоритма сортировки с помощью d-кучи (см. [1], [5]) массива a длины n осуществляется процедурой SORT_D(a, n). При этом к моменту выполнения последнего for-цикла массив a был упорядочен по невозрастанию, а после его исполнения упорядочивается по неубыванию.

В данной задаче массивом ключей d-кучи является массив a, массив имен и сами имена элементов не используются, поэтому из псевдокодов всех операций с d-кучей следует выбросить все части кода для работы с именами элементов и массивом имен.

 

procedure SORT_D(var a; n,d);

begin

ОБРАЗОВАTЬ_ОЧЕРЕДЬ(a,n,d);

nq:= n; while nq>1 do ИЗЪЯТИЕ_МИНИМУМА (a1, a, n, d);

for i:= 1 to (n mod 2) do a[i]Ûa[n-i+1];

end;

 

Временная сложность сортировки с помощью d–кучи, где d³2, есть O(n×log n).

Быстрая сортировка

Быстрая сортировка (см. [1]) относится к типу алгоритмов “разделяй и властвуй”. Данный алгоритм, сортирующий массив a[1..n] по неубыванию, представлен процедурой SORT_QUICK(a, 1, n). Операция РАЗДЕЛЯЙ(a, i, j, i1) путем перестановки элементов массива a изменяет его так, чтобы a[i], …, a[i1-1] ≤ a[i1] ≤ a[i1+1], …, a[j], и одновременно определяет число i1.

 

procedure SORT_QUICK (var a, i, j);

begin

if i < j then begin

РАЗДЕЛЯЙ (a, i, j, i1);

SORT_QUICK (a, i, i1-1); SORT_QUICK (a, i1+1, j);

end;

end;

 

procedure РАЗДЕЛЯЙ (var a, i, j, var i1);

begin

k:= (i+j)mod(2); b:= a[k];

i1:= i; j1:= j;

repeat

while a[j1] < b & j1 > i do j1:= j1-1;

while a[i1] > b & i1 <j do i1:= i1+1;

if i1 <= j1 then begin

a[i1]Ûa[j1]; i1:= i1+1; j1:= j1-1;

end;

until i1 > j1;

end;

 

Временная сложность быстрой сортировки n элементного массива оценивается сверху величиной O(n2), однако, в среднем быстрая сортировка выполняется за время O(n×log n).

Задания для лабораторной работы № 5

Предлагается попарное сравнение различных алгоритмов сортировки массива, состоящего из натуральных чисел.

Варианты выбора пары алгоритмов A и B для сравнения:

Вариант d=2, …, 101

· А - сортировка d-кучей,

· В - сортировка (d+1)-кучей;

Вариант d=102, …., 200

· А - сортировка (d-100)-кучей,

· В - быстрая сортировка.

 

Задание.

1. Написать программу, реализующую алгоритм А и алгоритм В.

2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:

· количество n элементов в исходном массиве a,

· верхнюю q и нижнюю w границы для значений элементов массива,

· заполнение массива a:

· псевдослучайное,

· автоматическое по неубыванию,

· автоматическое по невозрастанию.

Выходом данной программы должно быть время работы ТА алгоритма А и время работы ТВ алгоритма В в секундах.

3. Провести эксперименты на основе следующих данных:

3.1. q=1, w=109, n=1, …,106+1 с шагом 104, заполнение массива a:

· псевдослучайное,

· по возрастанию,

· по убыванию

(нарисовать графики функций TА(n) и ТВ(n) для всех трех случаев).

3.2. q =1, w=1, …,100 с шагом 1, n=106, заполнение массива a:

· псевдослучайное,

· по возрастанию,

· по убыванию.

(нарисовать графики функций TА(w) и ТВ(w) для всех трех случаев),

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


Поделиться с друзьями:

История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.027 с.