Поиск сравнением с образцом

 

 

 

 

 

 

Введение

4

1 Описание и анализ  поставленной задачи

5

2 Анализ метода решения  задачи поиска подстроки в строке

6

2.1 Анализ алгоритма SF

6

2.2 Анализ алгоритма Боуэра-Мура

6

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

9

3 Анализ и выбор структур  данных

11

4 Проектирование и реализация программного средства

12

5 Оценка эффективности

15

Заключение 

18

Список литературы

19

Приложение А Листинг  программы

18

   




Содержание

 

 

Введение 

Поиск информации  – одно из основных использований компьютера. Одна из простейших задач поиска информации – поиск точно заданной подстроки  в строке. Тем не менее, эта задача чрезвычайно важна – она применяется  в текстовых редакторах, СУБД, поисковых  машинах…

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

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

    1. Проанализировать методы решения задачи;
    2. Проанализировать алгоритмы поиска подстроки в строке;
    3. Проанализировать структуры данных и выбрать необходимые;
    4. Спроектировать и проанализировать программное средство;
    5. Оценить эффективность реализованных алгоритмов поиска.

1 Описание и  анализ поставленной задачи

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т  и слово (или образ) W. Необходимо найти первое вхождение этого  слова в указанном тексте. Это  действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного  алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}).

Наиболее типичным приложением  такой задачи является документальный поиск: задан фонд документов, состоящих  из последовательности библиографических  ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей  ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой  запрос можно трактовать следующим  образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан  массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск  строки обнаруживает первое вхождение W в Т, результатом будем считать  индекс i, указывающий на первое с  начала строки (с начала массива  Т) совпадение с образом (словом).

Пример. Требуется найти  все вхождения образца W = abaa в  текст T=abcabaabcabca.

Рисунок 1 – Пример сравнения

Образец входит в текст  только один раз, со сдвигом S=3, индекс i=4.

 

2 Анализ метода  решения задачи поиска подстроки в строке

2.1 Анализ алгоритма  SF

Самый очевидный алгоритм. Обозначенное S - слово, в котором  ищется образец X. Пусть m и n - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые  начинаются с позиций 1,2,...,m-n+1 в слове S; в случае равенства выводится  соответствующая позиция.

Идея алгоритма:

1) I=1;

2) Cравнить I-й символ массива T с первым символом массива W;

3) Cовпадение → сравнить вторые символы и так далее;

4) Несовпадение → I:=I+1 и переход на пункт 2.

Условия окончания алгоритма:

    1. Подряд М сравнений удачны;
    2. I+M>=N, то есть слово не найдено.

Это не эффективный алгоритм т.к. максимальное, количество сравнений  будет равно O((m-n+1)*n+1), хотя большинство из них на самом деле лишние.

2.2 Анализ алгоритма  Боуэра-Мура

Алгоритм Бойера-Мура, разработанный  двумя учеными – Бойером и  Муром, считается наиболее быстрым  среди алгоритмов общего назначения, предназначенных для поиска подстроки  в строке.

Простейший вариант алгоритма  Бойера-Мура состоит из следующих шагов.

    1. Строится таблица смещений для искомого образца. 
    2. Совмещается начало строки и образца и начинается проверка с последнего символа образца.
    3. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца.
    4. Если же символы совпадают, производится сравнение предпоследнего символа образца и т. д. Если все символы образца совпали с наложенными символами строки, значит нашлась подстрока и поиск окончен.
    5. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, сдвигается образец на один символ вправо и снова начинается проверку с последнего символа.
    6. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.

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

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

Пример 1. Пусть есть алфавит из пяти символов: a, b, c, d, e и надо найти вхождение образца “abbad” в строке “abeccacbadbabbad”. На рисунке 2 изображена таблица смещений.

Рисунок 2 – Таблица смещений

На рисунке 3 показано начало поиска.

Рисунок 3 – Начало поиска

Последний символ образца  не совпадает с наложенным символом строки. Сдвигается образец вправо на 5 позиций, что показано на рисунке 4.

Рисунок 4 – Сдвиг образца на 5 позиций

