Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Исторические сведения

2. Обзор основных понятий

3. Виды алгоритмов поиска

4. Применение алгоритмов поиска

Заключение

Список использованной литературы



Введение

Информация, в современном мире играет огромную роль в развитии общества и государства. С внедрением различных компьютерных технологий в процесс производства становятся актуальными такие проблемы как хранение больших объёмов данных на носителях, скорость передачи, а также быстрый поиск необходимой информации. Именно, поисковые системы позволяют пользователям по одному слову или словосочетанию производить поиск с невероятной точностью. На данный момент существуют также ряд систем которые могут предложить несколько вариантов склонений введённого слова или словосочетания. Глобальные или локальные сети без поисковых систем привели бы к тому, что пользователь должен был запомнить миллионы веб адресов, часто имеющие сокращённые названия. В генной инженерии поиск совпадений строковых последовательностей используется при анализе ДНК. В программировании - как одной из самых сложных сфер компьютерной индустрии - благодаря поиску сейчас можно найти ошибки, при лексическом анализе компьютерных программ. Информация из различных баз данных, также становится недоступной для извлечения без соответствующего поиска по заданным параметрам. Любая поисковая система строится на основе одного или нескольких скомбинированных алгоритмов. Каждый алгоритм отличается своей скоростью вычисления результата. Алгоритмы вычисления строковых совпадений применяются в таких областях, как распознавание речи, компьютерное зрение, криптография, сжатие данных, вычислительная геометрия и молекулярная биология. Невозможно представить всемирно известную лингвистическую систему ABBYY LINGVO без быстрого поиска по словам, или систему WINDOWS без возможности поиска файлов. Немаловажным фактором хорошей поисковой системы является интуитивно-понятный интерфейс, который поможет пользователю найти необходимые объекты.

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

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

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

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

Четвёртая задача включает в себя практические моменты применения алгоритмов поиска в тексте. Будет рассматриваться реализация ряда алгоритмов напрямую связанных с решением сегодняшних проблем. При этом в качестве языка программирования будет использоваться Pascal. В этой работе в качестве литературных источников будут рассмотрены труды Билла Смита, Кормена Т., Лейзера Ч.



1. Исторические сведения

Современное формальное определение алгоритма было дано в 30-50-е годы XX века в работах Тьюринга, Поста, Чёрча, Н. Винера, А.А. Маркова.

