File MultiSearch.h

↰ Parent directory (ADS/string)

The engineered search of many patterns at once, beyond the book: MultiSearcher finds all the occurrences in a text T of n bytes of k patterns :math:` P_0 , ldots , P_{k-1} : one pattern by StringSearcher [see :ref:`file_ADS_string_StringSearch.h], up to 64 by a filter of shuffles of bytes, more by a filter of shift-or on super characters, and by the automaton of Aho and Corasick [see File AhoCorasick.h] where a filter lets too much through; the benchmark of the multiple search compares it with AhoCorasick and with Vectorscan (the portable Hyperscan).

Definition (ADS/string/MultiSearch.h)

Detailed Description

The filter of shuffles puts the patterns, sorted, into 8 buckets of consecutive ones, so that the patterns of a bucket tend to share their first bytes (the patterns go into buckets, and the buckets are told apart by the 8 bits of a byte, as in the FDR matcher of Hyperscan). The place i of T is a candidate for the bucket b if, for every :math:` r < q , some pattern of b has the low half (4 bits) of :math: T[ i + r ] ` as the low half of its byte r and some pattern of b (maybe another) the high half as the high half: :math:`[
C_i = bigwedge_{ r < q } mathit{lo}_r[ T[ i + r ] bmod 16 ] wedge

mathit{hi}_r[ lfloor T[ i + r ] / 16 rfloor ] ,

` the bit b of the tables :math:` mathit{lo}_r ` and :math:` mathit{hi}_r ` (16 bytes each) set for the halves of the bytes r of the patterns of b. q is the least number of bytes, at most 8 and at most the shortest pattern, that brings the probability of a place to pass below :math:` 2^{-10} , the bytes of the text drawn with the frequencies of the bytes of the patterns: :math: prod_{ r < q } sum_x f( x ) [ C( x , r ) neq 0 ] < 2^{-10} `, so that a large alphabet needs one or two bytes and a small one more. A table of 16 bytes is one register, and one shuffle of bytes (vpshufb) looks up 32 places of T at once, so that a block of 32 places costs q loads, 2 q shuffles and a few logical operations, with no branch but the one on a candidate. A candidate is checked against the patterns of its buckets, by their first 8 bytes in one comparison of words and then by the rest. Every occurrence makes its place a candidate for its bucket, so that nothing is missed; when the checks exceed 2 a place on average (patterns everywhere, or a text whose bytes the filter cannot tell apart), the automaton goes on from the place reached, its occurrences that start before it left out (and count() takes the count of the automaton from a little before that place, less the occurrences before it in a window of the length of the longest pattern).

Above 64 patterns the halves of the bytes of a bucket cover them all, and the filter of shift-or of FDR takes over, on the first :math:` L = min( 8 , ell ) ` bytes of the patterns, :math:` ell ` the shortest. The super character of the place p is :math:` T[ p ] ` with the low 3 bits of :math:` T[ p + 1 ] , 11 bits, and its mask of 64 bits has the bit b of its byte :math: L - 1 - r ` off if a pattern of the bucket b has that super character at its place r < L (its byte r and the low bits of the byte r + 1, any of them past its end), the bytes from L on all off. A pattern that starts at s can then end its window at :math:` e = s + L - 1 ` only if the bit b of the byte :math:` e - p ` of the mask of p is off for every :math:` e - L < p le e `: :math:`[

mathit{St}_e = bigvee_{ t < L } mathit{sh}[ x( e - t ) ]_t

` has a bit off. A block of 8 places adds each mask moved by d bytes into a register of 16 bytes, the states of its 8 ends and of the next 8, one load, one shift of bytes and one or a place, the 11 bits read from two words of the text with no other load; the table of the masks is 16 KB. A state with a bit off sends its start to a table of the prefixes of L bytes of the patterns (chained, by a multiplicative hash), which checks the patterns of that prefix. When the patterns have 8 bytes or more, the filter takes the masks of the even places alone (a stride of 2, as FDR does on long patterns), half the loads: a window of :math:` W = min( 8 , lfloor ell / 2 rfloor ) ` even places, and each pattern twice, at its even offsets for the occurrences that start at an even place (in 4 buckets, the bits 0 to 3) and at its odd ones for the others (the bits 4 to 7), kept only if a window passes with probability below 2^-8 on a text of the super characters of the patterns, since its buckets hold twice the patterns.

findAll() gives the pairs ( start , number ) of the occurrences, by increasing start and number, count() their number; the patterns are numbered in their order, and the empty pattern is not allowed.

The contracts [see File Contract.h]: a pattern is not empty; findAll() gives, for each pattern, the occurrences of naiveMatching() [see File StringMatching.h] (an audit). The functions are defined in MultiSearch.tpp.

  1. Wang, Y. Hong, H. Chang, K. Park, G. Langdale, J. Hu, H. Zhu, Hyperscan: a fast multi-pattern regex matcher for modern CPUs, Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 631-648, 2019, https://www.usenix.org/conference/nsdi19/presentation/wang-xiang

    1. Aho, M. J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM 18(6), 333-340, 1975, doi:10.1145/360825.360855

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes