Baeza-Yates-Gonnet algorithm

The Baeza-Yates-Gonnet-Algorithm or Shift-or-Algorithm , also known as Shift-and or Bitap , solves the string matching problem by simulating a nondeterministic automaton . Among other things, a modification of this algorithm is used in the Unix tool grep .

Since the implementation can be traced back to bit operations, the algorithm is already very efficient in terms of its execution. If you combine this with the underlying system (one loop over the pattern in preprocessing, one loop over the text during the search), the result is an extremely efficient algorithm.

basis

The algorithm is based on a set of vectors with the following definition: ${\displaystyle R_{j}}$

${\displaystyle R_{j+1}[i]={\begin{cases}1,&{\mbox{falls }}i=0\\1,&{\text{falls }}R_{j}[i-1]=1{\text{ und }}\mathrm {Musterzeichen} _{i}=\mathrm {Eingabezeichen} _{j+1}\\0&{\text{sonst}}\end{cases}}}$

This clearly means that exactly when, after processing characters in the text, the last characters match the first characters of the search pattern. ${\displaystyle R_{j}[i]}$ ${\displaystyle 1}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i}$

A hit for a search pattern with length is found, if . ${\displaystyle m}$ ${\displaystyle R_{j}[m]=1}$

Furthermore, the characteristic vectors are required for all characters that may appear in the text:

${\displaystyle s_{a}[i]={\begin{cases}1,&{\text{falls im Suchmuster an Stelle }}i{\text{ das Zeichen }}a{\text{ steht}}\\0&{\text{sonst}}\end{cases}}}$

Example:

Search pattern , length ${\displaystyle abcac}$ ${\displaystyle m=5}$

Characteristic vectors:

${\displaystyle {\begin{matrix}&s_{a}&s_{b}&s_{c}&s_{d}&...\\a&1&0&0&0&...\\b&0&1&0&0&...\\c&0&0&1&0&...\\a&1&0&0&0&...\\c&0&0&1&0&...\end{matrix}}}$

Sequence (exact matching)

In order to simplify the process, a special bit operation Bitshift or for the vector is introduced first: ${\displaystyle \gg }$ ${\displaystyle R}$ ${\displaystyle R={\begin{matrix}0\\0\\0\\0\\0\end{matrix}}\quad {\stackrel {\mathrm {Bitshift} }{\longrightarrow }}\quad {\begin{matrix}1\\0\\0\\0\\0\end{matrix}}\quad {\stackrel {\mathrm {Bitshift} }{\longrightarrow }}\quad {\begin{matrix}1\\1\\0\\0\\0\end{matrix}}\quad {\stackrel {\mathrm {Bitshift} }{\longrightarrow }}\quad {\begin{matrix}1\\1\\1\\0\\0\end{matrix}}}$

The algorithm for exact matches can now be reduced to a few simple steps:

1. Initialize the vector with 0 (for all positions) and begin with the first character of the text to be searched ${\displaystyle R}$
2. Move all bits in one position to the right using a bit shift . ${\displaystyle R}$
3. Carry out a combination of and the characteristic vector of the current text character. ${\displaystyle UND}$ ${\displaystyle R}$
4. Go to the next text character. If end, cancel, otherwise go to (2)

On closer inspection, steps (2) and (3) carry out exactly the calculation rule for : By shifting the "old" character is created in place of the place (corresponds in combination with the condition ). The characteristic vector of the current text character has at the point just then , if patterns and text match here. This links both conditions. ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle UND}$ ${\displaystyle R_{j}[i]=1}$ ${\displaystyle i+1}$ ${\displaystyle 1}$ ${\displaystyle UND}$

Example (exact matching)

Pattern: , ${\displaystyle abcac}$ ${\displaystyle m=5}$

Text: ${\displaystyle abcabcac}$