Само слово «алгоритм» произошло от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Аль-Хорезми сформулировал правила вычислений в новой системе и, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа. Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритмы о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра (алгебра - аль-джебр - восполнение).

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

Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi:» («Аль-Хорезми говорил:»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманнской рукописи XIII века, написанной в стихах, можно прочесть: “Алгоризм был придуман в Греции. Это часть арифметики. Придуман он был мастером по имени Алгоризм, который дал ему своё имя. И поскольку его звали Алгоризм, Он назвал свою книгу «Алгоризм»”.

Около 1250 года английский астроном и математик Иоанн Сакробоско написал труд по арифметике Algorismus vulgaris, который стал на столетия основным учебником по вычислениям в десятичной позиционной системе счисления в европейских университетах. Во введении Сакробоско назвал автором науки о счёте мудреца по имени Алгус (Algus). В популярной средневековой поэме «Роман о Розе» (1275-1280) Жана де Мена «греческий философ Алгус» ставится в один ряд с Платоном, Аристотелем, Евклидом и Птолемеем.«Мастер Алгус» стал в средневековой литературе олицетворением счётного искусства.

Со временем, слово algorism (или algorismus) обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге, без использования абака. Абак - счётная доска, применявшаяся для арифметических вычислений приблизительно с V века до н. э. в Древней Греции, Древнем Риме. Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как Герберт Аврилакский, ставший в 999 г. папой римским под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей алгорисмиков и абацистов (иногда называемых гербекистами), которые пропагандировали использование для вычислений абака вместо арабских цифр. Прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений. В Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака», а сочинения по искусству счёта назывались Алгоритмами.

Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, около 1360 г. французский философ Николай Орем написал математический трактат Algorismus proportionum («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть Algorithmus linealis, то есть правила счёта на линиях.

Первоначальная форма algorismi спустя некоторое время потеряла последнюю букву, и слово приобрело более удобное для европейского произношения вид algorism. Позднее и оно, подверглось искажению, скорее всего, связанному со словом arithmetic.

В XVIII веке в одном из германских математических словарей, Vollstandiges mathematisches Lexicon, термин algorithmus всё ещё объясняется как понятие о четырёх арифметических операциях. Но такое значение не было единственным, ведь терминология математической науки в те времена ещё только формировалась. В частности, выражение algorithmus infinitesimalis применялось к способам выполнения действий с бесконечно малыми величинами.

Пользовался словом алгоритм и Леонард Эйлер, одна из работ которого так и называется - «Использование нового алгоритма для решения проблемы Пелля».

Потребовалось ещё почти два столетия, чтобы все старинные значения слова вышли из употребления. Этот процесс можно проследить на примере проникновения слова «алгоритм» в русский язык.

Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах и восходит к ещё более древним рукописям XVI века. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. Полное название этого учебника - «Сия книга, глаголемая по-еллински и по-гречески арифметика, а по-немецки алгоризма, а по-русски цифирная счётная мудрость».

Таким образом, слово «алгоритм» понималось первыми русскими математиками так же, как и в Западной Европе. Однако его не было ни в знаменитом словаре В.И. Даля, ни спустя сто лет в «Толковом словаре русского языка» под редакцией Д.Н. Ушакова. Но слово «алгорифм» можно найти в популярном дореволюционном Энциклопедическом словаре братьев Гранат, и в первом издании Большой советской энциклопедии. Здесь оно трактуется как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления. Однако к началу XX в. для математиков слово «алгоритм» уже означало любой арифметический или алгебраический процесс, выполняемый по строго определённым правилам, и это объяснение также даётся в следующих изданиях БСЭ.

Алгоритмы становились предметом всё более пристального внимания учёных, и постепенно это понятие заняло одно из центральных мест в современной математике. Что же касается людей, от математики далёких, то к началу сороковых годов это слово они могли услышать разве что во время учёбы в школе, в сочетании «алгоритм Евклида». Несмотря на это, алгоритм всё ещё воспринимался как термин сугубо специальный, что подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности, его нет даже в десятитомной Малой советской энциклопедии (1957 г.), не говоря уже об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании Большой советской энциклопедии (1969 г.) алгоритм уже характеризуется как одна из основных категорий математики, «не обладающих формальным определением в терминах более простых понятий, и абстрагируемых непосредственно из опыта». Как мы видим, отличие даже от трактовки первым изданием БСЭ разительное! За сорок лет алгоритм превратился в одно из ключевых понятий математики, и признанием этого стало включение слова уже не в энциклопедии, а в словари. Например, оно присутствует в академическом «Словаре русского языка» (1981 г.) именно как термин из области математики.

Одновременно с развитием понятия алгоритма постепенно происходила и его экспансия из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» вошло в 1985 г. во все школьные учебники информатики и обрело новую жизнь. Вообще можно сказать, что его сегодняшняя известность напрямую связана со степенью распространения компьютеров. Например, в третьем томе «Детской энциклопедии» (1959 г.) о вычислительных машинах говорится немало, но они ещё не стали чем-то привычным и воспринимаются скорее как некий атрибут светлого, но достаточно далёкого будущего. Соответственно и алгоритмы ни разу не упоминаются на её страницах. Но уже в начале 70-х гг. прошлого столетия, когда компьютеры перестали быть экзотической диковинкой, слово «алгоритм» стремительно входит в обиход. Это чутко фиксируют энциклопедические издания. В «Энциклопедии кибернетики» (1974 г.) в статье «Алгоритм» он уже связывается с реализацией на вычислительных машинах, а в «Советской военной энциклопедии» (1976 г.) даже появляется отдельная статья «Алгоритм решения задачи на ЭВМ». За последние полтора-два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится всё более привычной. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде «алгоритм поведения», «алгоритм успеха» или даже «алгоритм предательства».

В данной работе также будет использовано понятие «алгоритма поиска строки в подстроке». В развитии этого алгоритма принимали участие многие учёные.

Ричард Карп в 1987 году, вместе с Майклом Рабином, разработал алгоритм поиска подстроки, названный в их честь.

Ричард Карп родился в 1935 году в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа и его жены Розы Карп в Бостоне, штат Массачусетс. С ним росли двое младших братьев Роберт и Дэвид, и младшая сестра Кэролин. Окончив школу, Ричард поступил в Гарвардский университет, где получил титулы бакалавра (1955), магистра наук (1956) и наконец доктора философии по прикладной математике в 1959 году. После учёбы работал 9 лет в исследовательском центре IBM.В 1968 году он получил профессуру по информатике, математике и исследованию операций при калифорнийском университете Беркли, где и работает по сей день, не учитывая четырёхлетнего перерыва на работу в университете Вашингтона. В 1971 году Карп вместе с Джэком Эдмондсом разработал алгоритм для нахождения максимального потока в транспортной сети. Год спустя, Карп опубликовал свой труд «Reducibility Among Combinatorial Problems», в котором он доказал NP-полноту для 21 задачи.

Михаэль Рабин родился в 1931 году сыном раввина Исраэля Аврахама Рабина в городе Бреслау (ныне Вроцлав), принадлежащему тогда к Пруссии. В 1935 году его семья эмигрировала в Палестину. В 1953 году он получил титул магистра наук, закончив учёбу в Еврейском университете в Иерусалиме. Три года спустя, в 1956 году, защитил диссертацию в Принстонском университете и стал доктором философии. В настоящее время (сентябрь 2008 года) Майкл Рабин занимается исследованиями в области компьютерной безопасности и преподаёт в Иерусалиме и Гарварде.

В 1977 году были опубликованы результаты работ Д. Кнута, В. Пратта, Д. Морриса также занимавшихся алгоритмами поиска.

Дональд Эрвин Кнут - американский учёный, почётный профессор в отставке Стэнфордского университета и нескольких других университетов в разных странах, иностранный член Российской академии наук, преподаватель и идеолог программирования, автор 19 монографий и более 160 статей, разработчик нескольких известных программных технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и методам вычислительной математики, а также создатель настольных издательских систем TEX и METAFONT, предназначенных для набора и вёрстки книг, посвящённых технической тематике. Родился 10 января 1938 в США в семье преподавателя. Отец Дональда преподавал бухгалтерский учёт, а также занимался печатным делом на дому как любитель. С юных лет в Дональде наблюдалась склонность к математике, физике и музыке. Профессор Кнут удостоен премии Тьюринга (1974), Национальная научная медаль США (1979) и AMS Steele Prize, премия Харви (1995 год), премия Киото (1996) за достижения в области передовых технологий, премия имени Грейс Мюррей Хоппер (1971).

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

2. Обзор основных понятий

Алгоритм - набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Часто в качестве исполнителя выступает некоторый механизм (компьютер, токарный станок, швейная машина), но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.

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

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

Существуют основные свойства алгоритма, которыми должен обладать любой из них:

- Детерминированность (определенность). Это свойство заключается в том, что при задании одних и тех же исходных данных несколько раз алгоритм будет выполняться абсолютно одинаково и всегда будет получен один и тот же результат. Свойство детерминированности проявляется также и в том, что на каждом шаге выполнения алгоритма всегда точно известно, что делать дальше, а каждое действие однозначно понятно исполнителю и не может быть истолковано неопределенно. Благодаря этому свойству выполнение алгоритма носит механический характер.

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

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

- Дискретность - означает, что алгоритм состоит из последовательности отдельных шагов - элементарных действий, выполнение которых не представляет сложности. Именно благодаря этому свойству алгоритм может быть реализован на ЭВМ.

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

- Корректность - означает, что если алгоритм создан для решения определенной задачи, то для всех исходных данных он должен всегда давать правильный результат и ни для каких исходных данных не будет получен неправильный результат. Если хотя бы один из полученных результатов противоречит хотя бы одному из ранее установленных и получивших признание фактов, алгоритм нельзя признать корректным.

Если последовательность действий не обладает хотя бы одним из перечисленных выше свойств, то она не может считаться алгоритмом.

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

- Корректность.

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

- Отсутствие возврата к ранее просмотренным данным.

- Независимость от алфавита.

- Возможность предварительной подготовки данных.

- Кодирование выходного результата.

Корректность:

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

Временная и пространственная сложность:

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

Если сравнивать временную и пространственную сложности алгоритмов, то временная сложность считается более важным критерием при выборе алгоритма.

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

Отсутствие возврата к ранее просмотренным данным:

Просмотр строковых последовательностей естественно выполнять слева направо.

Поэтому чрезвычайно привлекательным свойством строковых алгоритмов считается их «онлайновость».

Это означает, что если в процессе вычислений уже просмотрена позиция «i» в строковой последовательности, то алгоритм уже не вернется к этой позиции «i» снова.

Другими словами, онлайновый алгоритм никогда не выполняет возврата к уже просмотренным позициям.

Независимость от алфавита:

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

Необходимость предварительной подготовки данных:

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

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

Кодирование выходного результата:

При вычислении кратных строк ключевую роль играет кодирование (способ представления) выходного результата, которое позволяет уменьшить объем выходных данных, а также сложность алгоритма.

3. Виды алгоритмов поиска

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

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

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

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

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

1. I=1,

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

3. совпадение - сравнить вторые символы и так далее,

4. несовпадение:

I:= I + 1

И переход на пункт 2,

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

1. подряд М сравнений удачны,

2. есть слово не найдено:

I + M > N

Сложность алгоритма:

Худший случай.

Недостатки алгоритма:

1. высокая сложность:

O (N * M)

В худшем случае:

И ((N - M + 1) * M)

2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);

3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

Алгоритм Д. Кнута, Д. Мориса и В. Пратта (КМП-поиск):

Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.

Пример.

(Символы, подвергшиеся сравнению, подчеркнуты.)

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

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

Особенности КМП-поиска:

1. требуется порядка сравнений символов для получения результата;

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

Поэтому выигрыш от КМП-поиска в большинстве случаев текстов весьма незначителен.

Алгоритм Р. Боуера и Д. Мура (БМ-поиск):

На практике алгоритм БМ-поиска наиболее эффективен, если образец W длинный, а мощность алфавита достаточно велика.

Идея БМ-поиска - сравнение символов начинается с конца образца, а не с начала, то есть сравнение отдельных символов происходит справа налево. Затем с помощью некоторой эвристической процедуры вычисляется величина сдвига вправо s. И снова производится сравнение символов, начиная с конца образца.

Этот метод не только улучшает обработку самого плохого случая, но и даёт выигрыш в промежуточных ситуациях.

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

О ((N - M + 1) * M + p)

Где:

p - мощность алфавита.

Алгоритм Рабина-Карпа (РК-поиск).

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d-ичная цифра.

Пример. Пусть образец имеет вид W = 3 1 4 1 5.

Вычисляем значения чисел из окна длины:

Из равенства:

ki = kj (mod * q)

Не следует, что ki= kj.

Если:



ki = kj (mod * q)

То ещё надо проверить, совпадают ли строки:

T [s + 1…s + m]

Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики.

В худшем случае время работы алгоритма:

РК - И((N - M + 1) * M)

В среднем же он работает достаточно быстро - за время:

О (N + M)

Пример: Сколько холостых срабатываний k сделает алгоритм РК, если q= 11, 13, 17.

Пусть W={2 6}:

Количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.

Поиск под слов с помощью конечных автоматов.

Cуществует последовательность букв x[1],...,x[n]. Определить, имеются ли в ней идущие друг за другом буквы "abcd".

Решение.

Имеется (n-3) позиции, на которых может находиться искомое под слово в исходном слове. Для каждой из позиций можно проверить, действительно ли там оно находится, сравнив четыре буквы. Есть более эффективный способ.

Прочитав слово x[1]...x[n] слева направо, нужно подождать появления буквы 'a'. После появления, за ней ожидается буква 'b', затем 'c', и, наконец, 'd'. Если ожидания оправданы, то слово "abcd" обнаружено. Если же какая-то из нужных букв не появляется, начинаем всё сначала.

В результате итог такой, что при чтении слова x слева направо в каждый момент времени находимся в одном из следующих состояний: "начальное" (0), "сразу после a" (1), "сразу после ab" (2), "сразу после abc" (3), "сразу после abcd" (4).

Прочитав очередную букву, происходит переход в следующее состояние по правилу, описанному в следующей таблице:

Текущее состояние	Очередная буква	Новое состояние
0	a	1
0	a	0
1	кроме b	2
1	a	1
1	кроме a,b	0
2	c	3
2	a	1
2	кроме a,c	0
3	d	4
3	a	1
3	кроме a,d	0

После того, как переход осуществлён в состояние 4, работа заканчивается.

Соответствующая программа очевидна:



В каждый момент времени хранится информация о том, какое максимальное начало нашего образца "abcd" является концом прочитанной части. Терминами индуктивных функций ситуацию можно описать так: рассмотрим функцию на словах, которая принимает два значения "истина" и "ложь" и истинна на словах, имеющих "abcd" своим под словом. Эта функция не является индуктивной, но имеет индуктивное расширение: «x» - длина максимального начала слова abcd, являющегося концом «x». Отметим, что в предыдущих рассуждениях нельзя заменить слово "abcd" на произвольное слово. Проблема связана с тем, что в образце могут быть повторяющиеся буквы. Пусть, например, происходит поиск вхождения слова "ababc". Вот появилась буква "a", за ней идет "b", за ней идет "a", затем снова "b". В этот момент ожидается буква "c". Вместо неё появляется другая буква, и образец "ababc" не обнаружен. Если вместо "c" появилась буква "a", то тогда за ней могут последовать буквы "b" и "c", и образец все-таки будет найден.

4. Применение алгоритмов поиска

Итак, допустим у нас есть текст, состоящий из n символов, который в дальнейшем ,будет называться T, а T[i] его i-ый символ. Строку или просто слово, состоящее из m символов, называется S, где S[i] -i-ый символ строки. Нужно проверить, входит ли данная строка в данный текст, и если входит, то начиная с какого символа текста. Рассмотрим несколько известных алгоритмов, решающих поставленную задачу.

Простейший алгоритм. Суть метода заключается в следующем: проверяется, совпадают ли «m» символов текста (начиная с выбранного) с символами нашей строки, примеряя шаблон куда только возможно. Естественно, реализовать описанный алгоритм проще всего (код Pascal):



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

O((n - m + 1) m)

Для маленьких строк поиск проработает быстро, но если в каком-то много мегабайтном файле нужно будет найти последовательность длинной 100 Кб, то, времени уйдёт очень много. Впрочем, основной недостаток вышеизложенного метода состоит в том, что приходится выполнять много лишней работы.

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

Алгоритм Рабина-Карпа.

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

Проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка Dm, где D - количество различных символов), и работать с ними будет так же неудобно.

