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

 

 

 

 

 

 

Введение	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;