5
$\begingroup$

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand.

R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two dimensional mm pattern in a two dimensional nn text. The publication [1] is very well written and quite understandable for a novice like me, the algorithm is described in pseudocode and I was able to implements it successfully.

One part of the BYR algorithm requires the Aho-Corasick algorithm. This allows to search occurences of multiple keywords in a string text. However, they also say that this part of their algorithm can be greatly improved by using Aho-Corasick not, but Commentz-Walter algorithm (based on Boyer-Moore rather than Knuth-Morris-Pratt algorithm). They evoke an alternative to the Commentz-Walter algorithm, alternative that they themselves developed. This is described and explained in their previous publication [2] (see 4th chapter).

This is where my problem lies. As I said, the algorithm goes through the text and check if it contains a word from the set of keywords. The words are arranged upside down and placed in a tree. To be efficient, it will sometimes be necessary to skip a number of letters, when he knows that there is no match found.

Trie

To determine the number of characters that can be skipped, two tables d and dd have to be computed. Then, the algorithm is very simple:

The algorithm works as follows:

  • We align the root of the trie with position m in the text, and we start matching the text from right to left following the corresponding path in the trie.
  • If a match is found (final node), we output the index of the corresponding string.
  • After a match or mismatch, we move the trie further in the text using the maximum of the shift associated to the current node (means dd), and the value of d[x], where x is the character in the text corresponding to the root of the trie.
  • Start matching the trie again from right to left in the new position.

My problem is that I do not know how to compute the dd function. In their publication, R. Baeza-Yates and M. Regnier propose a formal definition of it:

$dd(p_i[j]) = \underset{k=1}{\overset{L}{min}}\{s | s \geq 1 \: and \: (s\geq j+m_k-m_i \: or \: p_k[j-s+m_k-m_i]\ne p_i[j]) \: and \: ((s \geq l+m_k-m_i \: or \: p_k[l-s+m_k-m_i]=p_i[l]) \: for \: j < l \leq m_i)\}$

$p_i$ is a word among the set of keyword, $j$ is the index of a letter in this word, so $p_i[j]$ is like a node in the previous trie I showed. Number in the node represented $dd(node)$. $L$ is the number of words, and $m_i$ is the number of letters in the word $p_i$.

They give no indication concerning the construction of this function. They only recommend to use the work of W. Rytter [3]. This document builds a function similar to that expected, the difference being that in this case, there is only one keyword and not a set.

The definiton of dd (called D here), is as follow:

$D[j] = MIN \{ s + n - j | s \geq 1 \: and \: (s \geq j \: or \: pattern[j-s] \ne pattern[j]) \: and \: ((s \geq i \: or \: pattern[i-s] = pattern[i]) \: for \: j < i \leq n)\}$

It may be noted similarities with the previous definition, but I do not understand everything.

The pseudocode for the construction of this function is given in the paper, I have implemented it, here in C++.

The pseudocode is as follow:

// Input: a pattern word of size n, Output: D table used to skip char in the text
for k = 1 step 1 until n do D[k] = 2*n - k
j = n
t = n + 1
while j > 0 do
    begin
    f[j] = t
    while t <= n and pattern[j] != pattern[t] do
        D[t] = MIN(D[t], n-j)
        t = f[t]
    t = t - 1
    j = j - 1
// Knuth's algorithm version: for k = 1 step 1 until t do D[k] = MIN(D[k], n+t-k)
// Rytter's corrected version (I do not think this is the most important part, 
// the algorithm would still work but would be less efficient):
q = t
t = n+1-q
q1 = 1
j1 = 1
t1 = 0
while j1 <= t do
    f1[j1] = t1
    while t1 > 1 and pattern[j1] != pattern[t1] do t1 = f1[t1]
    t1 = t1 + 1
    j1 = j1 + 1
while q < n do
    for k = q1 step 1 until q do D[k] = Min(D[k], n+q-k)
    q1 = q + 1
    q = q + t - f1[t]
    t = f1[t]

It works, but I do not know how to expand it for several words, I do not know how to coincide with the formal definition of dd given by Baeza-Yates and Régnier. I said that the two definitions was similar, but I do not know to what extent.

I did not find any other information about their algorithm, it is impossible for me to know how to implement the construction of dd, but I am looking for someone who could perhaps understand and show me how to get there, explaining me the link between the definitions of D and dd.


  1. Fast Two Dimensional Pattern Matching by R. Baeza-Yates and M. Régnier (1993)
  2. Fast Algorithms for Two Dimensional and Multiple Pattern Matching by R. Baeza-Yates and M. Régnier (1990)
  3. A Correct Preprocessing Algorithm for Boyer–Moore String-Searching by W. Rytter (1980)
$\endgroup$
  • $\begingroup$ No problem! You'll have to decide whether the pseudocode is crucial for your question; will is be understandable if the link breaks, for instance? On that note, you might want to make your reference more robust. $\endgroup$ – Raphael Jul 4 '14 at 8:54
  • $\begingroup$ @Raphael Thank you for the advice. I hope it is cleaner, although unfortunately there is no syntax highlighting for pseudocode. $\endgroup$ – Delgan Jul 6 '14 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.