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

Суть данного алгоритма иллюстрируется рамкой длины 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;

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

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

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

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;

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

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;

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

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

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

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

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

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

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

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

· образование слова вида (B₁B₂… B_s)^k на основе ввода числа k и слова B₁B₂… B_s.

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

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

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

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

4.3. Y=aaaaa и X=(aaaaab)^h, h = 1, … ,10⁶+1 с шагом 10⁴ (нарисовать графики функций T₁(h) и T₂(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;

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(n²), однако, в среднем быстрая сортировка выполняется за время O(n×log n).

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

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

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

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

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

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

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

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

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

Задание.

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

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