рефераты конспекты курсовые дипломные лекции шпоры

  • Раздел Образование
  •  / 
  • Алгоритм прямого поиска подстроки в строке

Реферат Курсовая Конспект

Алгоритм прямого поиска подстроки в строке

Алгоритм прямого поиска подстроки в строке - раздел Образование, Основные операции при работе с деревьями   1. Установить I На Начало Строки S, Т.е. I...

 

1. Установить i на начало строки S, т.е. i = 0.

2. Проверить, не вышло ли i + M за границу N строки S. Если да, то алгоритм завершен (вхождения нет).

3. Начиная с i-го символа s, провести посимвольное сравнение строк S и p, т. е. S[i] и P, S[i+1] и P,…, S[i + M – 1] и P[M – 1].

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

Приведем пример, иллюстрирующий этот процесс. Символы образца, подвергшиеся сравнению, выделены синим цветом. Здесь

S: на дворе трава, на траве дрова;

P: траве.

н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
т р а в е                                                  
  т р а в е                                                
    т р а в е                                              
      т р а в е                                            
        т р а в е                                          
          т р а в е                                        
            т р а в е                                      
              т р а в е                                    
                т р а в е                                  
                  т р а в е                                
                  т р а в е                                
                  т р а в е                                
                  т р а в е                                
                  т р а в е                                
                    т р а в е                              
                      т р а в е                            
                        т р а в е                          
                          т р а в е                        
                            т р а в е                      
                              т р а в е                    
                                т р а в е                  
                                  т р а в е                
                                    т р а в е              
                                    т р а в е              
                                    т р а в е              
                                    т р а в е              
                                    т р а в е              

 

Приведем две блок-схемы, описывающие алгоритм. В первой блок-схеме (рис.1) используется дополнительная переменная flag, которая явно изменяет свое значение с 0 на 1 при обнаружении вхождения образца P в текст S.

Рис. 1. Блок-схема: Алгоритм прямого поиска подстроки в строке.

 

 

Во второй блок-схеме (рис.2) используется тот факт, что при j = M мы дошли до конца образца P, тем самым обнаружив его вхождение в строку S.

Рис. 2. Блок-схема: Алгоритм прямого поиска подстроки в строке.

 

 

Алгоритм работает достаточно эффективно, если при сравнении образца P с фрагментом текста S довольно быстро выявляется несовпадение (после нескольких сравнений во внутреннем цикле). Это случается довольно часто, но в худшем случае (когда в строке часто встречаются фрагменты, во многих символах совпадающие с образцом) производительность алгоритма значительно падает. Приведем пример. Здесь

S: учить, учиться, учитель

P: учитель

у ч и т ь ,   у ч и т ь с я ,   у ч и т е л ь
у ч и т е л ь                                
у ч и т е л ь                                
у ч и т е л ь                                
у ч и т е л ь                                
у ч и т е л ь                                
  у ч и т е л ь                              
    у ч и т е л ь                            
      у ч и т е л ь                          
        у ч и т е л ь                        
          у ч и т е л ь                      
            у ч и т е л ь                    
              у ч и т е л ь                  
              у ч и т е л ь                  
              у ч и т е л ь                  
              у ч и т е л ь                  
              у ч и т е л ь                  
                у ч и т е л ь                
                  у ч и т е л ь              
                    у ч и т е л ь            
                      у ч и т е л ь          
                        у ч и т е л ь        
                          у ч и т е л ь      
                            у ч и т е л ь    
                              у ч и т е л ь  
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь

БМ-поиск (Боуера–Мура)

 

Рассмотрим самый «плохой» для линейного поиска случай:

Подсчитаем для него число сравнений. Так как несовпадение символов происходит на последней букве образца, в каждом внешнем цикле производится M сравнений. Так как образец находится в конце строки, число внешних циклов равно N – M + 1, т.е. общее число сравнений есть M(N – M + 1). В 1975 году Р. Боуер и Д. Мур предложили алгоритм, который значительно ускоряет обработку данного случая. Алгоритм носит название БМ-поиска.

В отличие от линейного поиска, сравнение в БМ-поиске начинается не с начала, а с конца образца P. Кроме того, образец предварительно анализируется и благодаря этому он сдвигается не на один символ, а в общем случае на несколько. Рассмотрим механизм сдвига на примере.

S: на дворе трава, на траве дрова