${\displaystyle {\begin{vmatrix}i\setminus &R_{0}&\gg &s_{a}&R_{1}\\1&0&1&1&1\\2&0&0&0&0\\3&0&0&0&0\\4&0&0&1&0\\5&0&0&0&0\end{vmatrix}}{\begin{vmatrix}\gg &s_{b}&R_{2}\\1&0&0\\1&1&1\\0&0&0\\0&0&0\\0&0&0\end{vmatrix}}{\begin{vmatrix}\gg &s_{c}&R_{3}\\1&0&0\\0&0&0\\1&1&1\\0&0&0\\0&1&0\end{vmatrix}}{\begin{vmatrix}\gg &s_{a}&R_{4}\\1&1&1\\0&0&0\\0&0&0\\1&1&1\\0&0&0\end{vmatrix}}{\begin{vmatrix}\gg &s_{b}&R_{5}\\1&0&0\\1&1&1\\0&0&0\\0&0&0\\1&0&0\end{vmatrix}}{\begin{vmatrix}\gg &s_{c}&R_{6}\\1&0&0\\0&0&0\\1&1&1\\0&0&0\\0&1&0\end{vmatrix}}{\begin{vmatrix}\gg &s_{a}&R_{7}\\1&1&1\\0&0&0\\0&0&0\\1&1&1\\0&0&0\end{vmatrix}}{\begin{vmatrix}\gg &s_{c}&R_{8}\\1&0&0\\1&0&0\\0&1&0\\0&0&0\\1&1&1\end{vmatrix}}}$

There is a hit at (position - pattern length + correction for first character). ${\displaystyle R_{8}[5]=1}$ ${\displaystyle 8-5+1}$

Extension (approximate matching)

The algorithm can carry out a fault-tolerant search with slight modifications. For this, the vector is divided: ${\displaystyle R}$

1. ${\displaystyle R_{j}^{0}[i]}$: corresponds to the previous one ; The index stands for the number of errors that have occurred. ${\displaystyle R_{j}[i]}$ ${\displaystyle 0}$
2. ${\displaystyle R_{j}^{1}[i]}$: Designates a vector that is aimed at hits with at most one error. ${\displaystyle R}$
3. ...
4. ${\displaystyle R_{j}^{k}[i]}$: Designates a vector that is aimed at hits with a maximum of errors. ${\displaystyle R}$ ${\displaystyle k}$

Caution: In the case of the error-prone vectors, the above interpretation with “after j characters the last i match the first i of the pattern” is difficult and no longer necessarily plausible.

The calculation rule for remains unchanged. For error vectors , a distinction is made according to the causing action: ${\displaystyle R_{j}^{0}[i]}$ ${\displaystyle R_{j+1}^{k}}$

Insert a character in the search pattern

${\displaystyle R_{j+1}^{k}=({\mathit {Bitshift}}(R_{j}^{k})\ \wedge \ s_{x})\quad \vee \ R_{j}^{k-1}}$

Explanation: The first part of the expression describes when there are already errors, but the current character of the text and pattern match. The second part describes the error case: So far (in ) there were only errors, so the current character can be inserted into the pattern. ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle k-1}$

Interpretation: if after the input of the last characters at least characters match the search pattern and the rest can be matched by inserting the missing characters. ${\displaystyle R_{j}^{k}[i]=1}$ ${\displaystyle j}$ ${\displaystyle i+k}$ ${\displaystyle i}$

Deleting a character from the search pattern

${\displaystyle R_{j+1}^{k}=({\mathit {Bitshift}}(R_{j}^{k})\ \wedge \ s_{x})\quad \vee \ {\mathit {Bitshift}}(R_{j+1}^{k-1})}$

Explanation: The first part of the expression describes when there are already errors, but the current character of the text and pattern match. The second part describes the error case: If you do not look at the first characters of the text , but only the first (in the vector the position above), the pattern matches except for errors. The mark of the pattern is then simply deleted. ${\displaystyle k}$ ${\displaystyle j+1}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle k-1}$ ${\displaystyle i.}$

Replace a character in the pattern

${\displaystyle R_{j+1}^{k}=({\mathit {Bitshift}}(R_{j}^{k})\ \wedge \ s_{x})\quad \vee \ {\mathit {Bitshift}}(R_{j}^{k-1})}$

Explanation: The first part of the expression describes when there are already errors, but the current character of the text and pattern match. The second part describes the error case: According to characters, the last characters matched . If you now replace the character in the pattern with the character in the text, the last characters also match the first characters of the "new" pattern after characters . ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle i-1}$ ${\displaystyle i.}$ ${\displaystyle j+1.}$ ${\displaystyle j+1}$ ${\displaystyle i}$ ${\displaystyle i}$

The variants can be linked by bit or as required.

literature

• Ricardo A. Baeza-Yates, Gaston H. Gonnet: A New Approach to Text Searching . In: Communications of the ACM . tape 35 , no. October 10 , 1992, ISSN  0001-0782 , pp. 74-82 , doi : 10.1145 / 135239.135243 ( researchgate.net [PDF; 1000 kB ]).

Web links

• StringSearch - high-performance pattern matching algorithms in Java (implementations of the Shift-Or algorithm in Java; English)
• BNDM algorithm (PDF; 289 kB)