### 34 releases

0.7.3 | Mar 31, 2019 |
---|---|

0.6.10 | Feb 16, 2019 |

0.6.9 | Oct 29, 2018 |

0.6.6 | Jul 12, 2018 |

0.3.0 | Jul 14, 2015 |

#**4** in Text processing

**550,546** downloads per month

Used in **5,339** crates (13 directly)

**Unlicense/MIT**

235KB

3.5K
SLoC

# aho-corasick

A library for finding occurrences of many patterns at once. This library provides multiple pattern search principally through an implementation of the Aho-Corasick algorithm, which builds a fast finite state machine for executing searches in linear time. Features include case insensitive matching, overlapping matches and search & replace in streams.

Dual-licensed under MIT or the UNLICENSE.

### Documentation

### Usage

Add this to your

:`Cargo .toml`

`[``dependencies``]`
`aho-corasick ``=` `"`0.7`"`

and this to your crate root (if you're using Rust 2015):

`extern` `crate` aho_corasick`;`

### Example: basic searching

This example shows how to search for occurrences of multiple patterns simultaneously. Each match includes the pattern that matched along with the byte offsets of the match.

`use` `aho_corasick``::`AhoCorasick`;`
`let` patterns `=` `&``[``"`apple`"``,` `"`maple`"``,` `"`Snapple`"``]``;`
`let` haystack `=` `"`Nobody likes maple in their apple flavored Snapple.`"``;`
`let` ac `=` `AhoCorasick``::`new`(`patterns`)``;`
`let` `mut` matches `=` `vec!``[``]``;`
`for` mat `in` ac`.``find_iter``(`haystack`)` `{`
matches`.``push``(``(`mat`.``pattern``(``)``,` mat`.``start``(``)``,` mat`.``end``(``)``)``)``;`
`}`
`assert_eq!``(`matches`,` `vec!``[`
`(``1``,` `13``,` `18``)``,`
`(``0``,` `28``,` `33``)``,`
`(``2``,` `43``,` `50``)``,`
`]``)``;`

### Example: case insensitivity

This is like the previous example, but matches

case insensitively
using `Snapple`

:`AhoCorasickBuilder`

`use` `aho_corasick``::`AhoCorasickBuilder`;`
`let` patterns `=` `&``[``"`apple`"``,` `"`maple`"``,` `"`snapple`"``]``;`
`let` haystack `=` `"`Nobody likes maple in their apple flavored Snapple.`"``;`
`let` ac `=` `AhoCorasickBuilder``::`new`(``)`
`.``ascii_case_insensitive``(``true``)`
`.``build``(`patterns`)``;`
`let` `mut` matches `=` `vec!``[``]``;`
`for` mat `in` ac`.``find_iter``(`haystack`)` `{`
matches`.``push``(``(`mat`.``pattern``(``)``,` mat`.``start``(``)``,` mat`.``end``(``)``)``)``;`
`}`
`assert_eq!``(`matches`,` `vec!``[`
`(``1``,` `13``,` `18``)``,`
`(``0``,` `28``,` `33``)``,`
`(``2``,` `43``,` `50``)``,`
`]``)``;`

### Example: replacing matches in a stream

This example shows how to execute a search and replace on a stream without loading the entire stream into memory first.

`use` `aho_corasick``::`AhoCorasick`;`
`#` `fn` `example``(``)`` ``->` `Result``<``(``)`, `::``std``::``io``::`Error`>` `{`
`let` patterns `=` `&``[``"`fox`"``,` `"`brown`"``,` `"`quick`"``]``;`
`let` replace_with `=` `&``[``"`sloth`"``,` `"`grey`"``,` `"`slow`"``]``;`
`//` In a real example, these might be `std::fs::File`s instead. All you need to
`//` do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
`let` rdr `=` `"`The quick brown fox.`"``;`
`let` `mut` wtr `=` `vec!``[``]``;`
`let` ac `=` `AhoCorasick``::`new`(`patterns`)``;`
ac`.``stream_replace_all``(`rdr`.``as_bytes``(``)``,` `&``mut` wtr`,` replace_with`)``?``;`
`assert_eq!``(``b``"`The slow grey sloth.`"``.``to_vec``(``)``,` wtr`)``;`
`#` `Ok``(``(``)``)` `}``;` `example``(``)``.``unwrap``(``)`

### Example: finding the leftmost first match

In the textbook description of Aho-Corasick, its formulation is typically structured such that it reports all possible matches, even when they overlap with another. In many cases, overlapping matches may not be desired, such as the case of finding all successive non-overlapping matches like you might with a standard regular expression.

Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do
this doesn't always work in the expected way, since it will report matches as
soon as they are seen. For example, consider matching the regex

against the text `Samwise |Sam`

`Samwise`

. Most regex engines (that are Perl-like, or
non-POSIX) will report `Samwise`

as a match, but the standard Aho-Corasick
algorithm modified for reporting non-overlapping matches will report `Sam`

.A novel contribution of this library is the ability to change the match
semantics of Aho-Corasick (without additional search time overhead) such that

is reported instead. For example, here's the standard approach:`Samwise`

`use` `aho_corasick``::`AhoCorasick`;`
`let` patterns `=` `&``[``"`Samwise`"``,` `"`Sam`"``]``;`
`let` haystack `=` `"`Samwise`"``;`
`let` ac `=` `AhoCorasick``::`new`(`patterns`)``;`
`let` mat `=` ac`.``find``(`haystack`)``.``expect``(``"`should have a match`"``)``;`
`assert_eq!``(``"`Sam`"``,` `&`haystack`[`mat`.``start``(``)``..`mat`.``end``(``)``]``)``;`

And now here's the leftmost-first version, which matches how a Perl-like regex will work:

`use` `aho_corasick``::``{`AhoCorasickBuilder`,` MatchKind`}``;`
`let` patterns `=` `&``[``"`Samwise`"``,` `"`Sam`"``]``;`
`let` haystack `=` `"`Samwise`"``;`
`let` ac `=` `AhoCorasickBuilder``::`new`(``)`
`.``match_kind``(``MatchKind``::`LeftmostFirst`)`
`.``build``(`patterns`)``;`
`let` mat `=` ac`.``find``(`haystack`)``.``expect``(``"`should have a match`"``)``;`
`assert_eq!``(``"`Samwise`"``,` `&`haystack`[`mat`.``start``(``)``..`mat`.``end``(``)``]``)``;`

In addition to leftmost-first semantics, this library also supports
leftmost-longest semantics, which match the POSIX behavior of a regular
expression alternation. See

in the docs for more details.`MatchKind`

### Minimum Rust version policy

This crate's minimum supported

version is `rustc`

.`1.``24``.``1`

In general, this crate will be conservative with respect to the minimum
supported version of Rust. In general, it will follow the

crate's
policy, since `regex`

is an important dependent.`regex`

### Future work

Here are some plans for the future:

- Assuming the current API is sufficient, I'd like to commit to it and release
a

version of this crate some time in the next 6-12 months.`1.``0` - Despite the crate's name, it seems prudent to consolidate all
multi-pattern search optimizations into this crate so that they get the
widest possible use. A good place to start will be to move the regex
crate's Teddy algorithm into this one. (This is more than just a move. It
will require fleshing out the somewhat simplistic

design that exists internally currently.) In the future, it would be good to loot Hyperscan for some of its pertinent algorithms, such as FDR.`Prefilter` - Support stream searching with leftmost match semantics. Currently, only standard match semantics are supported. Getting this right seems possible, but is tricky since the match state needs to be propagated through multiple searches. (With standard semantics, as soon as a match is seen the search ends.)