P: дрова

Начинаем сравнение с последнего символа образца. Символы, подвергшиеся сравнению, выделены: в строке – красным цветом, в образце – синим. Индекс k указывает на первый сравниваемый символ в строке S (первоначально k = M - 1), индексы i и j – на сравниваемые символы в образце и строке соответственно. Сначала i = M - 1, j = k, затем i и j уменьшаются на единицу, пока не произойдет несовпадение символов S[j] и P[i] либо не закончится образец (i = -1).

 

        k                                                  
        j                                                  
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
д р о в а                                                  
        i                                                  

 

Совпадения не произошло при первом же сравнении, необходимо сдвинуть образец, т.е. увеличить индекс k. В БМ-поиске образец сдвигается так, чтобы «под» символом S[k] (в таблице) оказался совпадающий с ним ближайший к концу символ образца (иначе при j = k совпадение S[j] и P[i] точно не произойдет). Значит, в данном случае сдвигаем образец на одну позицию вправо, т.е. увеличиваем индекс k на единицу.

 

          k                                                
          j                                                
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
  д р о в а                                                
          i                                                

 

Совпадения образца со строкой опять не произошло, сдвигаем образец. Теперь S[k] = ‘о’ и расстояние от конца образца до символа ‘о’ в нем равно двум, значит, индекс k увеличиваем на два.

 

              k                                            
              j                                            
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
      д р о в а                                            
              i                                            

 

И опять не произошло совпадения образца со строкой. Теперь S[k] = ‘е’, такого символа в образце нет, поэтому мы можем сдвинуть образец сразу на его длину, т.е. увеличить индекс k на M.

                        k                                  
                        j                                  
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                д р о в а                                  
                        i                                  

 

Здесь S[k] = ’в’, расстояние от конца образца до символа ‘в’ равно единице, значит, индекс k увеличиваем на единицу.

 

                          k                                
                      j                                    
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                  д р о в а                                
                      i                                    

 

Теперь S[k] = ’а’, такой символ в образце есть, но лишь в последней позиции, в остальной части образца его нет, поэтому увеличиваем индекс k на длину образца M.

 

                                    k                      
                                    j                      
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                            д р о в а                      
                                    i                      

Символа S[k] = ’ ’ в образце нет, увеличиваем индекс k на M.

                                              k            
                                              j            
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                                      д р о в а            
                                              i            

Символа S[k] = ’е’ в образце нет, увеличиваем индекс k на M.

                                                        k  
                                                        j  
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                                                д р о в а  
                                                        i  

 

Символ S[k] = ’в’ в образце есть, расстояние от него до конца образца равно единице, увеличиваем индекс k на единице.

 

                                                          k
                                                j          
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                                                  д р о в а
                                                i          

 

Здесь индекс i = –1, следовательно, образец в строке найден.

В целом индекс k S[k] меняется следующим образом:

  • если символа S[k] в образце нет (кроме, может быть, последнего символа!), то k увеличивается на длину образца M;
  • если символ S[k] в образце есть и он не последний, то индекс k увеличивается на расстояние от конца образца до ближайшего символа S[k].

Разумеется, величины сдвигов вычисляются заранее и заносятся в таблицу TAB. Блок-схема для формирования таблицы TAB представлена на рис.3.

Рис.3.Блок-схема для формирования таблицы TAB:

 

Следует особенно отметить, что j < M – 1, так как TAB[P[M – 1]] должен быть равен M, а не нулю.

Далее достаточно очевидно, что образ в строке найден, если индекс j стал меньше нуля, и образ в строке не найден, если индекс i дошел до конца строки, т.е. стал больше или равен N (i может стать больше N, так как изменяется «скачками»).

Теперь можно привести блок-схему БМ-поиска(рис.4).

Рис.4. Блок-схема БМ-поиска.

КМП-поиск (Кнута–Мориса и–Пратта)

 

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

Пусть в образце все буквы не совпадают с первой, например:

S: от топота копыт пыль по полю летит

P: поле

Рассмотрим несколько случаев. Символы, подвергшиеся сравнению, выделены. Индексы i и j указывают на сравниваемые символы в образце и строке соответственно. Сначала i = j = 0, затем i и j увеличиваются на единицу, пока не произойдет несовпадение символов S[j] и P[i] либо не закончится образец (i = M).

 