Реализация для текста, состоящего только из цифр, и строки длиной до 8 символов.



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



Итак, нам все-таки приходится производить сравнение строк посимвольно, но так как «холостых» срабатываний будет немного (в 1/P случаях), то ожидаемое время работы малое. Строго говоря, время работы есть:

O(m + n + mn / P)

Где:

mn / P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа. Этот алгоритм значительно быстрее предыдущего и вполне подходит для работы с очень длинными строками.

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

Метод использует предобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки S[1..i] строки S наибольшей подстроки:

S[1..j] * (j<i)

Присутствующей одновременно и в начале, и в конце подстроки. Например, для подстроки abcHelloabc такой подстрокой является abc. Смысл префикс-функции в том, что мы можем отбросить заведомо неверные варианты, т. е. если при поиске совпала подстрока abcHelloabc, то имеет смысл продолжать проверку уже с четвертого символа. Вот как можно вычислить эту функцию для всех значений параметра от 1 до m. Используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1.



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

Время работы процедуры линейно, потому что, присвоение префикс - функции происходит четко m раз, остальное время меняется переменная k. Так как в цикле while она уменьшается, но не становится меньше 0, то уменьшаться она может не чаще, чем возрастать.

Переменная k возрастает на 1 не более m раз. Значит, переменная k меняется всего не более 2m раз.

