| 1 |
This document describes the internal design of this crate, which is an object |
| 2 |
lesson in what happens when you take a fairly simple old algorithm like |
| 3 |
Aho-Corasick and make it fast and production ready. |
| 4 |
|
| 5 |
The target audience of this document is Rust programmers that have some |
| 6 |
familiarity with string searching, however, one does not need to know the |
| 7 |
Aho-Corasick algorithm in order to read this (it is explained below). One |
| 8 |
should, however, know what a trie is. (If you don't, go read its Wikipedia |
| 9 |
article.) |
| 10 |
|
| 11 |
The center-piece of this crate is an implementation of Aho-Corasick. On its |
| 12 |
own, Aho-Corasick isn't that complicated. The complex pieces come from the |
| 13 |
different variants of Aho-Corasick implemented in this crate. Specifically, |
| 14 |
they are: |
| 15 |
|
| 16 |
* Aho-Corasick as a noncontiguous NFA. States have their transitions |
| 17 |
represented sparsely, and each state puts its transitions in its own separate |
| 18 |
allocation. Hence the same "noncontiguous." |
| 19 |
* Aho-Corasick as a contiguous NFA. This NFA uses a single allocation to |
| 20 |
represent the transitions of all states. That is, transitions are laid out |
| 21 |
contiguously in memory. Moreover, states near the starting state are |
| 22 |
represented densely, such that finding the next state ID takes a constant |
| 23 |
number of instructions. |
| 24 |
* Aho-Corasick as a DFA. In this case, all states are represented densely in |
| 25 |
a transition table that uses one allocation. |
| 26 |
* Supporting "standard" match semantics, along with its overlapping variant, |
| 27 |
in addition to leftmost-first and leftmost-longest semantics. The "standard" |
| 28 |
semantics are typically what you see in a textbook description of |
| 29 |
Aho-Corasick. However, Aho-Corasick is also useful as an optimization in |
| 30 |
regex engines, which often use leftmost-first or leftmost-longest semantics. |
| 31 |
Thus, it is useful to implement those semantics here. The "standard" and |
| 32 |
"leftmost" search algorithms are subtly different, and also require slightly |
| 33 |
different construction algorithms. |
| 34 |
* Support for ASCII case insensitive matching. |
| 35 |
* Support for accelerating searches when the patterns all start with a small |
| 36 |
number of fixed bytes. Or alternatively, when the patterns all contain a |
| 37 |
small number of rare bytes. (Searching for these bytes uses SIMD vectorized |
| 38 |
code courtesy of `memchr`.) |
| 39 |
* Transparent support for alternative SIMD vectorized search routines for |
| 40 |
smaller number of literals, such as the Teddy algorithm. We called these |
| 41 |
"packed" search routines because they use SIMD. They can often be an order of |
| 42 |
magnitude faster than just Aho-Corasick, but don't scale as well. |
| 43 |
* Support for searching streams. This can reuse most of the underlying code, |
| 44 |
but does require careful buffering support. |
| 45 |
* Support for anchored searches, which permit efficient "is prefix" checks for |
| 46 |
a large number of patterns. |
| 47 |
|
| 48 |
When you combine all of this together along with trying to make everything as |
| 49 |
fast as possible, what you end up with is enitrely too much code with too much |
| 50 |
`unsafe`. Alas, I was not smart enough to figure out how to reduce it. Instead, |
| 51 |
we will explain it. |
| 52 |
|
| 53 |
|
| 54 |
# Basics |
| 55 |
|
| 56 |
The fundamental problem this crate is trying to solve is to determine the |
| 57 |
occurrences of possibly many patterns in a haystack. The naive way to solve |
| 58 |
this is to look for a match for each pattern at each position in the haystack: |
| 59 |
|
| 60 |
for i in 0..haystack.len(): |
| 61 |
for p in patterns.iter(): |
| 62 |
if haystack[i..].starts_with(p.bytes()): |
| 63 |
return Match(p.id(), i, i + p.bytes().len()) |
| 64 |
|
| 65 |
Those four lines are effectively all this crate does. The problem with those |
| 66 |
four lines is that they are very slow, especially when you're searching for a |
| 67 |
large number of patterns. |
| 68 |
|
| 69 |
While there are many different algorithms available to solve this, a popular |
| 70 |
one is Aho-Corasick. It's a common solution because it's not too hard to |
| 71 |
implement, scales quite well even when searching for thousands of patterns and |
| 72 |
is generally pretty fast. Aho-Corasick does well here because, regardless of |
| 73 |
the number of patterns you're searching for, it always visits each byte in the |
| 74 |
haystack exactly once. This means, generally speaking, adding more patterns to |
| 75 |
an Aho-Corasick automaton does not make it slower. (Strictly speaking, however, |
| 76 |
this is not true, since a larger automaton will make less effective use of the |
| 77 |
CPU's cache.) |
| 78 |
|
| 79 |
Aho-Corasick can be succinctly described as a trie with state transitions |
| 80 |
between some of the nodes that efficiently instruct the search algorithm to |
| 81 |
try matching alternative keys in the trie. The trick is that these state |
| 82 |
transitions are arranged such that each byte of input needs to be inspected |
| 83 |
only once. These state transitions are typically called "failure transitions," |
| 84 |
because they instruct the searcher (the thing traversing the automaton while |
| 85 |
reading from the haystack) what to do when a byte in the haystack does not |
| 86 |
correspond to a valid transition in the current state of the trie. |
| 87 |
|
| 88 |
More formally, a failure transition points to a state in the automaton that may |
| 89 |
lead to a match whose prefix is a proper suffix of the path traversed through |
| 90 |
the trie so far. (If no such proper suffix exists, then the failure transition |
| 91 |
points back to the start state of the trie, effectively restarting the search.) |
| 92 |
This is perhaps simpler to explain pictorally. For example, let's say we built |
| 93 |
an Aho-Corasick automaton with the following patterns: 'abcd' and 'cef'. The |
| 94 |
trie looks like this: |
| 95 |
|
| 96 |
a - S1 - b - S2 - c - S3 - d - S4* |
| 97 |
/ |
| 98 |
S0 - c - S5 - e - S6 - f - S7* |
| 99 |
|
| 100 |
where states marked with a `*` are match states (meaning, the search algorithm |
| 101 |
should stop and report a match to the caller). |
| 102 |
|
| 103 |
So given this trie, it should be somewhat straight-forward to see how it can |
| 104 |
be used to determine whether any particular haystack *starts* with either |
| 105 |
`abcd` or `cef`. It's easy to express this in code: |
| 106 |
|
| 107 |
fn has_prefix(trie: &Trie, haystack: &[u8]) -> bool { |
| 108 |
let mut state_id = trie.start(); |
| 109 |
// If the empty pattern is in trie, then state_id is a match state. |
| 110 |
if trie.is_match(state_id) { |
| 111 |
return true; |
| 112 |
} |
| 113 |
for (i, &b) in haystack.iter().enumerate() { |
| 114 |
state_id = match trie.next_state(state_id, b) { |
| 115 |
Some(id) => id, |
| 116 |
// If there was no transition for this state and byte, then we know |
| 117 |
// the haystack does not start with one of the patterns in our trie. |
| 118 |
None => return false, |
| 119 |
}; |
| 120 |
if trie.is_match(state_id) { |
| 121 |
return true; |
| 122 |
} |
| 123 |
} |
| 124 |
false |
| 125 |
} |
| 126 |
|
| 127 |
And that's pretty much it. All we do is move through the trie starting with the |
| 128 |
bytes at the beginning of the haystack. If we find ourselves in a position |
| 129 |
where we can't move, or if we've looked through the entire haystack without |
| 130 |
seeing a match state, then we know the haystack does not start with any of the |
| 131 |
patterns in the trie. |
| 132 |
|
| 133 |
The meat of the Aho-Corasick algorithm is in how we add failure transitions to |
| 134 |
our trie to keep searching efficient. Specifically, it permits us to not only |
| 135 |
check whether a haystack *starts* with any one of a number of patterns, but |
| 136 |
rather, whether the haystack contains any of a number of patterns *anywhere* in |
| 137 |
the haystack. |
| 138 |
|
| 139 |
As mentioned before, failure transitions connect a proper suffix of the path |
| 140 |
traversed through the trie before, with a path that leads to a match that has a |
| 141 |
prefix corresponding to that proper suffix. So in our case, for patterns `abcd` |
| 142 |
and `cef`, with a haystack `abcef`, we want to transition to state `S5` (from |
| 143 |
the diagram above) from `S3` upon seeing that the byte following `c` is not |
| 144 |
`d`. Namely, the proper suffix in this example is `c`, which is a prefix of |
| 145 |
`cef`. So the modified diagram looks like this: |
| 146 |
|
| 147 |
|
| 148 |
a - S1 - b - S2 - c - S3 - d - S4* |
| 149 |
/ / |
| 150 |
/ ---------------- |
| 151 |
/ / |
| 152 |
S0 - c - S5 - e - S6 - f - S7* |
| 153 |
|
| 154 |
One thing that isn't shown in this diagram is that *all* states have a failure |
| 155 |
transition, but only `S3` has a *non-trivial* failure transition. That is, all |
| 156 |
other states have a failure transition back to the start state. So if our |
| 157 |
haystack was `abzabcd`, then the searcher would transition back to `S0` after |
| 158 |
seeing `z`, which effectively restarts the search. (Because there is no pattern |
| 159 |
in our trie that has a prefix of `bz` or `z`.) |
| 160 |
|
| 161 |
The code for traversing this *automaton* or *finite state machine* (it is no |
| 162 |
longer just a trie) is not that much different from the `has_prefix` code |
| 163 |
above: |
| 164 |
|
| 165 |
fn contains(fsm: &FiniteStateMachine, haystack: &[u8]) -> bool { |
| 166 |
let mut state_id = fsm.start(); |
| 167 |
// If the empty pattern is in fsm, then state_id is a match state. |
| 168 |
if fsm.is_match(state_id) { |
| 169 |
return true; |
| 170 |
} |
| 171 |
for (i, &b) in haystack.iter().enumerate() { |
| 172 |
// While the diagram above doesn't show this, we may wind up needing |
| 173 |
// to follow multiple failure transitions before we land on a state |
| 174 |
// in which we can advance. Therefore, when searching for the next |
| 175 |
// state, we need to loop until we don't see a failure transition. |
| 176 |
// |
| 177 |
// This loop terminates because the start state has no empty |
| 178 |
// transitions. Every transition from the start state either points to |
| 179 |
// another state, or loops back to the start state. |
| 180 |
loop { |
| 181 |
match fsm.next_state(state_id, b) { |
| 182 |
Some(id) => { |
| 183 |
state_id = id; |
| 184 |
break; |
| 185 |
} |
| 186 |
// Unlike our code above, if there was no transition for this |
| 187 |
// state, then we don't quit. Instead, we look for this state's |
| 188 |
// failure transition and follow that instead. |
| 189 |
None => { |
| 190 |
state_id = fsm.next_fail_state(state_id); |
| 191 |
} |
| 192 |
}; |
| 193 |
} |
| 194 |
if fsm.is_match(state_id) { |
| 195 |
return true; |
| 196 |
} |
| 197 |
} |
| 198 |
false |
| 199 |
} |
| 200 |
|
| 201 |
Other than the complication around traversing failure transitions, this code |
| 202 |
is still roughly "traverse the automaton with bytes from the haystack, and quit |
| 203 |
when a match is seen." |
| 204 |
|
| 205 |
And that concludes our section on the basics. While we didn't go deep into how |
| 206 |
the automaton is built (see `src/nfa/noncontiguous.rs`, which has detailed |
| 207 |
comments about that), the basic structure of Aho-Corasick should be reasonably |
| 208 |
clear. |
| 209 |
|
| 210 |
|
| 211 |
# NFAs and DFAs |
| 212 |
|
| 213 |
There are generally two types of finite automata: non-deterministic finite |
| 214 |
automata (NFA) and deterministic finite automata (DFA). The difference between |
| 215 |
them is, principally, that an NFA can be in multiple states at once. This is |
| 216 |
typically accomplished by things called _epsilon_ transitions, where one could |
| 217 |
move to a new state without consuming any bytes from the input. (The other |
| 218 |
mechanism by which NFAs can be in more than one state is where the same byte in |
| 219 |
a particular state transitions to multiple distinct states.) In contrast, a DFA |
| 220 |
can only ever be in one state at a time. A DFA has no epsilon transitions, and |
| 221 |
for any given state, a byte transitions to at most one other state. |
| 222 |
|
| 223 |
By this formulation, the Aho-Corasick automaton described in the previous |
| 224 |
section is an NFA. This is because failure transitions are, effectively, |
| 225 |
epsilon transitions. That is, whenever the automaton is in state `S`, it is |
| 226 |
actually in the set of states that are reachable by recursively following |
| 227 |
failure transitions from `S` until you reach the start state. (This means |
| 228 |
that, for example, the start state is always active since the start state is |
| 229 |
reachable via failure transitions from any state in the automaton.) |
| 230 |
|
| 231 |
NFAs have a lot of nice properties. They tend to be easier to construct, and |
| 232 |
also tend to use less memory. However, their primary downside is that they are |
| 233 |
typically slower to execute a search with. For example, the code above showing |
| 234 |
how to search with an Aho-Corasick automaton needs to potentially iterate |
| 235 |
through many failure transitions for every byte of input. While this is a |
| 236 |
fairly small amount of overhead, this can add up, especially if the automaton |
| 237 |
has a lot of overlapping patterns with a lot of failure transitions. |
| 238 |
|
| 239 |
A DFA's search code, by contrast, looks like this: |
| 240 |
|
| 241 |
fn contains(dfa: &DFA, haystack: &[u8]) -> bool { |
| 242 |
let mut state_id = dfa.start(); |
| 243 |
// If the empty pattern is in dfa, then state_id is a match state. |
| 244 |
if dfa.is_match(state_id) { |
| 245 |
return true; |
| 246 |
} |
| 247 |
for (i, &b) in haystack.iter().enumerate() { |
| 248 |
// An Aho-Corasick DFA *never* has a missing state that requires |
| 249 |
// failure transitions to be followed. One byte of input advances the |
| 250 |
// automaton by one state. Always. |
| 251 |
state_id = dfa.next_state(state_id, b); |
| 252 |
if dfa.is_match(state_id) { |
| 253 |
return true; |
| 254 |
} |
| 255 |
} |
| 256 |
false |
| 257 |
} |
| 258 |
|
| 259 |
The search logic here is much simpler than for the NFA, and this tends to |
| 260 |
translate into significant performance benefits as well, since there's a lot |
| 261 |
less work being done for each byte in the haystack. How is this accomplished? |
| 262 |
It's done by pre-following all failure transitions for all states for all bytes |
| 263 |
in the alphabet, and then building a single state transition table. Building |
| 264 |
this DFA can be much more costly than building the NFA, and use much more |
| 265 |
memory, but the better performance can be worth it. |
| 266 |
|
| 267 |
Users of this crate can actually choose between using one of two possible NFAs |
| 268 |
(noncontiguous or contiguous) or a DFA. By default, a contiguous NFA is used, |
| 269 |
in most circumstances, but if the number of patterns is small enough a DFA will |
| 270 |
be used. A contiguous NFA is chosen because it uses orders of magnitude less |
| 271 |
memory than a DFA, takes only a little longer to build than a noncontiguous |
| 272 |
NFA and usually gets pretty close to the search speed of a DFA. (Callers can |
| 273 |
override this automatic selection via the `AhoCorasickBuilder::start_kind` |
| 274 |
configuration.) |
| 275 |
|
| 276 |
|
| 277 |
# More DFA tricks |
| 278 |
|
| 279 |
As described in the previous section, one of the downsides of using a DFA |
| 280 |
is that it uses more memory and can take longer to build. One small way of |
| 281 |
mitigating these concerns is to map the alphabet used by the automaton into |
| 282 |
a smaller space. Typically, the alphabet of a DFA has 256 elements in it: |
| 283 |
one element for each possible value that fits into a byte. However, in many |
| 284 |
cases, one does not need the full alphabet. For example, if all patterns in an |
| 285 |
Aho-Corasick automaton are ASCII letters, then this only uses up 52 distinct |
| 286 |
bytes. As far as the automaton is concerned, the rest of the 204 bytes are |
| 287 |
indistinguishable from one another: they will never disrciminate between a |
| 288 |
match or a non-match. Therefore, in cases like that, the alphabet can be shrunk |
| 289 |
to just 53 elements. One for each ASCII letter, and then another to serve as a |
| 290 |
placeholder for every other unused byte. |
| 291 |
|
| 292 |
In practice, this library doesn't quite compute the optimal set of equivalence |
| 293 |
classes, but it's close enough in most cases. The key idea is that this then |
| 294 |
allows the transition table for the DFA to be potentially much smaller. The |
| 295 |
downside of doing this, however, is that since the transition table is defined |
| 296 |
in terms of this smaller alphabet space, every byte in the haystack must be |
| 297 |
re-mapped to this smaller space. This requires an additional 256-byte table. |
| 298 |
In practice, this can lead to a small search time hit, but it can be difficult |
| 299 |
to measure. Moreover, it can sometimes lead to faster search times for bigger |
| 300 |
automata, since it could be difference between more parts of the automaton |
| 301 |
staying in the CPU cache or not. |
| 302 |
|
| 303 |
One other trick for DFAs employed by this crate is the notion of premultiplying |
| 304 |
state identifiers. Specifically, the normal way to compute the next transition |
| 305 |
in a DFA is via the following (assuming that the transition table is laid out |
| 306 |
sequentially in memory, in row-major order, where the rows are states): |
| 307 |
|
| 308 |
next_state_id = dfa.transitions[current_state_id * 256 + current_byte] |
| 309 |
|
| 310 |
However, since the value `256` is a fixed constant, we can actually premultiply |
| 311 |
the state identifiers in the table when we build the table initially. Then, the |
| 312 |
next transition computation simply becomes: |
| 313 |
|
| 314 |
next_state_id = dfa.transitions[current_state_id + current_byte] |
| 315 |
|
| 316 |
This doesn't seem like much, but when this is being executed for every byte of |
| 317 |
input that you're searching, saving that extra multiplication instruction can |
| 318 |
add up. |
| 319 |
|
| 320 |
The same optimization works even when equivalence classes are enabled, as |
| 321 |
described above. The only difference is that the premultiplication is by the |
| 322 |
total number of equivalence classes instead of 256. |
| 323 |
|
| 324 |
There isn't much downside to premultiplying state identifiers, other than it |
| 325 |
imposes a smaller limit on the total number of states in the DFA. Namely, with |
| 326 |
premultiplied state identifiers, you run out of room in your state identifier |
| 327 |
representation more rapidly than if the identifiers are just state indices. |
| 328 |
|
| 329 |
Both equivalence classes and premultiplication are always enabled. There is a |
| 330 |
`AhoCorasickBuilder::byte_classes` configuration, but disabling this just makes |
| 331 |
it so there are always 256 equivalence classes, i.e., every class corresponds |
| 332 |
to precisely one byte. When it's disabled, the equivalence class map itself is |
| 333 |
still used. The purpose of disabling it is when one is debugging the underlying |
| 334 |
automaton. It can be easier to comprehend when it uses actual byte values for |
| 335 |
its transitions instead of equivalence classes. |
| 336 |
|
| 337 |
|
| 338 |
# Match semantics |
| 339 |
|
| 340 |
One of the more interesting things about this implementation of Aho-Corasick |
| 341 |
that (as far as this author knows) separates it from other implementations, is |
| 342 |
that it natively supports leftmost-first and leftmost-longest match semantics. |
| 343 |
Briefly, match semantics refer to the decision procedure by which searching |
| 344 |
will disambiguate matches when there are multiple to choose from: |
| 345 |
|
| 346 |
* **standard** match semantics emits matches as soon as they are detected by |
| 347 |
the automaton. This is typically equivalent to the textbook non-overlapping |
| 348 |
formulation of Aho-Corasick. |
| 349 |
* **leftmost-first** match semantics means that 1) the next match is the match |
| 350 |
starting at the leftmost position and 2) among multiple matches starting at |
| 351 |
the same leftmost position, the match corresponding to the pattern provided |
| 352 |
first by the caller is reported. |
| 353 |
* **leftmost-longest** is like leftmost-first, except when there are multiple |
| 354 |
matches starting at the same leftmost position, the pattern corresponding to |
| 355 |
the longest match is returned. |
| 356 |
|
| 357 |
(The crate API documentation discusses these differences, with examples, in |
| 358 |
more depth on the `MatchKind` type.) |
| 359 |
|
| 360 |
The reason why supporting these match semantics is important is because it |
| 361 |
gives the user more control over the match procedure. For example, |
| 362 |
leftmost-first permits users to implement match priority by simply putting the |
| 363 |
higher priority patterns first. Leftmost-longest, on the other hand, permits |
| 364 |
finding the longest possible match, which might be useful when trying to find |
| 365 |
words matching a dictionary. Additionally, regex engines often want to use |
| 366 |
Aho-Corasick as an optimization when searching for an alternation of literals. |
| 367 |
In order to preserve correct match semantics, regex engines typically can't use |
| 368 |
the standard textbook definition directly, since regex engines will implement |
| 369 |
either leftmost-first (Perl-like) or leftmost-longest (POSIX) match semantics. |
| 370 |
|
| 371 |
Supporting leftmost semantics requires a couple key changes: |
| 372 |
|
| 373 |
* Constructing the Aho-Corasick automaton changes a bit in both how the trie is |
| 374 |
constructed and how failure transitions are found. Namely, only a subset |
| 375 |
of the failure transitions are added. Specifically, only the failure |
| 376 |
transitions that either do not occur after a match or do occur after a match |
| 377 |
but preserve that match are kept. (More details on this can be found in |
| 378 |
`src/nfa/noncontiguous.rs`.) |
| 379 |
* The search algorithm changes slightly. Since we are looking for the leftmost |
| 380 |
match, we cannot quit as soon as a match is detected. Instead, after a match |
| 381 |
is detected, we must keep searching until either the end of the input or |
| 382 |
until a dead state is seen. (Dead states are not used for standard match |
| 383 |
semantics. Dead states mean that searching should stop after a match has been |
| 384 |
found.) |
| 385 |
|
| 386 |
Most other implementations of Aho-Corasick do support leftmost match semantics, |
| 387 |
but they do it with more overhead at search time, or even worse, with a queue |
| 388 |
of matches and sophisticated hijinks to disambiguate the matches. While our |
| 389 |
construction algorithm becomes a bit more complicated, the correct match |
| 390 |
semantics fall out from the structure of the automaton itself. |
| 391 |
|
| 392 |
|
| 393 |
# Overlapping matches |
| 394 |
|
| 395 |
One of the nice properties of an Aho-Corasick automaton is that it can report |
| 396 |
all possible matches, even when they overlap with one another. In this mode, |
| 397 |
the match semantics don't matter, since all possible matches are reported. |
| 398 |
Overlapping searches work just like regular searches, except the state |
| 399 |
identifier at which the previous search left off is carried over to the next |
| 400 |
search, so that it can pick up where it left off. If there are additional |
| 401 |
matches at that state, then they are reported before resuming the search. |
| 402 |
|
| 403 |
Enabling leftmost-first or leftmost-longest match semantics causes the |
| 404 |
automaton to use a subset of all failure transitions, which means that |
| 405 |
overlapping searches cannot be used. Therefore, if leftmost match semantics are |
| 406 |
used, attempting to do an overlapping search will return an error (or panic |
| 407 |
when using the infallible APIs). Thus, to get overlapping searches, the caller |
| 408 |
must use the default standard match semantics. This behavior was chosen because |
| 409 |
there are only two alternatives, which were deemed worse: |
| 410 |
|
| 411 |
* Compile two automatons internally, one for standard semantics and one for |
| 412 |
the semantics requested by the caller (if not standard). |
| 413 |
* Create a new type, distinct from the `AhoCorasick` type, which has different |
| 414 |
capabilities based on the configuration options. |
| 415 |
|
| 416 |
The first is untenable because of the amount of memory used by the automaton. |
| 417 |
The second increases the complexity of the API too much by adding too many |
| 418 |
types that do similar things. It is conceptually much simpler to keep all |
| 419 |
searching isolated to a single type. |
| 420 |
|
| 421 |
|
| 422 |
# Stream searching |
| 423 |
|
| 424 |
Since Aho-Corasick is an automaton, it is possible to do partial searches on |
| 425 |
partial parts of the haystack, and then resume that search on subsequent pieces |
| 426 |
of the haystack. This is useful when the haystack you're trying to search is |
| 427 |
not stored contiguously in memory, or if one does not want to read the entire |
| 428 |
haystack into memory at once. |
| 429 |
|
| 430 |
Currently, only standard semantics are supported for stream searching. This is |
| 431 |
some of the more complicated code in this crate, and is something I would very |
| 432 |
much like to improve. In particular, it currently has the restriction that it |
| 433 |
must buffer at least enough of the haystack in memory in order to fit the |
| 434 |
longest possible match. The difficulty in getting stream searching right is |
| 435 |
that the implementation choices (such as the buffer size) often impact what the |
| 436 |
API looks like and what it's allowed to do. |
| 437 |
|
| 438 |
|
| 439 |
# Prefilters |
| 440 |
|
| 441 |
In some cases, Aho-Corasick is not the fastest way to find matches containing |
| 442 |
multiple patterns. Sometimes, the search can be accelerated using highly |
| 443 |
optimized SIMD routines. For example, consider searching the following |
| 444 |
patterns: |
| 445 |
|
| 446 |
Sherlock |
| 447 |
Moriarty |
| 448 |
Watson |
| 449 |
|
| 450 |
It is plausible that it would be much faster to quickly look for occurrences of |
| 451 |
the leading bytes, `S`, `M` or `W`, before trying to start searching via the |
| 452 |
automaton. Indeed, this is exactly what this crate will do. |
| 453 |
|
| 454 |
When there are more than three distinct starting bytes, then this crate will |
| 455 |
look for three distinct bytes occurring at any position in the patterns, while |
| 456 |
preferring bytes that are heuristically determined to be rare over others. For |
| 457 |
example: |
| 458 |
|
| 459 |
Abuzz |
| 460 |
Sanchez |
| 461 |
Vasquez |
| 462 |
Topaz |
| 463 |
Waltz |
| 464 |
|
| 465 |
Here, we have more than 3 distinct starting bytes, but all of the patterns |
| 466 |
contain `z`, which is typically a rare byte. In this case, the prefilter will |
| 467 |
scan for `z`, back up a bit, and then execute the Aho-Corasick automaton. |
| 468 |
|
| 469 |
If all of that fails, then a packed multiple substring algorithm will be |
| 470 |
attempted. Currently, the only algorithm available for this is Teddy, but more |
| 471 |
may be added in the future. Teddy is unlike the above prefilters in that it |
| 472 |
confirms its own matches, so when Teddy is active, it might not be necessary |
| 473 |
for Aho-Corasick to run at all. However, the current Teddy implementation |
| 474 |
only works in `x86_64` when SSSE3 or AVX2 are available or in `aarch64` |
| 475 |
(using NEON), and moreover, only works _well_ when there are a small number |
| 476 |
of patterns (say, less than 100). Teddy also requires the haystack to be of a |
| 477 |
certain length (more than 16-34 bytes). When the haystack is shorter than that, |
| 478 |
Rabin-Karp is used instead. (See `src/packed/rabinkarp.rs`.) |
| 479 |
|
| 480 |
There is a more thorough description of Teddy at |
| 481 |
[`src/packed/teddy/README.md`](src/packed/teddy/README.md). |