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

Цель лекции: изучить основные алгоритмы поиска в тексте и научиться решать задачи поиска в тексте на основе алгоритмов прямого поиска; Кнута, Морриса и Пратта; Боуера и Мура.

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

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

Алфавит – конечное множество символов.

Строка (слово) – это последовательность символов из некоторого алфавита. Длина строки – количество символов в строке.

Строку будем обозначать символами алфавита, например X=x[1]x[2]...x[n] – строка длиной n, где x[i] – i -ый символ строки Х, принадлежащий алфавиту. Строка, не содержащая ни одного символа, называется пустой.

Строка X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. При этом Z1 называют левым, а Z2 – правым крылом подстроки. Подстрокой может быть и сама строка. Иногда при этом строку X называют вхождением в строку Y. Например, строки hrf и fhr является подстроками строки abhrfhr.

Подстрока X называется префиксом строки Y, если есть такая подстрока Z, что Y=XZ. Причем сама строка является префиксом для себя самой (так как найдется нулевая строка L, что X=XL ). Например, подстрока ab является префиксом строки abcfa.

Подстрока X называется суффиксом строки Y, если есть такая подстрока Z, что Y=ZX. Аналогично, строка является суффиксом себя самой. Например, подстрока bfg является суффиксом строки vsenfbfg.

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

Рассмотрим несколько известных алгоритмов поиска подстроки в строке более подробно.

Прямой поиск

Данный алгоритм еще называется алгоритмом последовательного поиска, он является самым простым и очевидным.

Основная идея алгоритма прямым поиском заключается в посимвольном сравнении строки с подстрокой. В начальный момент происходит сравнение первого символа строки с первым символом подстроки, второго символа строки со вторым символом подстроки и т. д. Если произошло совпадение всех символов, то фиксируется факт нахождения подстроки. В противном случае производится сдвиг подстроки на одну позицию вправо и повторяется посимвольное сравнение, то есть сравнивается второй символ строки с первым символом подстроки, третий символ строки со вторым символом подстроки и т. д. (рис 39.1) Символы, которые сравниваются, на рисунке выделены жирным. Рассматриваемые сдвиги подстроки повторяются до тех пор, пока конец подстроки не достиг конца строки или не произошло полное совпадение символов подстроки со строкой, то есть найдется подстрока.

//Описание функции прямого поиска подстроки в строке
int DirectSearch(char *string, char *substring){
  int sl, ssl;
  int res = -1;
  sl = strlen(string);
  ssl = strlen(substring);
  if ( sl == 0 ) 
    cout << "Неверно задана строка\n"; 
  else if ( ssl == 0 ) 
    cout << "Неверно задана подстрока\n"; 
  else
    for (int i = 0; i < sl - ssl + 1; i++)
      for (int j = 0; j < ssl; j++)
        if ( substring[j] != string[i+j] )
          break;
        else if ( j == ssl - 1 ){
          res = i;
          break;
        }
  return res;
}

Данный алгоритм является малозатратным и не нуждается в предварительной обработке и в дополнительном пространстве. Большинство сравнений алгоритма прямого поиска являются лишними. Поэтому в худшем случае алгоритм будет малоэффективен, так как его сложность будет пропорциональна O((n-m+1)xm), где n и m – длины строки и подстроки соответственно.

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

Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они совместно опубликовали в 1977 году. Алгоритм Кнута, Морриса и Пратта (КМП-алгоритм) является алгоритмом, который фактически требует только O(n) сравнений даже в самом худшем случае. Рассматриваемый алгоритм основывается на том, что после частичного совпадения начальной части подстроки с соответствующими символами строки фактически известна пройденная часть строки и можно, вычислить некоторые сведения, с помощью которых затем быстро продвинуться по строке.

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

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

//описание функции алгоритма Кнута, Морриса и Пратта
int KMPSearch(char *string, char *substring){
  int  sl, ssl;
  int res = -1;
  sl = strlen(string);
  ssl = strlen(substring);
  if ( sl == 0 ) 
    cout << "Неверно задана строка\n"; 
  else if ( ssl == 0 ) 
    cout << "Неверно задана подстрока\n"; 
  else {
    int  i, j = 0, k = -1;
    int  *d;
    d = new int[1000];
    d[0] = -1;
    while ( j < ssl - 1 ) {
      while ( k >= 0  substring[j] != substring[k] ) 
        k = d[k];
      j++;
      k++;
      if ( substring[j] == substring[k] )
        d[j] = d[k];
      else 
        d[j] = k;
    }
    i = 0;
    j = 0;
    while ( j < ssl  i < sl ){
      while ( j >= 0  string[i] != substring[j] )
        j = d[j];
      i++;
      j++;
    }
    delete [] d;
    res =  j == ssl ? i - ssl : -1;
  }
  return res;
}

