ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 10

Тема: «Исследование методов поиска в тексте»

Цель: научиться выполнять поиск подстроки в строке прямым поиском, методом Кнута, Мориса и Пратта, методом Боуера и Мура.

Ход работы

Теоретические обоснования

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

Пусть задан массив Txt из N элементов, называемый текстом и массив Wrd из M элементов, называемый словом, причем 0 < M ≤ N. Описать их можно как строки.

Поиск слова обнаруживает первое вхождение Wrd в Txt. Это действие типично для любых систем обработки текстов, отсюда и очевидная заинтересованность в поиске эффективного алгоритма для этой задачи.

Прямой поиск

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

Эти «сдвиги» слова повторяются до тех пор, пока конец слова не достиг конца текста или не произошло полное совпадение символов слова с текстом (т. е. слово найдено).

Этот алгоритм работает достаточно эффективно, если допустить, что несовпадение пары символов происходит после незначительного количества сравнений во внутреннем цикле. При достаточно большом множестве символов это довольно частый случай. Можно предполагать, что для текстов, составленных из 128 символов, несовпадение будет обнаруживаться после одной или двух проверок. Тем не менее, в худшем случае алгоритм будет малоэффективен, так как его сложность будет пропорциональна

O((N – M)·M).

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

Приблизительно в 1970 году Д. Кнут, Д. Морис и В. Пратт изобрели алгоритм (КМП-алгоритм), фактически требующий только O(N) сравнений даже в самом плохом случае. Новый алгоритм основывается на том соображении, что после частичного совпадения начальной части слова с соответствующими символами текста фактически известна пройденная часть текста и можно «вычислить» некоторые сведения (на основе самого слова), с помощью которых затем быстро продвинуться по тексту.

Основным отличием КМП-алгоритма от алгоритма прямого поиска является выполнение сдвига слова не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Таким образом, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим.

Если j определяет позицию в слове, содержащую первый несовпадающий символ (как в алгоритме прямого поиска), то величина сдвига Shift определяется как j – LenSuff–1. Значение LenSuff определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j (суффикс), которая полностью совпадает с началом слова. LenSuff зависит только от слова и не зависит от текста. Для каждого j будет своя величина Shift, которую обозначим Shift j.

Приведенный пример поиска слова ABCABD показывает принцип работы такого алгоритма. Символы, подвергшиеся сравнению, здесь подчеркнуты. Обратите внимание: при каждом несовпадении пары символов слово сдвигается на переменную величину, и меньшие сдвиги не могут привести к полному совпадению.

Точный анализ КМП-алгоритма весьма сложен. Его изобретатели доказывают, что требуется порядка O(M + N) сравнений символов, что значительно лучше, чем O((N – M)·M) сравнений при прямом поиске.

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

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

Метод же, предложенный Р. Боуером и Д. Муром в 1975 году (БМ-алгоритм), не только улучшает обработку самого плохого случая, но дает выигрыш в промежуточных ситуациях.

БМ-алгоритм основывается на необычном соображении – сравнение символов начинается с конца слова, а не с начала. Как и в случае КМП-алгоритма, перед фактическим поиском на основе слова формируется некоторая таблица. Пусть для каждого символа x из алфавита величина Shift_x – расстояние от самого правого в слове вхождения x до правого конца слова. Представим себе, что обнаружено расхождение между словом и текстом, причем символ в тексте, который не совпал, есть x. В этом случае слово сразу же можно сдвинуть вправо так, чтобы самый правый символ слова, равный x, оказался бы в той же позиции, что и символ текста x. Этот сдвиг, скорее всего, будет на число позиций, большее единицы. Если несовпадающий символ текста x в слове вообще не встречается, то сдвиг становится даже больше: сдвигаем вправо так, чтобы ни один символ слова не накладывался на символ x.

Почти всегда, кроме специально построенных примеров, данный алгоритм требует значительно меньше O(N) сравнений. В самых же благоприятных обстоятельствах, когда последний символ слова всегда попадает на несовпадающий символ текста, число сравнений пропорционально O(N/M).

Авторы алгоритма приводят и несколько соображений по поводу дальнейших усовершенствований алгоритма. Одно из них – объединить приведенную только что стратегию, обеспечивающую большие сдвиги в случае несовпадения, со стратегией Кнута, Морриса и Пратта, допускающей «ощутимые» сдвиги при обнаружении совпадения (частичного). Такой метод требует двух таблиц, получаемых при пред трансляции: Shift' – только что упомянутая таблица, а Shift'' – таблица, соответствующая КМП-алгоритму. Из двух сдвигов выбирается больший. Дальнейшее обсуждение этого предмета приводить не будем, поскольку дополнительное усложнение формирования таблиц и самого поиска, возможно, не оправдает видимого выигрыша в производительности. Фактические дополнительные расходы будут высокими и неизвестно, приведут ли все эти ухищрения к выигрышу или проигрышу.

Задание. Дан текстовый файл с расширением txt. В нем много слов с определениями. Слово и его определение записано в одну строку. 

Т.е. так

слово – его определение

еще слово – его определение

Необходимо чтобы происходил ввод слова с клавиатуры, затем это слово проверялось по блокноту. Если слово в блокноте есть, то вывод всей строки (слово + определение), Если нет такого слова, то сообщение об отсутствии слова в базе. 

Решение задачи.

#include <iostream>

#include <windows.h>

#include <string.h>

#include <fstream>

using namespace std;

int main()

{

char word[256];

int count=0,i;

ifstream wer("dict.txt");

if(wer.fail())

    {

cout<<"Error!"<<endl;

return 1;

    }

while(!wer.eof())

    {

wer.getline(word,256);

count++;

    }

wer.close();

ifstream wer2("dict.txt");

char ** dict=new char*[count];

for(i=0;i<count;i++)

    {

dict[i]=new char[256];

wer2.getline(dict[i],256);

    }

wer2.close();

cout<<"Enter word: ";

cin>>word;

for(i=0;i<count;i++)

if(strstr(dict[i],word))

cout<<dict[i];

return 0;

}