Выходит, что время работы всей процедуры есть O(m). Реализация алгоритма:



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

Алгоритм Боуэра-Мура на языке Pascal.

Пусть:

X = x*[1]...x*[n]

- слово-образец, которое нужно отыскать. Для каждой буквы s находим самое правое его вхождение в слово X, т. е. наибольшее k.

Эти сведения будут храниться в массиве Posit[s]. Если буква s вовсе не встречается, то:



Заключение

Главной задачей этой курсовой работы являлось изучение и анализ алгоритмов поиска подстроки в строке. При изучении исторических сведений стало известно, что в разработке алгоритмов поиска подстроки в стоке участвовали такие учёные как Ричард Карп, Майклом Рабином, Дональд Эрвин Кнут, Роберт Бойер, Джей Мур, биографии которых включают в себя много интересных фактов. Если принять во внимание развитие алгоритмов в целом ,то основополагающее значение в развитии имеет хорезмский учёный Абу Абдуллах Мухаммед ибн Муса аль-Хорезми. Современное определение алгоритма было использовано в 30-50-е годы XX века в работах Тьюринга, Поста, Чёрча, Н. Винера, А.А. Маркова.

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

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

Свойства алгоритмов:

1) Детерминированность,

2) Массовость,

3) Результативность,

4) Дискретность,

