Эвристика безопасного суффикса

Рассмотрим несколько примеров.

Пример 1.S=”abababbaab”, W=”abbaab”.

Сначала сравниваем суффикс S₆ и W. Как уже отмечалось, сравнение производим справа налево. Выясняется, что максимальный совпадающий суффикс S₆ и W”ab” состоит из двух символов. Ближайшее справа вхождение подстроки ”ab” в строку W начинается с позиции 0, поэтому далее можно сравнивать с W уже S_{6+strlen(W)-strlen(”ab”)+0}=S₁₀, т.к. при таком сдвиге впервые та же самая подстрока ”ab” строки S совпадет с соответствующей подстрокой W.

Иными словами, в этом примере мы искали максимальное i<6, такое что ”ab” являлась суффиксом W_i. Следующий претендент на сравнение вычислялся по формуле S_{6+strlen(W)-i}.

Пример 2.S=”abababbaab”, W=”bbbaab”.

Сначала, как и в предыдущем примере, сравниваем суффикс S₆ и W. Как уже отмечалось, сравнение производим справа налево. Выясняется, что максимальный совпадающий суффикс S₆ и W”ab” состоит из двух символов. Подстрока ”ab” больше в строку W не входит. Однако максимальное начало строки W, совпадающее с соответствующим суффиксом ”ab”, имеет длину 1,поэтому далее можно сравнивать с W уже S_{6+strlen(W)-strlen(”ab”)+1}=S₁₁. Действительно, при таком сдвиге впервые часть той же самой подстрока ”ab” строки S (имеется в виду подстрока ”b”) совпадет с соответствующей подстрокой W.

Иными словами, в этом примере мы искали максимальное i£2, такое что W_i являлась бы суффиксом ”ab”. Следующий претендент на сравнение вычислялся по формуле S_{6+strlen(W)-i} (сравнить с предыдущим примером).

Введем обозначение. Будем говорить, что строки A и B сравнимы: A ~B, если A является суффиксом B или B является суффиксом A.

Обобщая приведенные примеры, мы можем сказать, что мы искали максимальное i<strlen(W), такое что W_i~”ab”.

Введем функцию g, такую что g(l) равна максимальному i<strlen(W), такому, что W_i сравнима с суффиксом W длины l. Если такого не нашлось, то g(l)=0.

Пусть сравнивается суффикс S_k и W. Пусть C - максимальный по длине общий суффикс S_k и W. Следующим претендентом на сравнение будет

S_{k+ strlen(W) - g(strlen(C))}.

Осталось выяснить – каким образом задать функцию g(l).

По определению g(l)=Max{i<strlen(W): W_i~Suff(W,l)}, где Suff(W,l) – суффикс W длины l. То же самое можно переписать иначе:

g(l) = Max{ Max{i<strlen(W): W_i– суффиксSuff(W,l)},

Max{i<strlen(W): Suff(W,l) – суффикс W_i} }

Выше мы ввели функцию p(i), равную максимальной длине суффикса строки W_i, являющегося префиксом W. По определению имеем, что W_p(strlen(W)) является суффиксом W, поэтому W_p(strlen(W)) ~ Suff(W,l). Из последнего вытекает, что

g(l) ³ p(strlen(W))

Т.о. получаем

g(l) = Max{ Max{i<strlen(W): W_i– суффиксSuff(W,l)},

Max{i<strlen(W): Suff(W,l) – суффикс W_i} }

Более того, Max{i<strlen(W): W_i– суффиксSuff(W,l)} не может превзойти W_p(strlen(W)), т.к. если бы это произошло, то мы получили бы суффикс Suff(W,l) (а следовательно и суффикс W), являющийся префиксом W, длиной больше максимально возможной длины суффикса W, являющегося префиксом W. Т.о. получаем

g(l) = Max{ p(strlen(W)), Max{ p(strlen(W))£i<strlen(W): Suff(W,l) – суффикс W_i} }

Легко увидеть, что поиск

w(l)=Max{ p(strlen(W))£i<strlen(W): Suff(W,l) – суффикс W_i}

сводится к поиску самого правого участка строки W, совпадающего с Suff(W,l) (естественно, рассматриваются участки левее самого Suff(W,l)).

Пример:

l=2; W=” abac ab ac ab”;// выделен Suff(W,l) и его правое вхождение в W

Отметим, что такого участка может не существовать. Если рассмотреть строку W’, представляющую собой перевернутую строку W, то задачу можно свести к поиску самого левого вхождения строки W’_l в строку W’ (правее начальной позиции):

w(l)=Max{ p(strlen(W))£i<strlen(W): Suff(W,l) – суффикс W_i} =

=strlen(W) - Min{ i>l: W’_l – суффикс W_i}+l

Пример:

l=2; W’=”ba ca ba caba ”;// выделен W’_l и его левое вхождение в W

Рассмотрим начало строки W’, завершающееся найденным левым вхождением W’_l в строку W (в примере это – ”ba ca ba”). Более формально: рассмотрим W’_I, где I=argMin{ i>l: W’_l – суффикс W_i}.

Легко увидеть: l=p’(I), где p’ – префикс-функция W’. Действительно, если бы нашелся больший суффикс W’_I, являющийся одновременно префиксом W’, то, соответственно, нашлось бы и более левое вхождение подстроки W’_l в строку W (т.к. начало более длинного суффикса должно совпадать с W’_l).

С другой стороны равенство l==p’(I) влечет за собой тот факт, что W’_l является суффиксом W’_I.

Т.о. имеем

Min{ i>l: W’_l – суффикс W_i} = Min{ i>l: l==p’(i)}

Тогда получаем

w(l)= strlen(W) +l - Min{ i>l: l==p’(i)}

Последнее равенство дает алгоритм вычисления w(t): следует перебрать все значения i в порядке убывания и для каждого из них выполнить присвоение

w[p’(i)]= strlen(W) + p’(i) – i если i>p’(i)

В конце концов, получаем

g[l] = Max{ p(strlen(W)), w[l]}

В двух последних формулах мы реализовали w и g как массивы.

В прилагаемой программе реализованы функции создания массивов m, p и g. Реализованы функции поиска, использующие только эвристику стоп-символа, только эвристику безопасного суффикса и, наконец, функция поиска по обоим эвристикам.

---

Дата добавления: 2015-10-30