Три символа образца совпали, а четвертый – нет.

Сдвигается образец вправо на одну позицию, что показано на рисунке 5.

Рисунок 5 –Сдвиг образца на 1 позицию

Последний символ снова не совпадает с символом строки. В  соответствии с таблицей смещений сдвигается образец на 2 позиции. Это показано на рисунке 6.

Рисунок 6 – Сдвиг образца на 2 позиции

На рисунке 7 показан еще один сдвиг на 2 позиции.

Рисунок 7 – Сдвиг образца на 2 позиции

 

В соответствии с таблицей, сдвигается образец на одну позицию, и получается искомое вхождение образца. На рисунке 8 показана данная операция.

Рисунок 8 – Получение искомого вхождения образца

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

Метод использует предобработку  искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки S[1..i] строки S наибольшей подстроки S[1..j] (j<i), присутствующей одновременно и в начале, и в конце подстроки (как префикс и как суффикс). Например, для подстроки abcHelloabc такой подстрокой является abc (одновременно и префиксом, и суффиксом). Смысл префикс - функции в том, что можно отбросить заведомо неверные варианты, т.е. если при поиске совпала подстрока abcHelloabc (следующий символ не совпал), то имеет смысл продолжать проверку продолжить поиск уже с четвертого символа (первые три и так совпадут). Вначале рассматриваются некоторые вспомогательные утверждения. Для произвольного слова X рассматриваются все его начала, одновременно являющиеся его концами, и выбираются из них самое длинное (не считая, конечно, самого слова X). Оно обозначается n(X). Такая функция носит название -  префикс – функция.

Метод КМП использует предобработку  искомой строки, а именно:

    1. На основе строки создается префикс-функция. При этом используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1;
    2. Проверяется префикс предыдущей подстроки;
    3. Если же тот не подходит, то находится префикс ее префикса, и т.д.
    4. Действуя так, находится наибольший искомый префикс. 

Алгоритм последовательного  поиска и алгоритм КМП помимо нахождения самих строк считают, сколько  символов совпало в процессе работы.

 

 

3 Анализ и выбор  структур данных

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

Str: string; //описание строки;

Str[1]… //обращение к 1-ому символу строки.

 

 

4 Проектирование  и реализация программного средства

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

TFind = class

  private

    MyWord1, MyWord2:string;

    function  GetWord1: string;

    function  GetWord2: string;

    procedure SetWord1(const Value: string);

    procedure SetWord2(const Value: string);

  public

    constructor Create;

    destructor Destroy;

    function Search_Boyer_Moore(wrd1,wrd2:string):boolean;

    function Search_Knuth_Morris_Pratt(wrd1,wrd2:string):boolean;

    function Search_Straight_Forward(wrd1,wrd2:string):boolean;

    property Word1:string read GetWord1 write SetWord1 ;

    property Word2:string read GetWord2 write SetWord2 ;

  end;

Как видно из описания, присутствуют 3 метода – методы поиска, и 2 свойства, типа string.

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

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

Рисунок 9 – Интерфейс программы при запуске

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

Рисунок 10 – Интерфейс программы при завершении поиска

Класс TFind помещен в отдельный модуль. Это позволяет избежать громоздкости кода и скрыть саму реализацию класса с его методами и свойствами. На рисунке 11 представлено взаимодействие основного кода программы и дополнительного модуля с реализацией класса.

                                                         (1)


 

                                             (2)


Рисунок 11 – Взаимодействие модулей

    1. – поток данных и выбранный метод.Под потоком данных понимается искомая строка и строка поиска.
    2. – результат выполнения выбранного метода.Результат имеет тип bool.

 

 

 

 

 

 

 

 

 

 

 

 

5 Оценка эффективности

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

Временная сложность будет  подсчитываться в исполняемых командах: количество арифметических операций, количество сравнений.

Для оценки эффективности  трех представленных алгоритмов, было решено использовать несколько тестов, когда искомое слово находится  в конце файла, состоящего из 1500 строк, 3000 строк, 4500 строк, 5000 строк, по 12 слов в каждой(без форматирования). График  приведен на рисунке 12.

 

