Эвристика хорошего суффикса Бойер-Мура

Ответ 1

Сначала я использую p[i] символ в шаблоне, m длину шаблона, $ последний символ в шаблоне, т.е. $ = p[m-1].

Существует два сценария для случая эвристики хорошего суффикса 1.

Ситуация 1

Рассмотрим следующий пример:

    leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
         cXXXbXXXcXXXcXXX
                     ^ 
                     | mismatch here

Таким образом, подстрока XXX в шаблоне cXXXbXXXcXXXcXXX является хорошим суффиксом. Несоответствие происходит при значении c. Поэтому после несоответствия нам следует сдвинуть 4 вправо или 8?

Если мы сдвинем 4, как в следующем, то снова будет повторяться тот же самый несоответствие (b mismathes c),

    leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
             cXXXbXXXcXXXcXXX
                     ^ 
                     | mismatch occurs here again

Таким образом, в этой ситуации мы можем сдвинуть 8 символов вправо.

Ситуация 2

Посмотрим на другой пример

    leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
            cXXXXcXXXbXXXcXXX
                         ^ 
                         | mismatch happens here

Можно ли переместить 4 или 8 или более? Очевидно, что если мы сдвинем 8 или более, мы упустим возможность сопоставить шаблон с текстом. Поэтому в этой ситуации мы можем сдвигать только 4 символа вправо.

В чем разница между этими двумя ситуациями?

Разница в том, что в первом случае несогласованный символ c плюс хороший суффикс XXX, который равен cXXX, совпадает с следующим (счетчик справа) для XXX plus характер до этого. В то время как во второй ситуации cXXX не совпадает с следующим совпадением (счетчик справа) плюс символ перед этим совпадением.

Итак, для любого данного GOOD SUFFIX (назовем его XXX) нам нужно выяснить смещение в этих двух ситуациях: (1) символ (назовем его c) до GOOD SUFFIX плюс GOOD SUFFIX, в шаблоне также соответствует следующему (счету справа) совпадению хорошего суффикса + персонажу перед ним, (2) символ плюс GOOD SUFFIX не соответствует

Для ситуации (1), например, если у вас есть шаблон, 0XXXcXXXcXXXcXXXcXXXcXXX, если после первого теста c не удастся, вы можете сдвинуть 20 символов вправо и выровнять 0XXX с текстом который был протестирован.

Так вычисляется число 20,

              1         2
    012345678901234567890123
    0XXXcXXXcXXXcXXXcXXXcXXX
    ^                   ^

Позиция, в которой происходит несоответствие, равна 20, сдвинутая подстрока 0XXX займет позицию от 20 до 23. И 0XXX начинается с позиции 0, поэтому 20 - 0 = 20.

Для ситуации (2), как в этом примере, 0XXXaXXXbXXXcXXX, если после первого теста c не удастся, вы можете сдвинуть только 4 символа вправо и выровнять bXXX с текстом, который был протестирован.

Так вычисляется число 4,

    0123456789012345
    0XXXaXXXbXXXcXXX

Позиция, в которой происходит несоответствие, равна 12, следующая подстрока, которая занимает это место, равна bXXX, которая начинается с позиции 8, 12 - 8 = 4. Если мы установим j = 12 и i = 8, тогда сдвиг j - i, что в коде <<234 > .

Граница

Чтобы рассмотреть весь хороший суффикс, нам сначала нужно понять, что такое так называемый border. Граница - это подстрока, которая является префиксом proper и суффиксом proper строки. Например, для строки XXXcXXX, X является границей, XX является границей, XXX тоже. Но XXXc нет. Нам нужно определить начальную точку самой широкой границы суффикса шаблона, и эта информация сохраняется в массиве f[i].

Как определить f[i]?

Предположим, что мы знаем f[i] = j и для всех остальных f[k] с i < k < m, что означает самую широкую границу для суффикса, начиная с позиции i, начатого в позиции j. Мы хотим найти f[i-1] на основе f[i].

