Принцип алгоритма BM
Алгоритм BM разделен на две части
- правило плохого характера
- Правило хорошего суффикса
Сочетание этих двух правил может эффективно завершить сопоставление строк. Прежде чем описывать эти два правила, усвойте несколько понятий.
основная строка и строка шаблона
Как показано на рисунке, нам нужно найти, существует ли строка cbd в строке abcacabdc, тогда abcacabdc называется основной строкой, а cbd — строкой шаблона
правило плохого характера
В алгоритме BM, когда символы в строке шаблона сопоставляются с основной строкой, они сопоставляются с конца к началу., для приведенного выше рисунка первое сравнение заключается в том, что d в строке шаблона не равно c в основной строке, то в это времяосновная строкаc в называетсяплохой характер
плохой характер
Первый символ в строке шаблона, не равный основной строке (строка шаблона сопоставляется в обратном порядке), называется плохим символом (основной символ строки).
На данный момент плохим символом является c в основной строке.
В этот момент мы обозначаем положение плохого символа, соответствующего символу строки шаблона, как i, тогда i = 2 в это время
Хотя мы сопоставляем строку шаблона в обратном порядке, положение самой строки шаблона не меняется, то есть a b d соответствует индексу 0 1 2
движение струны узора
Итак, на сколько битов строка шаблона должна двигаться назад в это время?Метод подобен следующему.Найти позицию плохого символа в строке шаблона (найти первое совпадение с конца на начало и остановить) как k Значение по умолчанию is - 1 означает, что не найдено, затем переместите строку шаблона назад на i - k битов
В это время ищите строку шаблона abd через плохой символ c и обнаружите, что она не найдена, тогда k = -1, затем переместите 2 - (-1) = 3 бита, как показано ниже.
В это время неверным символом является а. Позиция символа в строке шаблона, соответствующая а, по-прежнему равна 2. Продолжайте поиск плохого символа в строке шаблона и найдите k = 0.
В это время строку шаблона необходимо переместить назад на i - k битов 2 - 0 = 2 бита, совпадение успешно
Кажется, что правила для плохих символов могут удовлетворять эффективному сопоставлению, но как насчет хороших правил для суффиксов?
Посмотрите на следующий сценарий: основная строка не изменилась, если предположить, что строка шаблона — dbca, тогда неверный символ соответствует позиции i = 0 в строке шаблона, а строка шаблона содержит неверный символ k = 3, затем шаблон строка должна двигаться назад на i - k = 0 - 3 = -3 бита, вы можете видеть, что вам нужно двигаться вперед в это время, и возникает ошибка, поэтому одного правила плохого символа недостаточно, и правило суффикса нужно сочетаться
Правило хорошего суффикса
Хорошим суффиксом является наличие эквивалентной строки для основной строки и строки шаблона.
Движение строки узора -1
Найдите в строке шаблона, есть ли строка с таким же хорошим суффиксом, если да, переместите ее назад, на позицию предыдущего хорошего суффикса, следующим образом
Так что, если строка шаблона не имеет той же строки, что и хороший суффикс?
Прежде чем говорить, вам нужно понять несколько концепций, чтобы помочь последующему пониманию.
- суффикс подстрока хорошего суффикса
- префикс подстроки строки шаблона
суффикс подстрока хорошего суффикса
Предположим, что строка шаблона — bccabc, а хороший суффикс в это время — abc, тогда ее подстроки суффикса соответственно
- bc
- c
префикс подстроки строки шаблона
Предположим, что строка шаблона — bccabc, а хороший суффикс в это время — abc, тогда его префиксные подстроки соответственно
- bc
- b
шаблон строки двигаться-2
При вычислении подстроки суффикса и подстроки префикса строки шаблона имеет смысл сохранять одинаковую длину, например, если суффикс составляет три бита abc, а его подстрока суффикса не более 2 бит, то при строка шаблона имеет хороший префикс. Вам нужно взять только первые 2 цифры.
Потому что взять 3 цифрыперемещение строки шаблона -1Есть и другие случаи, когда строка шаблона равна хорошему суффиксу. Сопоставление бессмысленно, если более 3 цифр
В это время подстрока суффикса bc хорошего суффикса abc точно такая же, как подстрока префикса bc строки шаблона, затем переместите подстроку префикса в строке шаблона в bc хорошего суффикса, как показано ниже.
В этот момент в строке шаблона bccabc находится bc, а затем он перемещается в текущую позицию. Наконец, совпадение успешно. Если последний символ не равен, это означает, что совпадение не удалось и не найдено.
Как выбрать, использовать ли правило плохих символов или правило хороших суффиксов для сопоставления строк
Как и раньше, ошибочное правило плохого символа может вызвать движение вперед, а хорошее правило суффикса можно использовать как обычно.
При выполнении алгоритма сопоставления эти два алгоритма можно использовать в комбинации для вычисления количества битов сдвига префикса, а затем вычислить количество битов сдвига правила суффикса и взять большее число в качестве реального количества битов сдвига назад. , что может обеспечить более эффективное сопоставление. , следующим образом
В этот момент переместите i - k = 5 - 3 = 2 бита по правилу плохого символа.
Если правило хорошего суффикса не соответствует, то сразу переместитесь назад на 6 цифр длины строки шаблона и выберите самые большие 6 цифр для перемещения.
Теперь переместите i - k = 3 - 5 = -2 бита в соответствии с правилом плохого символа.
Правило правильного суффикса перемещает 4 цифры (совпадающие с позицией правильного суффикса), в это время выберите самые большие 4 цифры для перемещения
Этот пример недостаточно хорош, нет ситуации, когда количество битов сдвинутых плохих символов > количество битов, сдвинутых хорошими суффиксами, но я понимаю смысл.
В это время i - k = 5 - 1 = 4 бита перемещаются назад в соответствии с правилом плохого символа, 2 бита перемещаются назад в соответствии с правилами хорошего суффикса, а больший бит перемещается назад на 4 бита следующим образом.
Дальнейшие правила движения такие же, как и раньше, поэтому я не буду их повторять.
обсуждение временной сложности
Я считаю, что каждый должен понять два правила и принципы алгоритма BM после приведенного выше объяснения, но кажется, что в соответствии с правилом плохого символа каждый раз, когда вы перемещаете плохой символ, вам нужно пройти по строке шаблона, чтобы найти его.
В хорошем суффиксе подстрока суффикса суффикса и подстрока префикса строки шаблона должны вычисляться каждый раз, а затем сравниваться, кажется, что производительность также будет затронута интуитивно.В этой статье не приводится подробная временная сложность BM (потому что она действительно сложнее)., но есть много возможностей для оптимизации с точки зрения реализации идей.
Реализация алгоритма и идеи оптимизации
При сопоставлении по правилу плохих символов каждый раз, когда необходимо пройти по строке шаблона, чтобы выяснить, есть ли плохие символы, здесь каждый символ строки шаблона может быть сохранен в хэш-таблице, такой как HashMap, и при поиске из него вы можете напрямую использовать карту, временную сложность O (1) для запроса.
При сопоставлении по правилам хороших суффиксных символов все подстроки подстроки префикса могут быть вычислены заранее и помещены в память.При совпадении хорошего суффикса, если длина строки хорошего суффикса равна 3, то мы сначала определить, находится ли строка шаблона в строке После того, как есть строка с тем же суффиксом, что и хороший суффикс, если нет, перейти непосредственно к ранее кэшированной подстроке префикса, чтобы найти подстроку префикса длины