Проблема состоит в том, что все совпадения начинаются с M в строке S с массивом шаблонов строк W [], где совпадение - это конкат всех строк в W в любом порядке. Все строки шаблона в W имеют одинаковую длину, и все должны встречаться ровно один раз за совпадение.
Если W = ["ab", "ba"] и S = "abba", то M = [0]. // OK
Если W = ["ab", "ba"] и S = "baab", то M = [0]. // OK
Если W = ["ab", "ba"] и S = "baba", то M = []. // OK
Если W = ["ab", "ba"] и S = "baabbaab", то M = [0, 2, 4]. // ОК
Applying Rabin-Karp thinking:
- WC = pattern word count // len(W)
- WL = pattern word length // len(W[0]), since all have the same length
- unordered pattern strings can use a rolling hash,
if the rolling hash is also order-independent
- so, we keep the rolling hash as the sum of rolling word-length subhashes
- e.g we act like it is a pattern of L=WC*WL length,
although we roll hashes for each WL fragment independently.
У меня есть рабочий C# источник, но псевдокод облегчает express мой конкретный c вопрос о сокращении ложных срабатываний:
loop: i=[1..len(S)-L+1]
// this part would normally be the one-line h update for a single-string pattern
j=i-1
loop: w=[0..WC-1]
roll hsub[w] by rolling-out S[j] and rolling-in S[j+WL]
j+=WL
h = sum(hsub[0..WC-1])
////
if h == p_h
// let's pretend we aren't checking false positives, for the purpose of this post
// if check_words(S[i..i+L], words)
add i to matches
ВОПРОС:
Характер типичных вычислений ха-1038 *, используемых для шаблонов перестановки слов, подобных этому, заключается в том, что хотя независимые субшиши могут не совпадать, сумма субхешей может слишком легко совпадать:
Если W = ["ab", "ba"] и S = "aabb", то M = [0]. // НЕПРАВИЛЬНО! (предположим, мы хотим сообщить о ложных срабатываниях)
The reason is obvious; the only factor that matters for the same hash h total of subhashes,
is that the occurence count of each char in every word position is the same.
So for the above example:
- the pattern W[ ]:
"ab",
"ba"
in position [0] across all words in W: 1 a and 1 b (look at it vertically)
in position [1] across all words in W: 1 a and 1 b
- the string window S[i,i+L-1] (shown broken by WL):
"aa"
"bb"
i=0 (for first window)
in [i] across all WL increments(S[i] and S[i+WL]): 1 a and 1 b
in [i+1] across all WL increments(S[i+1] and S[i+1+WL]): 1 a and 1 b
Таким образом, всякий раз, когда происходит такое выравнивание сумм позиций, вы получаете общее совпадение га sh.
Есть ли способ продолжить использовать технику суммирования скользящих слов, но уменьшить или удалить только что описанные ложноположительные случаи? Я пытался, но продолжаю возвращаться к этому: это базовая c особенность (и здесь недостаток) в простой аддитивной полиномиальной математике, используемой, в первую очередь, для включения хэшей. Что я могу сделать, чтобы улучшить ложные положительные знаки выравнивания символов, все еще используя простой скользящий калибр c?
Каждый раз, когда я думаю, что у меня есть способ отличить guish эти случаи лучше, это также портит независимость порядка разрешенных совпадений строк слов.
[Другие техники, такие как Aho-Corsick, здесь не используются, если они не могут быть использованы в скользящем га sh cal Сценарий c (например, Aho-Corsick - автомат с множественными совпадениями tr ie, но он не помогает ответить на мой конкретный c вопрос о вычислении ha sh, чтобы избежать ложноположительных выравниваний).]