Например, для шаблона aabbccaacc в postion i=4 суффикс ccaacc, а самая широкая граница для него - cc (p[8]p[9]), поэтому j = f[i=4] = 8. И теперь мы хотим знать f[i-1] = f[3] на основе информации, которую мы имеем для f[4], f[5],... Для f[3] суффикс теперь равен bccaacc. В позиции j-1=7 это a!= p[4-1], который равен b. Таким образом, bcc не является границей.

Мы знаем, что любая граница с шириной >= 1 из bccaacc должна начинаться с b плюс граница суффикса, начиная с positin j = 8, которая в этом примере cc. cc имеет самую широкую границу c в позиции j = f[8], которая 9. Поэтому мы продолжаем поиск с сравнения p[4-1] с p[j-1]. И они снова не равны. Теперь суффикс p[9] = c, и он имеет только границу с нулевой длиной в позиции 10. поэтому теперь j = f[9] и это 10. Таким образом, мы продолжаем поиск при сравнении p[4-1] с p[j-1], они не равны и это конец строки. Тогда f[3] имеет только границу с нулевой длиной, которая делает ее равной 10.

Чтобы описать процесс в более общем смысле

Следовательно, f[i] = j означает что-то вроде этого,

    Position:    012345     i-1  i     j - 1   j       m
    pattern:     abcdef ... @    x ... ?       x ...   $ 

Если символ @, который в позиции i - 1 совпадает с символом ? в позиции j - 1, мы знаем, что f[i - 1] = j - 1; или --i; --j; f[i] = j;. Граница - это суффикс @x ... $, начиная с позиции j-1.

Но если символ @, который в положении i - 1 отличается от символа ? в позиции j - 1, мы должны продолжить поиск справа. Мы знаем два факта: (1) мы знаем, что ширина границы должна быть меньше той, которая начиналась с позиции j, т.е. Меньше x...$. Во-вторых, граница должна начинаться с @... и заканчивается символом $, или она может быть пустой.

Исходя из этих двух фактов, мы продолжаем наш поиск в подстроке x ... $ (от позиции j до m) для границы, начинающейся с X. Затем следующая граница должна быть в j, которая равна f[j];, т.е. j = f[j];. Затем мы сравниваем символ @ с символом до X, который находится на j-1. Если они равны, мы обнаружили границу, если нет, продолжаем процесс до j > m. Этот процесс показан следующим кодом:

    while (j<=m && p[i-1]!=p[j-1])
    {
        j=f[j];
    }

    i--; j--;
    f[i]=j;

Теперь рассмотрим условие p[i -1] != p [j-1] , this is what we talked about in situation (2), p [i] matches p [j] , but p [i -1]!= p[j-1], поэтому мы переходим от i до j, то есть s[j] = j - i;.

Теперь единственное, что не объяснено, - это тест if (s[j] == 0), который будет иметь место, когда более короткий суффикс имеет одинаковую границу. Например, у вас есть шаблон

    012345678
    addbddcdd

Когда вы вычисляете f[i - 1] и i = 4, вы установите s[7]. Но когда вы вычисляете f[i-1] для i = 1, вы снова установите s[7], если у вас нет теста if (s[j] == 0). Это означает, что если у вас есть несоответствие в позиции 6, вы сдвигаете 3 вправо (выровняйте bdd в позиции cdd заняты) не 6 (не сдвигайте до add в позиции cdd занято).

Комментарии для кода

    void bmPreprocess1()
    {
        // initial condition, set f[m] = m+1;
        int i=m, j=m+1;

        f[i]=j;

        // calculate f[i], s[j] from i = m to 0.
        while (i>0)
        {
            // at this line, we know f[i], f[i+1], ... f[m].
            while (j<=m && p[i-1]!=p[j-1]) // calculate the value of f[i-1] and save it to j-1
            {
                if (s[j]==0) s[j]=j-i; // if s[j] is not occupied, set it.
                j=f[j]; // get the start position of the border of suffix p[j] ... p[m-1]
            }
            // assign j-1 to f[i-1]
            i--; j--;
            f[i]=j;
        }
    }