Каковы правила сдвига для алгоритма поиска строки Бойера – Мура?

Question

Я пытался понять правила сдвига в алгоритме поиска строк Бойера – Мура, но не понял их. Я читал здесь в Википедии, но это слишком сложно!

Будет очень полезно, если кто-то перечислит правило простым способом.

Answer 1

В алгоритме Бойера-Мура вы начинаете сравнивать символы шаблона с текстовыми символами с конца шаблона. Если вы обнаружите несоответствие, у вас есть конфигурация типа

....xyzabc....      <-text
  ....uabc          <- pattern
      ^
    mismatch

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

Это может быть сдвиг влево, если ситуация

     v
...xyzazc...
 ....uazc
 ..uazc

так что само по себе это не гарантирует прогресс.

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

Так например

           v
....abcdabceabcfabc...
    ...xabcfabcfabc
        ...xabcfabcfabc

приведет к хорошему сдвигу суффикса на четыре позиции, так как согласованная часть m = abcfabc встречается в шаблоне в четырех местах слева от его вхождения-суффикса, и ему предшествует другой символ (x вместо f), чем в позиции суффикса.

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

      v
...robocab....
    abacab
        abacab

Хороший сдвиг суффикса всегда смещает шаблон вправо, поэтому гарантирует прогресс.

Затем при каждом несоответствии сравниваются достижения сдвига плохого символа и сдвига хорошего суффикса, и выбирается большее. Это более подробно объясняется здесь Кристианом Чаррасом и Тьерри Лекроком, а также многими другими алгоритмами поиска строк.

---

Для примера, который вы упомянули в комментариях,

SSIMPLE EXAMPLE
EXAMPLE
  ^

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

SSIMPLE EXAMPLE
   EXAMPLE

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

SSIMPLE EXAMPLE
      EXAMPLE

Хороший сдвиг суффикса сдвигает образец дальше вправо, так что это выбранный сдвиг.

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

Тогда у нас есть полный матч.

В варианте с рисунком TXAMPLEпри хорошем сдвиге суффикса обнаруживается, что ни один непустой суффикс совпадающей части не является префиксом шаблона (и в шаблоне не встречается полная совпадающая часть, которой не предшествует A), поэтому хороший сдвиг суффикса выравнивает пустой суффикс совпадающей части текста (граница между E и пробел) с пустым префиксом шаблона (пустая строка, предшествующая T), в результате чего

SSIMPLE EXAMPLE
       TXAMPLE

(затем на следующем шаге сдвиг плохого персонажа выравнивает два Ls, и следующее несоответствие на последующем этапе происходит на начальном этапе. T шаблона).

Answer 2

Здесь хорошая визуализация .

(РЕДАКТИРОВАТЬ: Есть также очень хорошее объяснение с обоими примерами и примером того, как реализовать шаги предварительной обработки здесь.)

Основные правила:

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

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

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

Например, давайте рассмотрим следующую ситуацию:

• Моя картина заканчивается "собакой".
• В настоящее время я выровняю его по части текста, которая оканчивается на "собаку".
• Следовательно, плохая буква - это 's' (где они перестают соответствовать), а хороший суффикс - 'собака' (та часть, которая действительно соответствует).

У меня есть два варианта здесь:

1. Сдвиньте так, чтобы первые 's' (справа налево) в шаблоне были выровнены с 's' в тексте. Если в шаблоне нет 's', сдвиньте начало шаблона так, чтобы оно было сразу после 's'.
2. Сдвиньте так, чтобы следующая "собака" выровнялась с "собакой" в тексте. Если в паттерне нет другой "собаки", сместите начало паттерна так, чтобы оно было сразу за концом "собаки".

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

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

Answer 3

Есть две эвристики: эвристика символа летучей мыши и эвристика хорошего образца.

Во-первых, вы знаете, сравнение игл начинается с его конца. Таким образом, если символы не совпадают со смещением иглы, то, по крайней мере, сравниваемый символ в стоге сена будет соответствовать игле. Например "игла" - это "ABRACADABRA", а текущий символ в стоге сена - "B", она не соответствует последней "A", а также не соответствует предыдущей "R", поэтому сдвиг на единицу не имеет смысла, совпадений не будет. Но "Б" соответствует 2-му от конца символа в игле. Так что мы бы сдвинули иглу как минимум на 2 позиции. Если текущий символ в стоге сена не совпадает ни с одним в игле, иглу необходимо сместить за пределы текущего символа. Другими словами, мы смещаем шаблон до тех пор, пока текущий символ в стоге сена не совпадет с символом в игле или пока вся стрелка не сместится за пределы.

Величина сдвига вычисляется и сохраняется в массиве, поэтому для "ABRACADABRA" это будет: ['R'] = 1, ['B'] = 2, ['D'] = 4 и т. Д.

haystack: XYABRACADABRA...
                    |
needle:   ABRACADABRA
           ABRACADABRA <-- pointless shift: R will not match B
            ABRACADABRA

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

Величина сдвига для согласованной детали также предварительно рассчитывается: например, ['A'] = 3, ['RA'] = 11, ['BRA'] = 11, ['ABRA'] = 7, ['DABRA'] = 7...

haystack: XYZYXADABRACADABRA...
needle:   ABRACADABRA           (shift to ABRA from matched ADABRA)
          ~~~~   ~~~~
                 ABRACADABRA

Это не полное объяснение всех угловых случаев, а основная идея алгоритма.