Точный анализ рассматриваемого алгоритма весьма сложен. Д. Кнут, Д. Моррис и В. Пратт доказывают, что для данного алгоритма требуется порядка O(m+n) сравнений символов (где n и m – длины строки и подстроки соответственно), что значительно лучше, чем при прямом поиске.

Алгоритм Бойера и Мура

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

Существует множество вариаций алгоритма Бойера и Мура, рассмотрим простейший из них, который состоит из следующих шагов. Первоначально строится таблица смещений для искомой подстроки. Далее идет совмещение начала строки и подстроки и начинается проверка с последнего символа подстроки. Если последний символ подстроки и соответствующий ему при наложении символ строки не совпадают, подстрока сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа подстроки. Если же символы совпадают, производится сравнение предпоследнего символа подстроки и т.д. Если все символы подстроки совпали с наложенными символами строки, значит, найдена подстрока и поиск окончен. Если же какой-то (не последний) символ подстроки не совпадает с соответствующим символом строки, далее производим сдвиг подстроки на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомой подстроки, либо не будет достигнут конец строки (рис 39.3). На рисунке символы, подвергшиеся сравнению, выделены жирным шрифтом.

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

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

//описание функции алгоритма Бойера и Мура
int BMSearch(char *string, char *substring){
  int  sl, ssl;
  int res = -1;
  sl = strlen(string);
  ssl = strlen(substring);
  if ( sl == 0 ) 
    cout << "Неверно задана строка\n"; 
  else if ( ssl == 0 ) 
    cout << "Неверно задана подстрока\n"; 
  else {
    int  i, Pos;
    int  BMT[256];
    for ( i = 0; i < 256; i ++ )
      BMT[i] = ssl;
    for ( i = ssl-1; i >= 0; i-- )
      if ( BMT[(short)(substring[i])] == ssl ) 
        BMT[(short)(substring[i])] = ssl - i - 1;
    Pos = ssl - 1;
    while ( Pos < sl )
      if ( substring[ssl - 1] != string[Pos] )
        Pos = Pos + BMT[(short)(string[Pos])];
      else 
        for ( i = ssl - 2; i >= 0; i-- ){
          if ( substring[i] != string[Pos - ssl + i + 1] ) {
            Pos += BMT[(short)(string[Pos - ssl + i + 1])] - 1;
            break;
          }
          else
            if ( i == 0 )
              return Pos - ssl + 1;
          cout << "\t" << i << endl;
        }
  }
  return res;
}

Алгоритм Бойера и Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск. Таким образом, данный алгоритм является наиболее эффективным в обычных ситуациях, а его быстродействие повышается при увеличении подстроки или алфавита. В наихудшем случае трудоемкость рассматриваемого алгоритма O(m+n).

Существуют попытки совместить присущую алгоритму Кнута, Морриса и Пратта эффективность в "плохих" случаях и скорость алгоритма Бойера и Мура в "хороших" – например, турбо-алгоритм, обратный алгоритм Колусси и другие.

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

Ключевые термины

Алгоритм Бойера и Мура – это алгоритм поиска подстроки в строке, при котором первоначально строится таблица смещений для искомой подстроки, проверка начинается с последнего символа подстроки после совмещения начала строки и подстроки.

Алгоритм Кнута, Морриса и Пратта – это алгоритм поиска подстроки в строке, при котором сдвиг подстроки выполняется на некоторое переменное количество символов.

Алгоритм прямого поиска – это алгоритм поиска подстроки в строке, при котором происходит посимвольное сравнение строки с подстрокой.

Алфавит – конечное множество символов

Длина строки – количество символов в строке

Подстрока – это последовательность подряд идущих символов в строке.

Префикс – это подстрока, начинающаяся с первого символа строки.

Строка – это последовательность символов.

Суффикс – это подстрока, заканчивающаяся на последний символ строки.

Краткие итоги

Лабораторная работа 39. Алгоритмы поиска в тексте

Цель работы: изучить основные алгоритмы поиска в тексте и научиться решать задачи поиска в тексте на основе алгоритмов прямого поиска; Кнута, Морриса и Пратта; Боуера и Мура.

При выполнении лабораторной работы для каждого задания требуется написать программу на языке С++, которая получает на данные из входного файла, выполняет их обработку в соответствии с требованиями задания и выводит результат в выходной файл. Для обработки данных необходимо реализовать функции алгоритмов Кнута-Морриса-Пратта и Боуера-Мура для поиска в тексте. Ограничениями на входные данные является максимальный размер строковых данных, допустимый диапазон значений используемых числовых типов в языке С++.

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

Ознакомьтесь с материалом лекции 39.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

abababa

2

abcdefghijklmnopqrstuvwxyz
Abcd?aBcd!abCd.abcD!?

3

a123bc9e9c321

5

Указания к выполнению работы.

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

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы