17. Алгоритмы поиска

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

Рассмотрим алгоритм поиска на примере программы – словаря. Пусть в ЭВМ введена таблица-словарь из n русских и английских слов вида табл. 5.

Словарь Таблица 5

Русское слово	Английское слово
программа оператор метка . . .	program statement lable . . .

Размер таблицы фиксирован и известен.

Таблица должна храниться в виде двух массивов слов, причем русскому слову с номером 3 ("метка") соответствует английское с таким же номером ("lable") и т.д.

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

Простейший алгоритм поиска - линейный. При этом эталонный массив просматривается последовательно от первого до последнего элемента. Наиболее сложный случай, когда слова нет в словаре (не найдено). Суждение об этом можно сделать только по окончании просмотра всего массива.

17.1. Алгоритм линейного поиска

В соответствии с этим алгоритмом, как отмечалось выше, эталонный массив просматривается последовательно от первого до последнего элемента. Наиболее сложным является случай, когда слова нет в словаре (не найдено).

Общий алгоритм поиска можно описать так.

1. Ввести два исходных массива слов (таблицу-словарь).

2. Повторять

ввести новое слово и вывести русское

пока не надоест.

3. Закончить.

Пусть для окончания работы с программой (когда переводить надоело) необходимо ввести слово "End".

Уточненный алгоритм будет таким.

1. Ввести два исходных массива слов (таблицу-словарь).

2. Повторять

2.2.1. Ввести Слово (для перевода);

2.2.2. Номер Русского_Слова (Num):= 0;

2.2.3. Для номера Английского_Слова (i) от 1 до n выполнить

Если Слово = Английское_Слово[i] то

номер Русского_Слова (Num):= i;

2.2.4. Если номер Русского_Слова (Num) = 0 то

вывести: 'Введенного слова нет в словаре',

Иначе

вывести Русское_Слово[Num].

пока не будет Слово = 'End'.

3. Закончить.

Обозначим:

Rsl - массив русских слов в словаре

Asl - массив английских слов в словаре

Slovo - слово для перевода.

Программа линейного поиска будет иметь вид

Program Poisk;

Const

n = 100;

dl = 15; { длина слова }

Var

Rsl, Asl : Array[1..n] of string[dl];

Slovo : String[dl];

i, Num : Integer;

BEGIN

Writeln('Введите словарь');

For i := 1 to n do

Begin

ReadLn(Rsl[i]);

ReadLn(Asl[i]);

End;

{ перевод }

Repeat

WriteLn('Введите слово для перевода');

ReadLn(Slovo);

Num:=0; { номер слова в словаре }

For i := 1 to n do

If Slovo = Asl[i] then

Num := i;

If Num = 0 then

Writeln('Нет такого слова в словаре')

Else

Writeln(Rsl[Num]);

Until Slovo='End';

Writeln('Работа окончена. Нажмите клавишу ENTER');

Readln;

END.

Основной недостаток алгоритма линейного поиска – большое время. При использовании оператора For для поиска ВСЕГДА выполняется ровно n операций сравнения, не зависимо от того, найдено слово или нет. Поэтому программа, обнаружив слово в начале словаря, продолжает его просмотр до конца, т.е. выполняет бесполезную работу. Время поиска может быть существенно сокращено, если обеспечить его прекращение, когда слово найдено. При равномерном распределении элементов в таблице эталаонов (слов в словаре) среднее время поиска может стать пропорциональным величине n / 2.

Этого можно достичь, изменив пункт 2.2 в рассмотренном выше алгоритме следующим образом.

Ускорение линейного поиска

2.2. Повторять

2.2.1. Ввести Слово

2.2.2. Номер Русского_Слова := 0

2.2.3. Номер в таблице i := 1

2.2.4. Пока (Num=0) и (i<=n) выполнить

2.2.4.1. Если Слово = Английское_слово[i], То Num := i

2.2.4.2. i := i+1

2.2.5.Если Num = 0, ТО вывести "не знаю",

Иначе вывести русское слово[Num];

Соответствующий фрагмент программы приведен ниже.

{ Ускорение линейного поиска }

Repeat

WriteLn('Введите слово для перевода');

ReadLn(Slovo);

Num := 0;

i := 1;

While (Num=0) And (i<=n) do

Begin

If Slovo = Asl[i] then

Num := i;

i:=i+1;

End;

If Num = 0 then

Writeln('Нет такого слова в словаре')

Else

Writeln(Rsl[Num]);

End;

Если при программировании используется Турбо Паскаль 7.0, то прервать выполнение цикла For после совпадения введенного слова со словом в словаре можно более изящно, чем в приведенном выше примере. Для этого можно использовать процедуру Break, которая специально предназначена для досрочного выхода из циклов For, While и Repeat.

Соответствующий фрагмент программы приведен ниже, где добавленные операторы выделены.

. . . . . . . . . .

For i := 1 to n do

If Slovo = Asl[i] then

Begin

Num := i;

Break;

End;

If Num = 0 then

Writeln('Нет такого слова в словаре')

Else

Writeln(Rsl[Num]);

End;