Рисунок 12 – Зависимость времени поиска от количества строк в файле

Из графика видно, что самый медленный алгоритм – это алгоритм SF. За ним идет алгоритм Кнута-Мориса-Пратта. И лучший результат имеет алгоритм, который показал лучшее время – алгоритм Боуэра-Мура.

Так же необходимо оценить количество сравнений в каждом из данных алгоритмов. Ниже приведены рисунки с результатами. Искомое слово находится в конце файла, состоящего из 4000 строк (48000 слов).

Рисунок 13 – Количество сравнений в алгоритме SF

Рисунок 14 – Количество сравнений в алгоритме KMP

Рисунок 15 – Количество сравнений в алгоритме BM

Рисунок 16 – Зависимость количества сравнений от алгоритма

На основании данных тестов можно сделать вывод, что самым  неэффективным оказался алгоритм Stright Forward (SF) – 104705 сравнений. За ним следует алгоритм Кнутта-Мориса-Пратта (KMP) – 53483 сравнений. Лидером среди них оказался алгоритм Боуэра- Мура (BM) – 18316 сравнений.

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

 

 

 

 

 

 

 

 

 

Заключение

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

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

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

 

 

Список литературы

1 Ахо, Альфред Структура  данных и алгоритмы [Текст]. –  М.: Издательский дом «Вильямс», 2000. - 384 с.

2 Вирт, Н. Алгоритмы и  структуры данных [Текст].– М:. Мир, 1989. – 360 с.

3 Шень, А. Программирование: теоремы и задачи [Текст]. – М.: Московский центр непрерывного  математического образования, 1995.

4 Кормен, Т. Алгоритмы:  построение и анализ [Текст]/ Т.  Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002.  М.: МЦНМО, 2002.

 

 

Приложение А

(обязательное)

Листинг программы

unit Unit1;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, Unit2,{ Vcl.ComCtrls,} ComCtrls;

type

  TForm1 = class(TForm)

    Button1: TButton;

    Edit1: TEdit;

    Label1: TLabel;

    Label2: TLabel;

    Button2: TButton;

    Label3: TLabel;

    RadioButton1: TRadioButton;

    RadioButton2: TRadioButton;

    RadioButton3: TRadioButton;

    ProgressBar1: TProgressBar;

    ListBox1: TListBox;

    label4: TLabel;

    procedure Button1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure FormCreate(Sender: TObject);

    procedure FormClose(Sender: TObject; var Action: TCloseAction);

    procedure RadioButton3Click(Sender: TObject);

    procedure RadioButton1Click(Sender: TObject);

    procedure RadioButton2Click(Sender: TObject);

    procedure Edit1Click(Sender: TObject);

  private

    shag:integer;

    { Private declarations }

  public

    FileName:string;

    { Public declarations }

  end;

 

var

  Form1: TForm1;

 

implementation

var

  Find1 : TFind;

{$R *.dfm}

 

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

  find1.Destroy;

end;

 

procedure TForm1.FormCreate(Sender: TObject);

begin

  edit1.AutoSelect:=false;

  shag:=0;

  find1:=TFind.Create;

  radiobutton1.Caption:='Алгоритм  Бойера-Мура';

  radiobutton2.Caption:='Алгоритм  Кнута-Морриса-Пратта';

  radiobutton3.Caption:='Алгоритм SF';

end;

 

procedure TForm1.RadioButton1Click(Sender: TObject);

begin

  ProgressBar1.Position := 0 ;

  Application.ProcessMessages;

end;

 

procedure TForm1.RadioButton2Click(Sender: TObject);

begin

  ProgressBar1.Position := 0 ;

  Application.ProcessMessages;

end;

 

procedure TForm1.RadioButton3Click(Sender: TObject);

begin

  ProgressBar1.Position := 0 ;

  Application.ProcessMessages;

end;

 

procedure TForm1.Button1Click(Sender: TObject);

var

  opendialog:TOpenDialog;

  f:textfile;

  buff:string;