j                                                                  
о т   т о п о т а   к о п ы т   п ы л ь   П о   п <
Развернуть
Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Основные операции при работе с деревьями

Основные операции при работе с деревьями... Определение глубины дерева... Обход дерева на заданную глубину включение нового значения в дерево...

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

Что будем делать с полученным материалом:

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

Все темы данного раздела:

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

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

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

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

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

Алгоритмы представления графа
  При программировании задач обработки сетевых структур требуется решить вопрос о представлении графа структурами данных языка программирования. Выбор представления графа определяется

Файл setgraph.h
#include "graph.h" #include "set.h" // Определение класса для работы с множествами class SetGraph : public Graph { Set **graph; // Массив множеств дуг

Представление графа в виде матрицы смежности
  Еще один распространенный способ представления графа — это представление в виде матрицы смежности размером N * N (рис.1). B этой матрице в элементе с индексами (i,j) записывается ин

Файл MatrixGraph.cpp
#include "MatrixGraph.h"   // Реализация конструктора - заказ и инициализация памяти // под двумерный массив логических значений MatrixGraph::Matr

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

Файл ListGraph.h
#include "graph.h" // Описание родительского класса   // Описание шаблона классов для представления // простых однонаправленных списков template &

Файл ListGraph.cpp
#include "ListGraph.h"   // Реализация операций над списком. // Добавление нового элемента в список template <class T> void List<

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

Файл ArcGraph.h
#include "graph.h" // Определение родительского класса // Описание класса для представления A-графа class ArcGraph : public Graph { // Дуга представлена элемент

Файл ArcGraph.cpp
«include "ArcGraph.h"   //Реализация операции добавления дуги void ArcGraph::addArc(int from, int to) { // Сначала проверяем правильность задания

Файл convert.срр
#include "SetGraph.h" #include "MatrixGraph.h" #include "ListGraph.h" #include "ArcGraph.h"   // Функция пр

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

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

Поиск кратчайших путей
Путем в графе называют чередующуюся последовательность вершин и дуг v1, e1, v2, e2,... vn-1 en-1, vn, в которой каждый элемент vi— вершина графа, а каждый элемент еi — дуга графа, ведущая из пре

Алгоритм Э. Дейкстры.
Опишем алгоритм нахождения такого пути при условии, что длины всех дуг неотрицательны. Этот алгоритм был предложен и опубликован Э. Дейкстрой (Е. W. Dijkstra), поэтому и носит его имя. Алг

Алгоритм Флойда — Уоршалла
Идея алгоритмом Флойда — Уоршалла, состоит в следующем. Будем рассматривать последовательность матриц смежности. В этой матрице элемент с индексами (i,j) равен +∞, если в графе нет ребра, вед

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

Файл listgraph.h
// Класс ListGraph задает структуру L-графа class ListGraph {   // Массив списков дуг List<int> *graph; // Количество вершин графа i

Файл Arc.h
// Структура ребра для алгоритма Крускала: сравнение ребер // происходит по их весам   struct Arc { int from, to; double weight; Arc(int f

Файл listgraph.cpp
// Собственно алгоритм Крускала double ListGraph::minSkeleton( // Выходной поток для вывода результирующей информации: std::ostream & out, // Нагрузка на реб

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

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

Пузырьковая сортировка
  Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются сле

Быстрая сортировка
  Алгоритм быстрой сортировки обладает привлекательными особенностями: он принадлежит к категории обменных (in-place) сортировок (т.е., требует всего лишь небольшого вспомогательного

Сортировка слиянием
  Рассматривается сортировка слиянием (mergesort), которая является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов с последующей процедурой слияния.

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

Двоичный поиск
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится

Работа со словарем. Иоиск и вставка. Хеширование.
  Довольно часто встречаются ситуации, когда обработке подлежат много маленьких строк — слов, которые надо сохранять в некоторой единой структуре — словаре. Сами слова н

Файл dictionary.h
// Класс, представляющий словарь в виде хеш-таблицы classHashDictionary { private: static const intP = 557;

Файл dictionary.cpp
// Реализация функций intHashDictionary::code(char c) { returnstrchr("abcdefghijklmnopqrstuvwxyz&

Файл "hashtable.h".
  // Класс, представляющий хеш-таблицу пар (ключ, значение), причем // ключом является строка, а значением может быть произвольный объект. //В таблице хранятся не са

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги