Мастер класс. "Алгоритмы поиска"

else r:=s-1;

end;

if a[s]=b then write(s) {вывод результата}

else write('no');

Попутные вопросы:

• почему не будет работать этот алгоритм в неупорядоченном массиве?

• можно ли дихотомический поиск осуществить только в части массива?

Попутное задание:

• сколько итераций (шагов) потребуется для нахождения шаблона в упорядоченном массиве из 1000 элементов? А из 10000 элементов?

• оцените вычислительную ёмкость этого алгоритма (O(log₂n)).

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

Предварительные вопросы:

• что такое строка в Паскале?

• какой максимальный размер строки в Паскале может быть?

• есть ли в Паскале встроенные средства поиска подстроки? (есть, функция pos).

• недостаток функции pos? (она работает со строками не более 255 символов)

Алгоритм предназначен для поиска подстроки в строке. Этот алгоритм устраняет повторную обработку символов, которые уже ранее рассматривались (например, при использовании «классического» алгоритма поиска подстроки, это постоянно происходит).

Попутные вопросы:

• какова вычислительная ёмкость «классического» алгоритма поиска подстроки? (O(n*m), где n и m — длины строки и подстроки)

Суть алгоритма Боуера-Мура. Сначала в специальном буфере (d) записываем расстояния всех символов подстроки от конца. Например, в слове "проба" буква "п" будет иметь значение 4, "б" - 1, "а" - 5 (а не 0, т.е. равным длине подстроки); все остальные символы строки, не входящие в подстроку, также будут иметь значение длины подстроки (в нашем случае - 5). Затем сравниваем подстроку с очередным фрагментом строки. Сравнение начинаем с конца. Если какой-либо символ строки не совпадает с символом подстроки, то сдвигаем указатель строки на число, соответствующее граничному символу строки в буфере d. Проще говоря, пододвигаем под граничную букву строки такую же букву подстроки (если она есть). Заканчивается цикл, когда сравнение окажется успешным, или же когда закончится строка. По моему опыту, эффект начинает сказываться уже при длине строки примерно в сотню символов.

Заметим, что чем больше подстрока и чем меньше совпадений, тем эффективность алгоритма выше.

Итак, есть массив s типа char (строка) и массив p типа char (подстрока). n и m — длины строки и подстроки соответственно.

procedure boumur(var s,p:array of char;n:longint;m:integer;var k:longint);

{s-строка, p-подстрока, n,m - их длины, k-позиция подстроки в строке}

var i:longint; j:integer; c:char; {i,j-указ-ли в строке и подстроке}

d:array[char] of byte; {массив сдвигов}

begin

for c:=chr(0) to chr(255) do d[c]:=np; {заполнение массива d числом np}

for j:=0 to m-2 do d[p[j]]:=m-j-1; {занесение расстояния символов}

i:=m; {поиск с m, т.е.с конца подстроки}

repeat

j:=m; k:=i; {сравнение начинаем с конца}

repeat

dec(k); dec(j); {двигаемся назад}

until (jor(p[j]s[k]); {пока не совпадение или не конец подстроки}

i:=i+d[s[i-1]]; {сдвигаем i на знач-е символа из массива d}

until (jor(in); {выход если сравнилось или конец строки}

if jthen k:=k+2 else k:=0; {если подстроки нет, то k:=0}

end;

Попутные вопросы:

• всегда ли оправдано применение алгоритма Боуера-Мура для поиска подстроки? (нет)

• в каких случаях алгоритм Боуера-Мура более эффективен, а когда менее эффективен?

• какова вычислительная ёмкость этого алгоритма? (n/m).

• насколько алгоритм Боуера-Мура эффективнее «классического» алгоритма?

Обобщение

Создание эффективных алгоритмов — это не просто творческое проведение досуга или интеллектуальная забава. Создание эффективных алгоритмов это уже, по сути, – требование времени. Эффективный алгоритм позволяет решать более сложные задачи без увеличения мощности компьютера, т.е. даёт экономический эффект, порой значительный. А платим мы за это только силой ума.

Рассмотренные нами алгоритмы решают задачу поиска для разных видов данных. Алгоритмы разные, но преследуют одну и ту же цель. Что, помимо цели, ещё объединяет рассмотренные алгоритмы? (Это можно спросить у учеников).

Во-первых, необычный, нестандартный подход к решаемой задаче. Во-вторых, – изящество, некая алгоритмическая эстетика, которую надо почувствовать. Те самые милые хитрости, которые неожиданно (или ожидаемо) дают эффект. Эти алгоритмы просто красивы.

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

Творческое домашнее задание:

• Изменить «барьерный» алгоритм так, чтобы осуществлять поиск с конца.

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

• Составить программу замера времени выполнения поиска подстроки по алгоритму Боуера-Мура и «классическим» способом. Сравнить время.