Понимание алгоритма для сопоставления шаблонов с использованием массива LCP

Question

Предисловие: Мой вопрос в основном является алгоритмическим вопросом, поэтому, даже если вы не знакомы с суффиксами и массивами LCP, вы, вероятно, можете мне помочь.

В статье this описано, как эффективно использовать суффикс и массивы LCP для сопоставления строк.

я понял SA и LCP работу и как время выполнение алгоритма может быть улучшено с O(P*log(N)) (где P является длиной паттерна и N является длиной строки) для O(P+log(N)) (Спасибо Криса Eelmaa отвечает here и jogojapans ответить here).

Я пытался использовать алгоритм на рисунке 4, который объясняет использование LLcp и RLcp. Но у меня проблемы с пониманием того, как это работает.

Алгоритм (из the source):

Объяснение используемых имен переменных:

lcp(v,w) : Length of the longest common prefix of v and w 
W = w0..wP-1 : pattern of length P 
A = a0..aN-1 : the text (length N) 
Pos[0..N-1] : suffix array 
L_W : index (in A) of first occurrence of the matched pattern 
M : middle index of current substring 
L : lower bound 
R : upper bound 
Lcp : array of size N-2 such that Lcp[M] = lcp(A_Pos[L_M], A_pos[M]) where L_M is the lower bound of the unique interval with M in the middle 
Rcp : array of size N-2 such that Rcp[M] = lcp(A_Pos[R_M], A_pos[M]) where R_M is the upper bound of the unique interval with M in the middle 

Теперь я хочу попробовать алгоритм, используя следующий пример (частично взяты из here):

SA | LCP | Suffix entry 
----------------------- 
5 | N/A | a 
3 | 1 | ana 
1 | 3 | anana 
0 | 0 | banana 
4 | 0 | na 
2 | 2 | nana 

A = "banana" ; N = 6 
W = "ban" ; P = 3 

Я хочу попытаться сопоставить строку, скажем ban, и ожидал, что алгоритм вернется 0 как L_W.

Вот как я бы пошагово алгоритм:

l = lcp("a", "ban") = 0 
r = lcp("nana", "ban") = 0 
if 0 = 3 or 'b' =< 'a' then // which is NOT the case for both conditions 
    L_W = 0 
else if 0 < 3 or 'b' =< 'n' then // which is the case for both conditions 
    L_W = 6 // which means 'not found' 
... 
... 

Я чувствую, что я что-то отсутствует, но я не могу выяснить, что. Также мне интересно, как можно использовать предварительно вычисляемый массив LCP вместо вызова lcp(v,w).

Answer 1

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

Очевидно, что у меня нет никакого доказательства для этого, я не Manber или Майерс, это более мотивированного предположение:

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

Второе условие на третьей строке достигает этого превосходно. Если мы проигнорируем равенство на данный момент, заявив, что l и P не равны, но второе условие истинно, т. Е. W [l] < SA [0] [l], обратите внимание, что это l s, а не s - это означало бы, что W лексикографически перед первой записью массива суффиксов и, следовательно, не в тексте вообще.

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

(Тем не менее, я не уверен, почему быть равного к самому первому суффикса в массиве - что и л и P равными будет означать, как самый длинный общий префикс в оба strings is P long, ergo, до тех пор, пока запрос, ergo, весь запрос - скомпонован вместе с до первым суффиксом. На фундаментальном уровне, если запрос является первым суффиксом в массиве, он находится в массиве, таким образом, в тексте.)

С другой стороны, строка 5 - буквально всегда верно. Когда запрос не является окончательным суффиксом из-за несоответствия, r < P. Когда запрос не является окончательным суффиксом, потому что окончательный суффикс достигает конца его строки, w [r] == SA [n-1] [r] (который, к сведению, будет конечным не-часовым символом в текст). Когда запрос является окончательным суффиксом, r = P и, следовательно, w [r] == SA [n-1] [r].

Итак ... Да. Это всего лишь разумная догадка, но я бы сказал, что на пятой строке на бумаге были две критические типографские ошибки. Противоположность этой теории, конечно же, подчеркивает, насколько невероятно невероятно, что ошибка не только прошла мимо авторов, но и редакторов журнала ... Особенно учитывая, что она была первоначально получена в 1989 году, наконец, принята в 1992 году , и ошибки буквально являются самой важной частью всей бумаги.