{'fraction_non_alphanumeric': 0.04209628102111925, 'fraction_numerical': 0.008319704188295527, 'mean_word_length': 4.372039724980901, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Tuning the Bad-Character Rule: the Worst-Character Rule

In this note we present the worst-character rule, an efficient variation of the bad-character heuristic for the exact string matching problem, firstly introduced in the well-known Boyer-Moore algorithm. Our proposed rule selects a position relative to the current shift which yields the largest average advancement, according to the characters distribution in the text. Experimental results show that the worst-character rule achieves very good results especially in the case of long patterns or small alphabets in random texts and in the case of texts in natural languages.


Introduction
Given a text T and a pattern P over some alphabet Σ, the string matching problem consists in finding all occurrences of the pattern P in the text T . It is a very extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, information retrieval, computational biology, etc.
In this paper we present the worst-character rule, an efficient variation of the bad-character heuristic for the exact string matching problem, firstly introduced in the well-known Boyer-Moore algorithm [BM77]. Our proposed rule selects a position relative to the current shift which yields the largest average advancement, according to the characters distribution in the text. Experimental results show that the worst-character rule achieves very good results especially in the case of long patterns or small alphabets in random texts and in the case of texts in natural languages.
Before entering into details, we review some useful notations and terminology. A string P of length m ≥ 0 over a finite alphabet Σ is represented as a finite array P [0 .. m− 1]. By P [i] we denote the (i + 1)-st character of P , for 0 ≤ i < m. Likewise, by P [i .. j] we denote the substring of P contained between the (i+1)-st and the (j + 1)-st characters of P , where 0 ≤ i ≤ j < m.
Let T be a text of length n and let P be a pattern of length m. If the character P [0] is aligned with the character T [s] of the text, so that P [i] is aligned with T [s + i], for 0 ≤ i ≤ m − 1, we say that the pattern P has shift s in T . In this case the substring T [s .. s + m − 1] is called the current window of the text. If T [s .. s + m − 1] = P , we say that the shift s is valid. Then the string matching problem consists in finding all valid shifts of P in T , for given pattern P and text T .
Most string matching algorithms have the general structure shown in Figure 1(A), where the procedure Precompute Globals(P ) computes useful mappings, in the form of tables, which may be accessed by the function named Shift Increment(s, P, T, j); the function Check Shift(s, P, T ) checks whether s is a valid shift and returns the position j of the last matched character in the pattern; the function Shift Increment(s, P, T, j) computes a positive shift increment according to the information tabulated by procedure named Precompute Globals(P ) and to the position j of the last matched character in the pattern. For instance, to look for valid shifts, the celebrated Boyer-Moore algorithm [BM77] scans the pattern from right to left and, at the end of the matching phase, it computes the shift increment as the largest value given by the good-suffix and the bad-character rules.

The bad-character rule
Information gathered during the execution of the Shift Increment(s, P, T, j) function, in combination with the knowledge of P , as suitably extracted by procedure Precompute Globals(P ), can yield shift increments larger than 1 and ultimately lead to more efficient algorithms. In this section we focus our attention on the use of the bad-character heuristic for preprocessing the pattern, introduced by Boyer and Moore in [BM77].
The Boyer-Moore algorithm is the progenitor of several algorithmic variants which aim at computing close to optimal shift increments very efficiently. Specifically, the Boyer-Moore algorithm checks whether s is a valid shift, by scanning the pattern P from right to left and, at the end of the matching phase, it computes the shift increment as the largest value suggested by the good-suffix rule and the bad-character rule, provided that both of them are applicable.
Specifically, the bad-character heuristic states that if c = T [s+j−1] = P [j−1] is the first mismatching character, while scanning P and T from right to left with shift s, then P can be safely shifted in such a way that its rightmost occurrence of c, if present, is aligned with position (s + j − 1) in T (provided that such an occurrence is in P [0 .. j − 2], otherwise the bad-character rule has no effect). In the case in which c does not occur in P , then P can be safely shifted just past position (s + j − 1) in T . More formally, the shift increment suggested by the bad-character heuristic is given by the expression Procedure Precompute bc, shown in Figure 1(B), computes the function bc P during the preprocessing phase in O(m + σ)-time and O(σ)-space, where σ is the size of the alphabet Σ.
Due to the simplicity and ease of implementation of the bad-character heuristic, some variants of the Boyer-Moore algorithm were based just on it and dropped the good-suffix heuristic.
For instance, Horspool [Hor80] suggested the following simplification of the original Boyer-Moore algorithm, which performs better in practical cases. He just dropped the good suffix heuristic and proposed to compute shift advancements in such a way that the rightmost character T [s+m−1] is aligned with its rightmost occurrence on P [0 .. m − 2], if present; otherwise the pattern is advanced just past the window. This corresponds to advance the shift by hbc The resulting algorithm performs well in practice and can be immediately translated into programming code (see Baeza-Yates and Régnier [BYR92] for a simple implementation in the C programming language).
Likewise, the Quick-Search algorithm, presented in [Sun90], uses a modification of the original heuristic, much along the same lines of the Horspool algorithm. Specifically, it is based on the following observation: when a mismatching character is encountered, the pattern is always shifted to the right by at least one character, but never by more than m characters. Thus, the character T [s + m] is always involved in testing for the next alignment. So, one can apply the bad character rule to T [s + m], rather than to the mismatching character, possibly obtaining larger shift advancements. This corresponds to advance the shift by Finally, the Smith algorithm [Smi91] computes its shift advancements by taking the largest value suggested by the Horspool and the Quick-Search badcharacter rules. Its preprocessing phase is performed in O(m+σ)-time and O(σ)space complexity, while its searching phase has a quadratic worst case time.
Although the role of the good-suffix heuristic in practical string matching algorithms has recently been reappraised [CF03b,CF03c,CF05], also in consideration of the fact that often it is as effective as the bad-character heuristic, especially in the case of non-periodic patterns, the bad character heuristic is still considered one of the powerfull method for speed up the performance of string matching algorithms (see for instance [FL08,FL09]).
For a given shift s, the Horspool and the Quick-Search algorithms compute their shift advancements by applying the bad-character rule on a fixed position s + q of the text, with q equal respectively to m − 1 and to m. We refer to the value q as the bad-character relative position.
It may be possible that other bad-character relative positions generate larger shift advancements. We will show below how, given a pattern P and a text T with known character distribution, we can compute efficiently the bad-character relative position, to be called worst-character relative position, which ensures the largest shift advancements on the average. The worst-character rule is then the bad-character rule based on such a worst-character relative position.

Finding the worst-character relative position
To begin with, we introduce the generalized bad-character function gbc P (i, c). Suppose the pattern P has shift s in the text T . For a given bad-character relative ) evaluates to i+1 (this corresponds to advance the pattern just past position s + i of the text). Thus, Plainly, gbc P (i, c) ≥ 1 always holds. Additionally, the shift rules of the Horspool and Quick-Search algorithms can be expressed in terms of the generalized bad-character function by hbc P (c) = gbc P (m − 1, c) and qbc P (c) = gbc P (m, c), respectively, for c ∈ Σ.
Next, let f : Σ → [0, 1] be the relative frequency of the characters in the text T . Given a fixed pattern P and a bad-character relative position 0 ≤ i ≤ m, the average shift advancement of the generalized bad-character function on i is given by the function Thus, the worst-character relative position of a given pattern P and a given relative frequency function f can be defined as the smallest position 0 ≤ q ≤ m such that adv P,f (q) = max 0≤j≤m adv P,f (j) .
The procedure Find worst character, shown in Figure 2(A), computes the worst-character relative position for a given input pattern P and a given relative frequency function f over Σ in O (m + σ)-time and O (σ)-space. It exploits the recurrence for the computation of adv P,f (i), for i = 0, . . . , m, which is based, in turn, on the fact that for c ∈ Σ and i = 0, 1, . . . , m.
Observe that in the above recurrence only entries of the generalized badcharacter function of the form gbc P (i, P . Observe that at the i-th iteration of the for-loop of procedure Find worst character, only the value lp i P (P [i]) is needed. The function lp i P is maintained as an array of dimension σ and computed by the following recursive relation The initialization of lp 0 P is plainly done in O (σ)-time, while the computation of lp i P , for i > 0, can be done in constant time from array lp i−1 P . Finally, the values gbc P (i, P [i]) are computed using the following relation

The worst-character heuristic
The position q computed by procedure Find worst character is then used by the worst-character heuristic to calculate shift advancements during the searching phase. In particular the worst-character heuristic computes shift advancements in such a way that the character T [s + q] is aligned with its rightmost occurrence on P [0 .. q − 1], if present; otherwise the pattern is advanced just past position s + q of the text. This corresponds to advance the shift by wc P (T [s + q]) positions, where Observe that if q = 0 then the advancement is always equal to 1. The resulting algorithm can be immediately translated into programming code (see Figure 2 for each c ∈ Σ do 2.
for each c ∈ Σ do 3.
adv P,

Experimental Results
To evaluate experimentally the impact of the worst-character heuristic, we have chosen to test the Worst Character Matcher algorithm (in short WC), given in Figure 2(C), with three algorithms based on variations of the badcharacter rule, namely the Horspool algorithm (in short, HOR), the Quick-Search algorithm (in short QS), and the Smith algorithm (in short SM). Experimental results have been evaluated in terms of running times and average advancement given by the shift heuristics. All algorithms have been implemented in the C programming language and were used to search for the same strings in large fixed text buffers on a PC with AMD Athlon processor of 1.19GHz. In particular, all algorithms have been tested on four Randσ problems and on four Exp λ σ problems, for alphabet sizes σ = 2, 4, 8, 16. For each problem, the patterns have been constructed by selecting 200 random substrings of length m from the files, for m = 2, 4, 8, 16, 32, 64, 128, 256, 512. Each Randσ and Exp λ σ problem consists in searching a set of 200 random patterns of a given length in a 20Mb random text over a common alphabet of size σ. Randσ and Exp λ σ problems differ in the distribution of characters in the text buffer.
In a Randσ the characters of the text buffer have a uniform distribution, i.e. the relative characters frequency is defined by the law f (c) = 1/σ, for all c ∈ Σ.
In an Exp λ σ problem the distribution of characters follows the inverse-rank power-law of degree λ, a model that gives a very good approximation of the relative frequency function of characters in terms of their ranks both in natural language dictionaries and texts (cf. [CF03a]). Formally, in a text in natural language the relative frequency of the character c i of rank i can be approximated by where the value of the degree λ ∈ R can be determined experimentally and usually ranges in the interval [3.
In the following tables running times are expressed in hundredths of seconds, while the average advancements are expressed in number of characters.

Conclusions
Several efficient variations of the bad-character heuristic have been proposed in the last years with the aim of obtaining better performances in practical cases. For instance, the Berry-Ravindran algorithm [BR99] generalizes the Quick-Search algorithm by using in its bad-character rule the last two characters, rather than just the last one. Another example is the Tuned-Boyer-Moore algorithm [HS91] which introduces, using the Horspool bad-character rule, an efficient implementation of the searching phase. Finally, algorithms in the Fast-Search family [CF05] combine the bad-character rule with the good-suffix heuristic by computing an O(σ × m)-space function.
In this paper we have presented the worst-character rule, a variation of the bad-character heuristic, which is based on the position relative to the current shift which yields the largest average advancement, according to the characters distribution in the text. We have also shown experimental evidence that the worst-character rule achieves very good results in practice, especially in the case of long patterns or small alphabets in random texts and in the case of texts in natural languages.