Построение таблицы хороших суффиксов - Понимание примера

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

Итак, вот что: Следующий пример демонстрирует, как построить таблицу хороших суффиксов по шаблону ANPANMAN:

Index | Mismatch | Shift | goodCharShift
-----------------------------------------------
  0   |         N|   1   | goodCharShift[0]==1
  1   |        AN|   8   | goodCharShift[1]==8
  2   |       MAN|   3   | goodCharShift[2]==3
  3   |      NMAN|   6   | goodCharShift[3]==6
  4   |     ANMAN|   6   | goodCharShift[4]==6
  5   |    PANMAN|   6   | goodCharShift[5]==6
  0   |   NPANMAN|   6   | goodCharShift[6]==6
  0   |  ANPANMAN|   6   | goodCharShift[7]==6

Любая помощь по этому вопросу высоко ценится. Я просто не знаю, как добраться до этих номеров. Спасибо!

Источник

2 ответа

Решение

Это может помочь вам, хороший суффикс-стол.

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

Источник

Строка 1, ни один символ не соответствует, прочитанный символ не был N. Длина хорошего суффикса равна нулю. Поскольку в шаблоне много букв, которые также не являются N, мы имеем здесь минимальную информацию - сдвиг на 1 - наименее интересный результат.

Во второй строке мы сопоставили N, и этому предшествовало нечто, отличное от A. Теперь посмотрим на схему, начиная с конца, где у нас N предшествует чему-то другому, кроме A? Есть два других N, но оба предшествуют A. Это означает, что никакая часть хорошего суффикса не может быть полезна для нас - сдвиг на полную длину паттерна 8.

Строка 3: мы сопоставили AN, и ему предшествовал не M. В середине шаблона есть AN, которому предшествует P, поэтому он становится кандидатом на сдвиг. Сдвиг, что AN справа, чтобы выровняться с нашим матчем, это сдвиг 3.

Строки 4 и выше: совпадающие суффиксы не соответствуют ничему другому в шаблоне, но конечный суффикс AN соответствует началу шаблона, поэтому сдвиги здесь равны 6.

Источник

Хотя это старый вопрос, и ответ на него принимается, но я просто хочу добавить PDF-файл из JHU, который довольно хорошо объясняет правила хороших суффиксов. http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf

Этот pdf-файл делает мою жизнь намного проще. Так что надеюсь, что это поможет и людям, которые борются с пониманием этого алгоритма.

Источник
Другие вопросы по тегам