Automata have always played a very important role in the design of e cient solutions for the exact string matching problem. Among these, a special mention is deserved by those algorithms exploiting the bit-parallelism technique to e ciently simulate the su x automaton of a string. However, the bit-parallel encoding requires one bit for each character, and thus performance degrade quickly as the length of searched pattern grows beyond the machine word size w. In this paper, we present a novel technique for exploiting the bit-parallel representation of a nondeterministic su x automaton also in the case of strings of length m > w. Our approach consists in searching for a pruned version of the original pattern, whose automaton can be represented with a reduced number of bits, thus allowing to retain the performance of the original approach also in the case patterns exceeding the word size. Experimental results show that, in the case of very long patterns, our method scales better than existing approaches.
The string matching problem consists in nding all the occurrences of a pattern
P of length m in a text T of length n, both de ned over an alphabet of
size . It is a basic problem of computer science that has been studied for
more than 40 years [
Automata play a very important role in the design of e cient string matching algorithms. For instance both the KMP and the BDM algorithms are based on nite automata; in particular, they simulate, respectively, a deterministic automaton for the language ?P and a deterministic su x automaton for the language of the su xes of P . The e ciency of such solutions is strictly in uenced by the encoding used for simulating the underlying automata. ? This work has been supported by G.N.C.S., Istituto Nazionale di Alta Matematica
Francesco Severi and by Programma Ricerca di Ateneo UNICT 2020-22 linea 2 ?? Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
A successful technique which has been extensively used for the e cient
simulation of non-deterministic automata is the bit parallelism [
Speci cally, the bit parallel encoding takes advantage of the intrinsic
parallelism of the bitwise operations inside a computer word, allowing to cut down
the number of operations that an algorithm performs by a factor up to !, where
! is the number of bits in the computer word. However, one bit per pattern
symbol is required for representing the states of the full automaton, for a total
of dm=!e words. Thus, as long as a pattern ts in a computer word, bit-parallel
algorithms are extremely fast, otherwise their performances degrade
considerably as dm=!e grows. Although such limitation is intrinsic, several techniques
have been developed which retain good performance also in the case of long
patterns [
In this paper, we introduce a novel approach for the the bit-parallel simulation of the su x automaton in the case of long patterns. The idea is to rst search for a pruned pattern, and to subsequently verify each occurrence of the original pattern. The pruned pattern is constructed by preserving only the occurrences of a single pivot character c; remaining characters are implicitly associated to the special wildcard symbol " " and are allowed to match any character of the alphabet, except from c. It turns out that the su x automaton of a pruned pattern can be encoded using k bits, where k is the number of occurrences of c in P . Though in the worst case k = m, on the average it is much smaller than m, and, when the size of the alphabet is large enough, it is also smaller than ! even for very long patterns.
From our experimental results it turns out that, under suitable conditions, our approach is able to represent patterns which far exceed the word size w.
The paper is organized as follows. Section 2 presents the basic notions which we use along the paper. In Section 3 we review the previous solutions known in literature which make use of the bit-parallelism approach to e ciently encode the non-deterministic su x automaton of a string. In Section 4, we present and describe in details the new algorithm. In Section 5 we perform an experimental evaluation comparing the new algorithm with existing solutions. Finally, we draw our conclusions in Section 6. 2
Given a nite alphabet , we denote by m, with m 0, the set of strings of length m over and put = Sm2N m. We regard a string P 2 m as an array P [0::m 1] of characters and denote its length by jP j = m (in particular, denoting by the empy string, we have j j = 0). Thus, P [i] is the i-th character of P , for 0 i < m, and P [i::j] is the substring of P starting at the i-th position and ending at the j-th position, for 0 i j < m. Moreover, for each character c 2 , we denote by P (c) the number of its occurrences in P (we refer to such value as simply (c) when the pattern P is clear from the context). For any two strings P and P 0, we say that P 0 is a su x of P if P 0 = P [i::m 1] for some 0 i < m and write Su (P ) for the set of all su xes of P . Similarly, P 0 is a pre x of P if P 0 = P [0::i], for some 0 i < m. In addition, we write P P 0 , or more simply P P 0, for the concatenation of P and P 0, and P r for the reverse of the string P , i.e. P r = P [m 1]P [m 2]:::P [0].
For a string P 2 m, the su x automaton of P is an automaton which recognizes the language Su (P ) of the su xes of P . Finally, we recall the notation of some bitwise in x operators on computer words, namely the bitwise and \&", the bitwise or \j", the left shift \ " operator (which shifts to the left its rst argument by a number of bits equal to its second argument), and the unary bitwise not operator \ ". 3
In this section we review existing solutions for the exact online string matching problem which make use of a su x automaton for searching for all occurrences of a pattern in a text, focusing on those algorithms which implement speci c solutions to encode the automata for long patterns. Most of them are ltering based solutions, which means that they use the su x automaton, constructed over an approximate version of the input string, for nding candidate occurrences of the pattern that must subsequently veri ed for an exact occurrence by running an additional veri cation phase.
All algorithms reviewed in this section are variants of the well known
BackwardDAWG-Matching algorithm (BDM) algorithm [
However, one of the side e ects of the BDM algorithm lies in the use of
the deterministic variant of the su x automaton since the workload required
to manage the individual transitions may be not negligible and, although its
construction is linear in the size of the string, the proportionality factor hidden in
the asymptotic notation is particularly high, making its construction prohibitive
in the case of long patterns [
The BNDM algorithm [
When the pattern size m is larger than !, the con guration bit-vector and all auxiliary bit-vectors need to be split over dm=!e multiple words. For this reason the performance of the BNDM algorithm degrades considerably as dm=!e grows. A common approach to overcome this problem consists in constructing an automaton for a substring of the pattern tting in a single computer word, to lter possible candidate occurrences of the pattern. When an occurrence of the selected substring is found, a subsequent naive veri cation phase allows to establish whether this belongs to an occurrence of the whole pattern.
However, besides the costs of the additional veri cation phase, a drawback of this approach is that, in the case of the BNDM algorithm, the maximum possible shift length cannot exceed !, which could be much smaller than m.
Peltola and Tarhio presented in [
The idea is to search rst the superimposed pattern in the text, so that only every k-th character of the text is examined. This ltration phase is done with the standard BNDM algorithm, where only the k-th characters of the text are inspected. When an occurrence of the superimposed pattern is found the occurrence of the original pattern must be veri ed. The time for its veri cation phase grows proportionally to m=!, so there is a threshold after which the performance of the algorithm degrades signi cantly.
Durian et al. presented in [
The main modi cation in the automaton simulation consists in moving the rightmost bit, when set, to the rst position of the bit array, thus simulating a circular automaton. Like in the case of the LBNDM, algorithm the BXS algorithm works as a lter algorithm, thus an additional veri cation phase is needed when a candidate occurrence has been located.
Cantone et al. presented in [
As we noticed in the previous section, the e ciency of an algorithm simulating the non-deterministic su x automaton by bit-parallelism is heavily in uenced by the length of the pattern and by the size of the resulting automaton: on the one hand, as we pointed out, the performance of such solutions degrade as m grows; on the other hand, automata constructed over longer patterns lead to larger shifts during the searching phase when a backward scan of the window is performed. Thus the need for e cient bit-parallel encoding able to keep as low as possible the number of words involved in the encoding and able to preserve, at the same time, the length of the pattern.
In this section, we present a new algorithm for the online exact string matching problem based on a su x automaton constructed over an approximate version of the pattern P , which we simply call pruned pattern, where some speci cally selected characters are replaced with don't care symbols. We will then show how to e ciently simulate the su x automaton constructed over the pruned version of the pattern using bit-parallelism. 4.1
Let P be a pattern of size m and let T be a text of size n, both strings over a common alphabet of size . In addition let c 2 be a character of the alphabet occurring in P which we refer as the pivot character. A pruned version of P over the pivot character c is a string Pc obtained by preserving in P all the occurrences of c, while the remaining positions are allowed to match any character belonging to n fcg. In other words the pruned pattern Pc is obtained from P by replacing any character in n fcg by a don't care symbol.
More formally, for each c 2 , the pruned string Pc is a string of length m de ned over the alphabet c = fc; ?g where, for i = 0; 1; ::; m 1, Pc[i] is set to: Pc[i] = c if P [i] = c ? otherwise P z
**** ...
For instance, if we assume that P = abbacbbcac is a pattern of length m = 10 over the alphabet = fa; b; cg and that a is the pivot character, then we have that Pa = a ? ?a ? ? ? ?a?, where ? is the don't care symbol. Similarly we have Pb = ?bb ? ?bb ? ??.
The string matching problem allowing for don't care symbols is a well known
approximate variant of the exact matching problem [
Speci cally, let (c) be the absolute frequency of the pivot character c in P . Then the pruned string Pc of a string P can be encoded as a sequence, hd0; d1; :::; d (c)i, of length (c) + 1 over the alphabet P = f0; 1; 2; : : : ; m 1g, where each element of Pc represents the number of consecutive ? symbols between two successive occurrences of the pivot character c, or located at the two extremities of the string.
More formally, let hp0; p1; : : : ; p (c) 1i be the sequence of all positions in P where the pivot character occurs, with 0 p1, p (c) 1 < m and pi 1 < pi, for 0 < i < (c). Then we have, for 0 i (c): di =
We refer to such a representation of the pruned string Pc as its implicit encoding and we denote it as P^c (see Figure 1). It trivially turns out that di m for 0 i k. More precisely we have m = (c) + (c) X di i=0 For instance, given the string P = banana, then Pa = *a*a*a, Pb = b*****, Pn = **n*n*, while P^a = h1; 1; 1; 0i, P^b = h0; 5i and P^n = h2; 1; 1i.
In the next sections we describe the preprocessing and the searching phases of our new algorithm, which we call Pruned BNDM (PBNDM) algorithm, and which solves the exact string matching problem by making use of the su x automaton of the pruned pattern. 4.2
During the preprocessing phase of the PBNDM algorithm, a character c occurring in P is elected to be the pivot character. Since such choice is arbitrary, the pivot character is selected as the character with maximum absolute frequency not exceeding the word size w, if any. If such choice is not possible we truncate the pattern at its longest pre x that contains at least one character with an absolute frequency not exceeding the word size w. It is easy to observe that the selection of the pivot character can be performed in O(m) time, by computing the frequencies of all the characters appearing in P . Without loss in generality we can assume that such pivot character can be selected on the pattern P .
Let P^c = hd0; d1; :::; d (c)i the implicit encoding of Pc. It is a string of length (c) + 1 over the alphabet ^ = f1; 2; 3; : : : ; mg of size m + 1.
The bit-parallel representation of the su x automaton of P^cr is computed by means of an array B of m + 1 bit-vectors, each of size (c) + 1, where the i-th bit of B[d] is set i P^[i] = d, for 0 d m and 0 i (c). However, since the last transition of the automaton is allowed for any value greater than or equal to d0, the rst bit of each bit-vector in B is set for any value d d0.
More formally, for 0 i (c) and 0 d m, B[d][i] is de ned as follows: B[d][i] = 1 if (i = 0 and d 0 otherwise d0) or (i > 0 and d = di); A separate discussion should be made for the rst transition made on the automaton. Since it is admitted that the rst transition can start from any position of the pattern it is necessary to allow that at the rst transition each i-th state can be activated by values lower than or equal to di. For this purpose an auxiliary set of m + 1 bit-vectors is de ned, called S, which is used for the simulation of the rst transition on the automaton.
More formally, for 0 i (c) and 0 d m, S[d][i] is de ned as follows: S[d][i] = 1 if (i = 0 and d 0 otherwise d0) or (i > 0 and d di); Read(S; i; l; c) 1. j i 2. while j l and S[j] 6= c do 4. j j 1 6. return (i j; j) Preprocess(P; m; c; k)
Initialize bit-vectors B and S 1. for i 0 to m do 2. B[i] 0 3. S[i] 0
Compute B, d0 and dmax
1
The pseudo-code of the preprocessing phase of the algorithm is shown in Figure 2. It makes use of an auxiliary procedure Read which performs a scan of the string S starting at position j = i and proceeds from right to left until a given position l j is reached or an occurrence of the pivot character c is found. It returns the couple of integers (i j; j).
The implicit encoding of Pc is computed gradually, during the initialization of table B through procedure Read, which computes the next element of the implicit encoding of Pc. Table S is then computed from table B in a single-pass for loop. The time complexity of the preprocessing phase is O(m). Since di m, then the space overhead to store B and S is O(m) too. Apart from the tables encoding the transitions of the su x automaton, B and S, the preprocessing phase returns two additional integers, d0 and dmax = maxfdi : 0 i kg, which are used during the searching phase. 4.3
The searching phase of the PBNDM algorithm acts using a ltering method. Speci cally, it rst searches for all the occurrences of the pruned pattern Pc in the text. When an occurrence of Pc is found, starting at position j of the text, the algorithm naively checks for the whole occurrence of the pattern, i.e. it checks if P = T [j::j + m 1].
As in the original BNDM algorithm, a window W of length m is shifted over the text, starting from the left end of the text and sliding from left to right. At each iteration of the algorithm a position of the window W is attempted performing a scanning of its characters proceeding from right to left and performing the transitions over the automaton accordingly.
During the backward scanning, W^ c = hw0; w1; :::; wli is computed on the y by procedure Read, and the automaton con gurations si, represented as a bit-vector D of (c) + 1 bits, are updated accordingly.
If wl > dmax, then the pre x of Pc of size d0 has been recognized, so the window is shifted without performing any transition. Otherwise, the rst transition is performed by setting D D & S[wl], so that all states si such that di wl are kept active. Transition on any subsequent wi, for 0 < i l, is implemented as D D & B[wi]. Moreover, by the de nition of B and S, s0 is kept active during the i-th transition if wi d0. When, after performing the i-th transition, state s0 is active, then a pre x of Pc of size d0 + Pk j=i+1 wj has been recognized.
Apart from the case where Pc is recognized, each attempt ends when either D becomes zero or it is established that wi > dmax while proceeding in the backward scan.
As the original BNDM algorithm, the PBNDM algorithm has a O(nm) worst case time complexity and a O( + m) space complexity. 5
In this section, we compare our new algorithm against other su x automaton
based solutions, focusing on those which make use of bit-parallelism for solving
the problem with long strings. In particular we included the following algorithms:
{ BNDM: the Backward-Nondeterministic-DAWG-Matching algorithm [
All algorithms have been implemented in the C programming language and
have been tested using the Smart tool [
Algorithms have been compared in terms of running times and average shift advancements. Table 1 and Table 2 report the average shift achieved by each algorithm during the searching phase and the the search speed (expressed in Gigabytes per second) observed in our experimental evaluations, respectively. In both tables best results have been boldfaced to ease their localization. Table 1 also reports the gain (expressed as a percentage) with respect to the best result obtained by the previous algorithms. If the shift advancement is lower, the gain is expressed with a negative value.
Regarding the average shift advancement our experimental results clearly show that PBNDM achieves the best performance in the most of practical cases and always proposes the largest advancements in the case of long patterns. This suggests that our automaton encoding scales better as the size of the pattern increases and is thus more suitable to handle long strings.
The only exception is the case of very small alphabets where PBNDM is second to LBNDM which is the clear winner in terms of shift advancements. In this case PBNDM proposes shorter shifts than 10 times those proposed by LBNDM. However, it is important to note that LBNDM search simultaneously m=w substrings of the pattern, each of length w (see Section 3), and that the 128 1.79 1.82 1.91 1.67 2.29 1.83 overall progress due to the shift is always counterbalanced by the number of checks that must be performed, which corresponds to the number of superimposed substrings. This results in poor performance in the case of very long patterns, especially when the size of the alphabet is small. In other words, the advantage obtained in the advancements is not exploited in the general performance of the algorithm. Less performances are also shown by the BNDM and SBNDM algorithms, due to the fact that the length of the pattern is always limited to the size of the word w.
Also the BXS algorithm uses an encoding based on a superimposed pattern and this causes it to have a degenerative behavior in the case of very long patterns, failing to scale well with respect to the length of the pattern. Speci cally it does not work well when the superimposed pattern is not sensitive enough, i.e. too many di erent characters are accepted at the same position. This happens when the alphabet is too small or the pattern is too long.
We can observe, indeed, that although the size of the pattern increases the length of the superimposed pattern remains xed at w. As a result the BXS algorithm, although particularly fast for patterns of moderate length (up to 128 or 256), is particularly slow for very long patterns, going beyond the execution time limit set for our tests, especially in the case of small alphabets. Its behavior, on the other hand, improves considerably as the size of the alphabet increases, becoming the best alternative to PBNDM for natural language texts.
The FBNDM algorithm is in general the one that performs best among the previous solutions, managing to scale the length of the shift quite well as the length of the pattern increases. Any factor of the pattern with no repeated characters (see Section 3) is always limited by the size of the alphabet and, as the pattern length increases, this imposes a relatively limited number of factors which can be represented by a single computer word. As a consequence this limits the shift advancement to the overall length of the factors of the pattern taken into account. But despite this limitation FBNDM is in most cases the best alternative to PBNDM, especially in the case of small alphabets, and this translates into the best running times in most of the cases where PBNDM is not the best alternative.
On the whole we notice how the loss relative to the advancement of the shift never goes beyond 11% (with the exception of LBNDM as discussed above) while the gain obtained in increasing the shift, in the case of longer patterns, is impressive and reaches up to 954%. This aspect is clearly re ected in the execution times in which PBNDM is always among the rst two best alternatives, becoming the fastest among all the algorithms for very long patterns. Although the presets remain moderate for small alphabets, the speed up achieved as the alphabet size increases is such that PBNDM is up to 3 times faster than the best alternative for natural language texts. 6
In this paper, we introduced a new algorithm, called PBNDM, based on a novel encoding of the su x automaton of a string, suitable for patterns exceeding the word size w. Our algorithm is based on a pruned version of the pattern whose automaton can be encoded in an implicit form using few bits. From our experimental results our solution turns out to be competitive when compared for searching long strings against existing bit-parallel algorithms.
We observe that, although in this paper we focused on the application of the new encoding in the case of the exact pattern matching problem, it turns out to be exible enough to be applied in all those solutions that make use of such data structure, even in the case of non-standard and approximate pattern matching.
In our future works we intend to tune the algorithm in order to make it competitive with the most e cient algorithms in practical cases, also in the case of small alphabets, a condition in which our algorithm still su ers due to the reduced length of the shifts. This includes the use of fast loops for further improving running times, and the use of condensed alphabets for representing longer and longer patterns inside a single word.