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

    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;