1aho-corasick 2============ 3A library for finding occurrences of many patterns at once with SIMD 4acceleration in some cases. This library provides multiple pattern 5search principally through an implementation of the 6[Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm), 7which builds a finite state machine for executing searches in linear time. 8Features include case insensitive matching, overlapping matches, fast searching 9via SIMD and optional full DFA construction and search & replace in streams. 10 11[](https://github.com/BurntSushi/aho-corasick/actions) 12[](https://crates.io/crates/aho-corasick) 13 14Dual-licensed under MIT or the [UNLICENSE](https://unlicense.org/). 15 16 17### Documentation 18 19https://docs.rs/aho-corasick 20 21 22### Usage 23 24Add this to your `Cargo.toml`: 25 26```toml 27[dependencies] 28aho-corasick = "0.7" 29``` 30 31 32### Example: basic searching 33 34This example shows how to search for occurrences of multiple patterns 35simultaneously. Each match includes the pattern that matched along with the 36byte offsets of the match. 37 38```rust 39use aho_corasick::AhoCorasick; 40 41let patterns = &["apple", "maple", "Snapple"]; 42let haystack = "Nobody likes maple in their apple flavored Snapple."; 43 44let ac = AhoCorasick::new(patterns); 45let mut matches = vec![]; 46for mat in ac.find_iter(haystack) { 47 matches.push((mat.pattern(), mat.start(), mat.end())); 48} 49assert_eq!(matches, vec![ 50 (1, 13, 18), 51 (0, 28, 33), 52 (2, 43, 50), 53]); 54``` 55 56 57### Example: case insensitivity 58 59This is like the previous example, but matches `Snapple` case insensitively 60using `AhoCorasickBuilder`: 61 62```rust 63use aho_corasick::AhoCorasickBuilder; 64 65let patterns = &["apple", "maple", "snapple"]; 66let haystack = "Nobody likes maple in their apple flavored Snapple."; 67 68let ac = AhoCorasickBuilder::new() 69 .ascii_case_insensitive(true) 70 .build(patterns); 71let mut matches = vec![]; 72for mat in ac.find_iter(haystack) { 73 matches.push((mat.pattern(), mat.start(), mat.end())); 74} 75assert_eq!(matches, vec![ 76 (1, 13, 18), 77 (0, 28, 33), 78 (2, 43, 50), 79]); 80``` 81 82 83### Example: replacing matches in a stream 84 85This example shows how to execute a search and replace on a stream without 86loading the entire stream into memory first. 87 88```rust 89use aho_corasick::AhoCorasick; 90 91let patterns = &["fox", "brown", "quick"]; 92let replace_with = &["sloth", "grey", "slow"]; 93 94// In a real example, these might be `std::fs::File`s instead. All you need to 95// do is supply a pair of `std::io::Read` and `std::io::Write` implementations. 96let rdr = "The quick brown fox."; 97let mut wtr = vec![]; 98 99let ac = AhoCorasick::new(patterns); 100ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with) 101 .expect("stream_replace_all failed"); 102assert_eq!(b"The slow grey sloth.".to_vec(), wtr); 103``` 104 105 106### Example: finding the leftmost first match 107 108In the textbook description of Aho-Corasick, its formulation is typically 109structured such that it reports all possible matches, even when they overlap 110with another. In many cases, overlapping matches may not be desired, such as 111the case of finding all successive non-overlapping matches like you might with 112a standard regular expression. 113 114Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do 115this doesn't always work in the expected way, since it will report matches as 116soon as they are seen. For example, consider matching the regex `Samwise|Sam` 117against the text `Samwise`. Most regex engines (that are Perl-like, or 118non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick 119algorithm modified for reporting non-overlapping matches will report `Sam`. 120 121A novel contribution of this library is the ability to change the match 122semantics of Aho-Corasick (without additional search time overhead) such that 123`Samwise` is reported instead. For example, here's the standard approach: 124 125```rust 126use aho_corasick::AhoCorasick; 127 128let patterns = &["Samwise", "Sam"]; 129let haystack = "Samwise"; 130 131let ac = AhoCorasick::new(patterns); 132let mat = ac.find(haystack).expect("should have a match"); 133assert_eq!("Sam", &haystack[mat.start()..mat.end()]); 134``` 135 136And now here's the leftmost-first version, which matches how a Perl-like 137regex will work: 138 139```rust 140use aho_corasick::{AhoCorasickBuilder, MatchKind}; 141 142let patterns = &["Samwise", "Sam"]; 143let haystack = "Samwise"; 144 145let ac = AhoCorasickBuilder::new() 146 .match_kind(MatchKind::LeftmostFirst) 147 .build(patterns); 148let mat = ac.find(haystack).expect("should have a match"); 149assert_eq!("Samwise", &haystack[mat.start()..mat.end()]); 150``` 151 152In addition to leftmost-first semantics, this library also supports 153leftmost-longest semantics, which match the POSIX behavior of a regular 154expression alternation. See `MatchKind` in the docs for more details. 155 156 157### Minimum Rust version policy 158 159This crate's minimum supported `rustc` version is `1.41.1`. 160 161The current policy is that the minimum Rust version required to use this crate 162can be increased in minor version updates. For example, if `crate 1.0` requires 163Rust 1.20.0, then `crate 1.0.z` for all values of `z` will also require Rust 1641.20.0 or newer. However, `crate 1.y` for `y > 0` may require a newer minimum 165version of Rust. 166 167In general, this crate will be conservative with respect to the minimum 168supported version of Rust. 169 170 171### FFI bindings 172 173* [G-Research/ahocorasick_rs](https://github.com/G-Research/ahocorasick_rs/) 174is a Python wrapper for this library. 175 176 177### Future work 178 179Here are some plans for the future: 180 181* Assuming the current API is sufficient, I'd like to commit to it and release 182 a `1.0` version of this crate some time in the next 6-12 months. 183* Support stream searching with leftmost match semantics. Currently, only 184 standard match semantics are supported. Getting this right seems possible, 185 but is tricky since the match state needs to be propagated through multiple 186 searches. (With standard semantics, as soon as a match is seen the search 187 ends.) 188
){kind=link}
){kind=link}