File StringSearch.h

↰ Parent directory (ADS/string)

The exact search of a pattern P of m bytes in a text T of n bytes, beyond the book: the engineered search of Namespace ADS, the one that the benchmark of the searches compares with memmem() of the C library, std::search() with its three searchers and the searchers of Boost.Algorithm, while kmp() [see File StringMatching.h] stays the algorithm of the textbook.

Definition (ADS/string/StringSearch.h)

Detailed Description

The occurrences are the places :math:`[
mathrm{Occ}( P , T ) = { s in [ 0 , n - m ]T[ s .. s + m - 1 ]

= P } .

`

StringSearcher prepares P once, as the searchers of the standard library do, and then finds its occurrences in any text:

  • P of one byte is found by memchr();

  • P of fewer than kSkip bytes goes through the filter of k probes (the packed filters of Faro and Kulekci and of Mula): the places :math:` o_1 , ldots , o_k ` of the rarest bytes :math:` b_i = P[ o_i ] ` of P, k = 2, or 4 if P hints at a small alphabet (fewer than 8 distinct bytes in 8 or more, or a repeated byte in fewer, as on DNA), and the start s is compared with P by memcmp() only if :math:` T[ s + o_i ] = b_i ` for every i. The test is made for W consecutive starts at once by k vector comparisons of W bytes and their AND, AVX-512 (W = 64), AVX2 (32) or SSE2 (16) as the target allows, four blocks a step with the comparisons with P out of the way of the probes (elsewhere memchr() finds the first probe and the others are checked one by one), so that on a text of independent bytes of probabilities :math:` p_c ` the expected number of comparisons with P is :math:` ( n - m + 1 ) prod_i p_{b_i} , e.g., :math: n / 256 ` on DNA with four probes. The rarest bytes are those of a fixed ranking of the bytes by their frequency in text (the letters of English by frequency, the blank and the newline the most common, the control and the high bytes the rarest), the later place on a tie;

  • P of kSkip bytes or more is searched by the shifts of its q-grams, in the spirit of Horspool and of Wu and Manber, as the hashed q-grams of Lecroq: q is the least length with :math:` d^q ge 16 m ` for the d distinct bytes of P, :math:` 2 le q le 8 , a q-gram g is hashed to :math: h( g ) in [ 0 , 4096 ) ` (the 12 top bits of its product by :math:` lfloor 2^{64} / phi rfloor `), and :math:`[
    mathit{shift}[ x ] = minbigl{ 255 , m - q + 1 , min{ m - q - i :

    0 le i < m - q , ; h( P[ i .. i + q - 1 ] ) = x } bigr} ,

    ` 0 for the hash of the last q-gram of P; the window at s moves to :math:` s + mathit{shift}[ h( T[ s + m - q .. s + m - 1 ] ) ] , and a window of shift 0 is compared with P and moves by the shift that the last q-gram of P has among the others. A shift never passes an occurrence, since it is at most the distance to the last place where the q-gram at the end of the window occurs in P. On random texts a window moves by about m - q + 1, :math: O( n / m ) ` windows of one load of 8 bytes; the text 1024 bytes ahead is prefetched, and the four quarters of a text of 16 KB or more are searched at once, their windows in registers, so that the chains of loads of the four overlap (the occurrences of a quarter wait for the end of the ones before it). When 64 steps have moved the first window by less than 16 m (a text of few distinct q-grams), the filter of the probes takes over;

  • every search counts its comparisons with P, m bytes each, those that find an occurrence too: once their bytes exceed :math:` 16 ( s - s_0 ) + 4096 ` at the window s of a search begun at :math:` s_0 , the search goes on with the Two-Way algorithm of Crochemore and Perrin, so that no text costs more than :math: 16 n + 4096 + m ` bytes compared before it, and :math:` 2 n ` comparisons after it, O( n + m ) in all (e.g., a pattern that agrees with a periodic text on its probes and nowhere else, or one that occurs at every place, :math:` a^m ` in :math:` a^n , which cost :math: Theta( n m ) ` to the comparisons with P alone). The Two-Way algorithm cuts P at a critical factorization P = u v, whose local period at |u| is the period p of P, found by the two maximal suffixes of P for an order of the bytes and its reverse (the longer one gives |u|); it compares v from left to right and then u from right to left, and moves by p, with a memory of the prefix of P that is known to match, if u is a suffix of :math:` P[ 0 .. p + |u| - 1 ] , or else by :math: max( |u| , |v| ) + 1 , in O( 1 ) extra space and at most :math: 2 n ` comparisons, made here 8 bytes at a time in both directions; its factorization, O( m ), is made only when a search comes to it.

Preparing P takes O( 256 + m ) time (the last place of each byte gives the probes) and 4 KB for the shifts; find() gives the first occurrence at or after from (npos if none), findAll() all of them, overlapping ones included, in increasing order, count() their number, and operator() the range of the first occurrence in [ first , last ), the interface of the searchers of std::search(). The empty pattern occurs at every place 0 , … , n. The functions findFirst() and findAll() of the namespace prepare P and search once.

The contracts [see File Contract.h]: an occurrence found is one, and findAll() gives those of naiveMatching() [see File StringMatching.h] (an audit, O( n m ) time). The functions are defined in StringSearch.tpp.

  1. Faro, M. O. Kulekci, Fast packed string matching for short patterns, Proceedings of the 15th Workshop on Algorithm Engineering and Experiments (ALENEX), 113-121, 2013, doi:10.1137/1.9781611972931.10

  1. Mula, SIMD-friendly algorithms for substring searching, 2016, http://0x80.pl/notesen/2016-11-28-simd-strfind.html

    1. Horspool, Practical fast searching in strings, Software: Practice and Experience 10(6), 501-506, 1980, doi:10.1002/spe.4380100608

  2. Wu, U. Manber, A fast algorithm for multi-pattern searching, Technical Report TR-94-17, Department of Computer Science, University of Arizona, 1994, https://www.cs.arizona.edu/sites/default/files/TR94-17.pdf

  3. Lecroq, Fast exact string matching algorithms, Information Processing Letters 102(6), 229-235, 2007, doi:10.1016/j.ipl.2007.01.002

  1. Crochemore, D. Perrin, Two-way string-matching, Journal of the ACM 38(3), 650-674, 1991, doi:10.1145/116825.116845

  1. Faro, T. Lecroq, The exact online string matching problem: a review of the most recent results, ACM Computing Surveys 45(2), 13:1-13:42, 2013, doi:10.1145/2431211.2431212

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions

Defines