5) Конечность,

6) Корректность.

Основные качества:

1) Скорость вычислений и требуемая память,

2) Отсутствие возврата к ранее просмотренным данным,

3) Независимость от алфавита,

4) Возможность предварительной подготовки данных,

5) Кодирование выходного результата,

6) Корректность.

Применение алгоритмов на практике уже давно не является только частью программирования, так как в современном мире понятие «алгоритм» с каждым днём укрепляется в нашей жизни. Сегодня каждое электронное устройство, которое включает в себя микрочипы, микроконтроллеры, микропроцессоры, требует качественного программного обеспечения, или ряд правильных и последовательных алгоритмов. Экономичное и технически простое производство микропроцессоров позволяет внедрять электронику почти в любой предмет быта, после чего многие устройства получают приставку «Smart», т. е. «умный».

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

При большом объёме текстовой информации требуются эффективные методы поиска нужного слова или цифры. Для этого учёные в области программирования создали ряд алгоритмов приемлемых в каждом конкретном случае. Алгоритмы Кнута-Морриса-Пратта, простейший алгоритм, Алгоритм Рабина-Карпа, Алгоритм Р. Боуера и Д. Мура (БМ - поиск), являются самыми эффективными алгоритмами поиска.

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

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



Список использованной литературы

1. Ахо А. Алгоритмы поиска подстроки в строке // Структура данных и алгоритмы. - Издательсво.: «Вильямс», 2000. - С. 384.

