Описание эвристики "хорошего суффикса" с примерами¶

Для начала - как эвристика вообще работает.

Пусть для данного выравнивания паттерна P и текста T подстрока t текста T совпадает с суффиксом P, но левее t происходит несовпадение.

SAGGTAGACTAAGACTTACCCAT
     GAAGCAAG

t = AAG

Тогда, если существует, найдем самое правое вхождение t' == t в паттерн P, такое, что символ левее P отличается от символа левее t в паттерне P.

SAGGTAGACTAAGACTTACCCAT
     GAAGCAAG

t = AAG после C
t' = AAG после G

Сдвинем паттерн P вправо так, чтобы t' из паттерна совпадало с t из текста.

SAGGTAGACTAAGACTTACCCAT
         GAAGCAAG

Если же t' в паттерне P не существует, до сдвинем левый край P левее t из текста T как можно меньше, чтобы префикс P совпадал с суффиксом t, если такой префикс существует.

паттерн изменен на AGAGCAAG с целью демонстрации

SAGGTAGACTAAGACTTACCCAT
          |AGAGCAAG
          |||
          |||
          AAGAGCAAG

Если префикса нет, сдвинем паттерн левее подстроки t из текста.

SAGGTAGACTAAGACTTACCCAT
             TCAGCAAG

На примере фразы¶

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

HERE IS A SIMPLE EXAMPLE -> HERE IS A SIMPLE EXAMPLE   
      MPLEXAMPLE         ->             MPLEXAMPLE
           ^

Для сравнения, "плохой символ" в той же ситуации дает меньший сдвиг:

HERE IS A SIMPLE EXAMPLE -> HERE IS A SIMPLE EXAMPLE
        IEXAMPLE         ->            IEXAMPLE

В алгоритме Бойера-Мура после вычисления выбирается лучшая эвристика

Расчет эвристики "хорошего суффикса"¶

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

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

1  MatchLength(string, i, j):
2      if i == j:
3          return Length(string) - i
4       match_length = 0 
5       ls = Length(s)
6       while i < ls and j < ls and string[i] == string[j]
7            match_length += 1
8            i += 1
9            j += 1
10      return match_length

Если вернуться к примеру выше, эта функция дала бы примерно такие результаты:

MatchLength(GAAGCAAG, 1, 5) == 3

Т.е. следующие три символа после 1-го и 5-го включительно совпадают:

GAAGCAAG

Какие таблицы понадобятся для работы алгоритма¶

Для работы алгоритма используются две одномерные таблицы: L и F. Таблица F используется только в случае, если L[i] содержит "пустое" значение, или найдено совпадение паттерна и подстроки.

В таблице L содержится следующая информация:

Для всех i, L[i] содержит наибольшую (самую правую) позицию меньше n, такую, что строка P[i..n] совпадает с суффиксом P[1..L[i]], и символ, предшествующий этому суффиксу, не равен P[i-1] (то есть символу до P). Если такой позиции нет, L[i] равен 0.

Таблица F описывает величину наибольшего суффикса P[i..n] для F[i], который также является префиксом P. если такого суффикса нет, P[i] = 0

Пока становится только запутанее. Давайте посмотрим на примеры

Предобработка¶

Функция FindPrefixes(string) возвращает массив Z такой, что Z[i] содержит число, равное длине подстроки S[i], котороая при этом является и префиксом S. Если такого префикса нет, то Z[i] будет 0.

Пример:

FindPrefixes("coconut")
--
[7, 0, 2, 0, 0, 0, 0]

FindPrefixes("aaaaaaa")
--
[7, 6, 5, 4, 3, 2, 1]

Домашнее задание - реализовать данную функцию.

Как вы уже могли преположить, данная функция используется для создания таблиц L и H.

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

FindPrefixes(Reversed("EXAMPLE"))
--
[7, 0, 0, 0, 0, 0, 1]

FindPrefixes("ELMAXE")
--
[7, 0, 0, 0, 0, 0, 1]

Создание таблицы сдвигов L¶

По умолчанию используется эта таблица. Что она содержит?

При помощи этой таблицы можно вычислить сдвиг, если не совпал i-1 элемент, по следующей формуле:

shift = Length(pattern) - L[i] - 1

GoodSuffixTable("EXAMPLE")
--
  E   X   A   M   P   L   E
[-1, -1, -1, -1, -1, -1,  0]
-- Сдвиг
[ -,  -,  -,  -,  -,  -,  -,  7]