begin

  listbox1.Clear;

  Filename:='';

  opendialog:=TOpenDialog.Create(self);

  opendialog.InitialDir:='C:\';

  opendialog.Options:=[ofFileMustExist];

  opendialog.Filter:='txt-files|*.txt';

  if opendialog.Execute then showmessage('Выбран  файл: '+opendialog.filename)

    else showmessage('Действие  отменено');

  FileName:= opendialog.FileName;

  opendialog.Free;

  if fileName<>'' then  begin

    assignfile(f,FileName);

    reset(f);

    while not eof (f) do begin

      readln(f,buff);

      inc(shag);

      listbox1.Items.Add(buff);

    end;

    buff:='';

    closefile(f);

   end;

end;

 

procedure TForm1.Button2Click(Sender: TObject);

var

  f:textfile;

  ok:boolean;

  buff:string;

  today:TdateTime;

  i,a,s,proc:integer;

begin

  if FileName='' then begin

    showmessage('Выберите  файл!');

    exit;

  end;

  ok:=false;

  buff:='';

  Find1.Word1:=edit1.Text;

  assignfile(f,FileName);

  reset(f);

  s:=0;

  for i:=1 to 1000 do a:=a+1;

  if radiobutton1.Checked then begin

    while (not eof(f))and(ok=false) do begin

      proc := ((s * 100) div Shag);

      readln(f,buff);

      Find1.Word2:=buff;

      ok:=Find1.Search_Boyer_Moore(Find1.Word1,Find1.Word2);

      if ok then break;

      ProgressBar1.Position := proc ;

      Application.ProcessMessages;

      inc(s);

    end;

    if ok

      then showmessage('Слово  найдено в файле! ')

      else showmessage('Слово не найдено в файле! ');

      closefile(f);

      ProgressBar1.Position := 0 ;

      Application.ProcessMessages;

    exit;

  end else

  if radiobutton2.Checked then begin

    while (not eof(f))and(ok=false) do begin

      proc := ((s * 100) div Shag);

      readln(f,buff);

      Find1.Word2:=buff;

      ok:=Find1.Search_Knuth_Morris_Pratt(Find1.Word1,Find1.Word2);

      if ok then break;

      ProgressBar1.Position := proc ;

      Application.ProcessMessages;

      inc(s);

    end;

    if ok

      then showmessage('Слово  найдено в файле! ')

      else showmessage('Слово не найдено в файле! ');

      closefile(f);

      ProgressBar1.Position := 0 ;

      Application.ProcessMessages;

    exit;

  end else

  if radiobutton3.Checked then begin

    while (not eof(f))and(ok=false) do begin

      proc := ((s * 100) div Shag);

      readln(f,buff);

      Find1.Word2:=buff;

      ok:=Find1.Search_Straight_Forward(Find1.Word1,Find1.Word2);

      if ok then break;

      ProgressBar1.Position := proc ;

      Application.ProcessMessages;

      inc(s);

    end;

    if ok

      then showmessage('Слово  найдено в файле! ')

      else showmessage('Слово не найдено в файле! ');

      closefile(f);

      ProgressBar1.Position := 0 ;

      Application.ProcessMessages;

    exit;

  end else showmessage('Выберите  метод поиска!');

end;

 

procedure TForm1.Edit1Click(Sender: TObject);

begin

  Edit1.SelStart:=0;

  Edit1.SelLength:=edit1.MaxLength-1;

  Edit1.SetFocus;

end;

 

end.

 

unit Unit2;

interface

type

  TFind = class

  private

    MyWord1, MyWord2:string;

    function  GetWord1: string;

    function  GetWord2: string;

    procedure SetWord1(const Value: string);

    procedure SetWord2(const Value: string);

  public

    constructor Create;

    destructor Destroy;

    function Search_Boyer_Moore(wrd1,wrd2:string):boolean;

    function Search_Knuth_Morris_Pratt(wrd1,wrd2:string):boolean;

    function Search_Straight_Forward(wrd1,wrd2:string):boolean;

    property Word1:string read GetWord1 write SetWord1 ;

    property Word2:string read GetWord2 write SetWord2 ;

  end;

 

implementation

 

{ Find }

 

constructor TFind.Create;

begin

  Word1:='';

  Word2:='';

  inherited;

end;

Поиск сравнением с образцом