2. Брайан К. Практика программирования. - Издательсво: «Невский диалект», 2001. - С. 381. компьютерный алгоритм программирование

3. Вирт Н. Алгоритмы и структуры данных. - Издательсво: «Мир», 1989. - С. 360.

4. Кнут Д. Алгоритм Кнута-Морриса-Пратта // Искусство программирования на ЭВМ. - Издательсво: «Мир», 1978. - т.3. - С. 356.

5. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн // Алгоритмы: построение и анализ - 2-e издание. - М.: «Вильямс», 2005. - С. 1019 - 1058.

6. Э.Э. Гасанов, В.Б. Кудрявцев // Теория хранения и поиска информации - М.: ФИЗМАТЛИТ, 2002. - 288 с.

7. Кристофер Д. Маннинг, Прабхакар Рагхаван, Хайнрих Шютце// Введение в информационный поиск. Издательство: «Вильямс», 2011- 528 стр.

8. Билл Смит // Методы и алгоритмы вычислений на строках. Издательсво: «Вильямс» ,2006. - 496 с.

9. Матьяш В.А., Ключарев А.А., Щекин С.В. Структуры и алгоритмы обработки данных. Часть 1: Учебное пособие. - Издательство: ГУАП, 2003.

10. Бочарова Т.А. Основы алгоритмизации: Учебное пособие Издательство Тихоокеан. гос.ун., 2011. - 64 стр.

11. Окулов С.М. Алгоритмы обработки строк. Учебное пособие// Издательство: БИНОМ. Лаборатория знаний 2012- 256 с.

12. Стивенс Р. Delphi. Готовые алгоритмы. Учебное пособие Издательство: ДМК Пресс 2007г. - 384 стр.

13. Комлева Н.В. Структуры и алгоритмы компьютерной обработки данных. Учебное пособие // Издательство: Евразийский открытый институт, Московский государственный университет экономики, статистики и информатики 2004г. - 140стр.

14. Стивенс Р. Visual Basic. Готовые алгоритмы. Учебное пособие//Издательство: ДМК Пресс 2007г. - 384стр.

15. Голицина О.Л., Попов И.И. Основы алгоритмизации и программирования Издательство: ФОРУМ: ИНФРА-М, 2006. - 432 стр.

16. Программирование и основы алгоритмизации: Учеб. пособие / В.Г. Давыдов. - 2-е изд., стер. - Издательство: Высш. шк., 2005. - 447 стр.

Размещено на Allbest.ru