- здесь единственный совпадающий суффикс - это последняя 'E'

GoodSuffixTable("GAAGCAAG")
--
  G   A   A   G   C   A   A   G
[-1, -1, -1, -1, -1,  3, -1,  0]
-- Сдвиг
[ -,  -,  -,  -,  -,  4,  -,  7]

"G" в центре паттерна игнорируется, так как сдвигаться до суффикса 'G' перед которым идет 'A', когда алгоритм "споткнулся" об "AG", бессмысленно. Получается, что "сдвиг" нужен до первой 'G'.

GoodSuffixTable("GATGCAAG")
--
  G   A   T   G   C   A   A   G
[-1, -1, -1, -1, -1, -1, -1,  3]
-- Сдвиг
[ -,  -,  -,  -,  -,  -,  -,  4]

А теперь все нормально, потому что в центре перед 'G' расположено 'T', а не 'A'.

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

SAGGTAGACTAAGACTTACCCAT
     GAAGCAAG

После сдвига:

SAGGTAGACTAAGACTTACCCAT
         GAAGCAAG

Совпадение строки с самой собой не важно, поэтому L[0] = -1. Если L[i] сожержит -1 (подходящего суффикса нет), осуществляется переход к следуюущей таблице, "таблице полного сдивга" H ("full shift table"). В случае, если произошло несовпадение символов текста и паттерна на i-1-м символе, выполняется сдвиг на Length(pattern) - L[i].

L[i] = k, где S[i:] совпадает с S[:k]. Несовпадающие суффиксы равны -1. Например, для EXAMPLE будет:

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

GoodSuffixTable(string):
    L = new Array[Int] of -1 of size Length(string)
    Z = FindPrefixes(Reversed(S)) 
    Z = Reverse(Z)
    for j in 0..Length(S)-1 exclusively:
        i = Length(S) - Z[j]
        if i != Length(S):
            L[i] = j
    return L

Создание таблицы полного сдвига H¶

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

Используется схожим с таблицей L образом: если i-1-й элемент паттерна не совпал, то паттерн перемещается на Length(P) - F[i] вправо.

По сути, это таблица, содержащую размеры следующей вещи: самого длинного суффикса строки S[i:] (можно сказать, что это суффикс суффикса паттерна), который одновременно является и префиксом S.

На примере "EXAMPLE":

FullShiftTable("BONOBO")
--
               'O'
            'B  O'
         'O  B  O'
      'N  O  B  O'
   'O  N  O  B  O'
'N  O  N  O  B  O'
--
[6, 2, 2, 2, 2, 0]
-- Сдвиг
[0, 4, 4, 4, 4, 6]

- Другой пример:

FullShiftTable("EXAMPLE")
--
[7, 1, 1, 1, 1, 1, 1]
-- Сдвиг
[0, 6, 6, 6, 6, 6, 6]

Псевдокод функции

FullShiftTable(string):
    F = new Array[Int] of 0 of size Length(string)
    Z = FindPrefixes(string)
    Z = Reversed(Z)
    longest = 0
    for i in Length(Z):
        if Z[i] == i+1:
            longest = max(Z[i], longest)
        else:
            longest
        F[-i-1] = longest
    return F

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

Теперь мы (надеюсь) готовы к тому, чтобы добавить эвристику "хорошего суффикса" к основному алгоритму.

Добавим новую эвристику в алгоритм Бойера-Мура-Хорспула:

BoyerMoore(pattern, text):
    lp = Length(pattern)
    lt = length(text)

    if lp == 0 or lt == 0 or lt < lp:
        return []

    matches = new List

    bad_character = BadCharacterTable(pattern)
    L = GoodSuffixTable(pattern)
    F = FullShiftTable(pattern) 

    previous_k = -1
    shift = 0

    while i >= 0 and shift + i > previous_k and pattern[i] = text[shift+i]:
        i -= 1

    if i == -1 or shift + i == previous_k:
        matches.append(shift)
    else:
        char_shift = i - bad_character[AlphabetIndex(text[shift + i])][i]
        if i + 1 == lp:
            suffix_shift = 1
        else if L[i+1] == -1:
            suffix_shift = lp - F[i+1]
        else:
            suffix_shift = lp - L[i+1] - 1
        max_shift = Max(char_shift, suffix_shift)
        if max_shift == i+1:
            previous_k = matches[-1] if matches is not empty else -1
        shift += max_shift

    return matches

</font>