# Matcher
A high-performance, multi-functional word matcher implemented in Rust.
Designed to solve **AND OR NOT** and **TEXT VARIATIONS** problems in word/word_list matching. For detailed implementation, see the [Design Document](../DESIGN.md).
## Features
- **Multiple Matching Methods**:
- Simple Word Matching
- Regex-Based Matching
- Similarity-Based Matching
- **Text Normalization**:
- **Fanjian**: Simplify traditional Chinese characters to simplified ones.
Example: `่ฒ่ธ` -> `่ซ่`
- **Delete**: Remove specific characters.
Example: `*Fu&*iii&^%%*&kkkk` -> `Fuiiikkkk`
- **Normalize**: Normalize special characters to identifiable characters.
Example: `๐ข๐ฐ๐๐ปฯ ๐โฦฆโ๐!` -> `hello world!`
- **PinYin**: Convert Chinese characters to Pinyin for fuzzy matching.
Example: `่ฅฟๅฎ` -> `/xi//an/`, matches `ๆดๆ` -> `/xi//an/`, but not `ๅ
` -> `/xian/`
- **PinYinChar**: Convert Chinese characters to Pinyin.
Example: `่ฅฟๅฎ` -> `xian`, matches `ๆดๆ` and `ๅ
` -> `xian`
- **AND OR NOT Word Matching**:
- Takes into account the number of repetitions of words.
- Example: `hello&world` matches `hello world` and `world,hello`
- Example: `ๆ &ๆณ&ๆ &ๅคฉ` matches `ๆ ๆ ๆณๅคฉ` (because `ๆ ` is repeated twice), but not `ๆ ๆณๅคฉ`
- Example: `hello~helloo~hhello` matches `hello` but not `helloo` and `hhello`
- **Customizable Exemption Lists**: Exclude specific words from matching.
- **Efficient Handling of Large Word Lists**: Optimized for performance.
## Usage
### Adding to Your Project
To use `matcher_rs` in your Rust project, run the following command:
```shell
cargo add matcher_rs
```
### Explanation of the configuration
* `Matcher`'s configuration is defined by the `MatchTableMap = HashMap<u32, Vec<MatchTable>>` type, the key of `MatchTableMap` is called `match_id`, for each `match_id`, the `table_id` inside **should but isn't required to be unique**.
* `SimpleMatcher`'s configuration is defined by the `SimpleMatchTableMap = HashMap<SimpleMatchType, HashMap<u32, &'a str>>` type, the value `HashMap<u32, &'a str>`'s key is called `word_id`, **`word_id` is required to be globally unique**.
#### MatchTable
* `table_id`: The unique ID of the match table.
* `match_table_type`: The type of the match table.
* `word_list`: The word list of the match table.
* `exemption_simple_match_type`: The type of the exemption simple match.
* `exemption_word_list`: The exemption word list of the match table.
For each match table, word matching is performed over the `word_list`, and exemption word matching is performed over the `exemption_word_list`. If the exemption word matching result is True, the word matching result will be False.
#### MatchTableType
* `Simple`: Supports simple multiple patterns matching with text normalization defined by `simple_match_type`.
* We offer transformation methods for text normalization, including `Fanjian`, `Normalize`, `PinYin` ยทยทยท.
* It can handle combination patterns and repeated times sensitive matching, delimited by `&` and `~`, such as `hello&world&hello` will match `hellohelloworld` and `worldhellohello`, but not `helloworld` due to the repeated times of `hello`.
* `Regex`: Supports regex patterns matching.
* `SimilarChar`: Supports similar character matching using regex.
* `["hello,hallo,hollo,hi", "word,world,wrd,๐", "!,?,~"]` will match `helloworld!`, `hollowrd?`, `hi๐~` ยทยทยท any combinations of the words split by `,` in the list.
* `Acrostic`: Supports acrostic matching using regex **(currently only supports Chinese and simple English sentences)**.
* `["h,e,l,l,o", "ไฝ ,ๅฅฝ"]` will match `hope, endures, love, lasts, onward.` and `ไฝ ็็ฌๅฎนๆธฉๆ, ๅฅฝๅฟๆ
ๅธธไผดใ`.
* `Regex`: Supports regex matching.
* `["h[aeiou]llo", "w[aeiou]rd"]` will match `hello`, `world`, `hillo`, `wurld` ยทยทยท any text that matches the regex in the list.
* `Similar`: Supports similar text matching based on distance and threshold.
* `Levenshtein`: Supports similar text matching based on Levenshtein distance.
* `DamerauLevenshtein`: Supports similar text matching based on Damerau-Levenshtein distance.
* `Indel`: Supports similar text matching based on Indel distance.
* `Jaro`: Supports similar text matching based on Jaro distance.
* `JaroWinkler`: Supports similar text matching based on Jaro-Winkler distance.
#### SimpleMatchType
* `None`: No transformation.
* `Fanjian`: Traditional Chinese to simplified Chinese transformation. Based on [FANJIAN](./str_conv/FANJIAN.txt).
* `ๅฆณๅฅฝ` -> `ไฝ ๅฅฝ`
* `็พโพ` -> `็ฐ่บซ`
* `Delete`: Delete all punctuation, special characters and white spaces.
* `hello, world!` -> `helloworld`
* `ใไฝ โทๅฅฝใ` -> `ไฝ ๅฅฝ`
* `Normalize`: Normalize all English character variations and number variations to basic characters. Based on [SYMBOL_NORM](./str_conv/SYMBOL-NORM.txt), [NORM](./str_conv/NORM.txt) and [NUM_NORM](./str_conv/NUM-NORM.txt).
* `โะโใ ร` -> `he11o`
* `โฦงใ` -> `123`
* `PinYin`: Convert all unicode Chinese characters to pinyin with boundaries. Based on [PINYIN](./str_conv/PINYIN.txt).
* `ไฝ ๅฅฝ` -> `โniโโhaoโ`
* `่ฅฟๅฎ` -> `โxiโโanโ`
* `PinYinChar`: Convert all unicode Chinese characters to pinyin without boundaries. Based on [PINYIN_CHAR](./str_conv/PINYIN-CHAR.txt).
* `ไฝ ๅฅฝ` -> `nihao`
* `่ฅฟๅฎ` -> `xian`
You can combine these transformations as needed. Pre-defined combinations like `DeleteNormalize` and `FanjianDeleteNormalize` are provided for convenience.
Avoid combining `PinYin` and `PinYinChar` due to that `PinYin` is a more limited version of `PinYinChar`, in some cases like `xian`, can be treat as two words `xi` and `an`, or only one word `xian`.
`Delete` is technologically a combination of `TextDelete` and `WordDelete`, we implement different delete methods for text and word. 'Cause we believe `CN_SPECIAL` and `EN_SPECIAL` are parts of the word, but not for text. For `text_process` and `reduce_text_process` functions, users should use `TextDelete` instead of `WordDelete`.
* `WordDelete`: Delete all patterns in `WHITE_SPACE`.
* `TextDelete`: Delete all patterns in [TEXT_DELETE](./str_conv/TEXT-DELETE.txt).
### Basic Example
Hereโs a basic example of how to use the `Matcher` struct for text matching:
```rust
use matcher_rs::{text_process, reduce_text_process, SimpleMatchType};
let result = text_process(SimpleMatchType::TextDelete, "ไฝ ๅฅฝ๏ผไธ็๏ผ");
let result = reduce_text_process(SimpleMatchType::FanjianDeleteNormalize, "ไฝ ๅฅฝ๏ผไธ็๏ผ");
```
```rust
use std::collections::HashMap;
use matcher_rs::{Matcher, MatchTableMap, MatchTable, MatchTableType, SimpleMatchType};
let match_table_map: MatchTableMap = HashMap::from_iter(vec![
(1, vec![MatchTable {
table_id: 1,
match_table_type: MatchTableType::Simple { simple_match_type: SimpleMatchType::FanjianDeleteNormalize},
word_list: vec!["example", "test"],
exemption_simple_match_type: SimpleMatchType::FanjianDeleteNormalize,
exemption_word_list: vec![],
}]),
]);
let matcher = Matcher::new(&match_table_map);
let text = "This is an example text.";
let results = matcher.word_match(text);
```
```rust
use std::collections::HashMap;
use matcher_rs::{SimpleMatchType, SimpleMatcher};
let mut simple_match_type_word_map = HashMap::default();
let mut simple_word_map = HashMap::default();
simple_word_map.insert(1, "ไฝ ๅฅฝ");
simple_word_map.insert(2, "ไธ็");
simple_match_type_word_map.insert(SimpleMatchType::Fanjian, simple_word_map);
let matcher = SimpleMatcher::new(&simple_match_type_word_map);
let text = "ไฝ ๅฅฝ๏ผไธ็๏ผ";
let results = matcher.process(text);
```
For more detailed usage examples, please refer to the [test.rs](./tests/test.rs) file.
## Feature Flags
* `prebuilt`: By enable prebuilt feature, we could boost process matcher build time, but with package size increasing.
* `runtime_build`: By enable runtime_build feature, we could build process matcher at runtime, but with build time increasing.
* `serde`: By enable serde feature, we could serialize and deserialize matcher and simple_matcher. With serde feature, AhoCorasick's prefilter is disabled, because I don't know how to serialize it correctly, which will lead to performance regression when the patterns size is small (say, less than 100).
Default feature is `prebuilt`, `prebuilt` and `runtime_build` can't be enabled at same time. If you want to make `Matcher` and `SimpleMatcher` serializable, you should enable `serde` feature.
## Benchmarks
Bench against pairs ([CN_WORD_LIST_100000](../data/word_list/cn/cn_words_100000.txt), [CN_HAYSTACK](../data/text/cn/่ฅฟๆธธ่ฎฐ.txt)) and ([EN_WORD_LIST_100000](../data/word_list/en/en_words_100000.txt), [EN_HAYSTACK](../data/text/en/sherlock.txt)). Word selection is totally random.
The `matcher_rs` library includes benchmarks to measure the performance of the matcher. You can find the benchmarks in the [bench.rs](./benches/bench.rs) file. To run the benchmarks, use the following command:
```shell
cargo bench
```
```
Current default simple match type: SimpleMatchType(None)
Current default simple word map size: 1000
Current default combined times: 2
Timer precision: 41 ns
bench fastest โ slowest โ median โ mean โ samples โ iters
โโ build_cn โ โ โ โ โ
โ โโ build_cn_by_combined_times โ โ โ โ โ
โ โ โโ 1 2.411 ms โ 3.148 ms โ 2.543 ms โ 2.542 ms โ 100 โ 100
โ โ โโ 2 5.268 ms โ 5.628 ms โ 5.308 ms โ 5.318 ms โ 100 โ 100
โ โ โโ 3 7.833 ms โ 8.757 ms โ 8.033 ms โ 8.082 ms โ 100 โ 100
โ โ โโ 4 10.36 ms โ 16.95 ms โ 10.75 ms โ 10.89 ms โ 100 โ 100
โ โ โฐโ 5 12.91 ms โ 14 ms โ 13.14 ms โ 13.2 ms โ 100 โ 100
โ โโ build_cn_by_multiple_simple_match_type 16.67 ms โ 75.17 ms โ 17.23 ms โ 18.19 ms โ 100 โ 100
โ โโ build_cn_by_simple_match_type โ โ โ โ โ
โ โ โโ "fanjian" 5.263 ms โ 6.504 ms โ 5.727 ms โ 5.719 ms โ 100 โ 100
โ โ โโ "fanjian_worddelete_textdelete_normalize" 5.688 ms โ 6.144 ms โ 5.751 ms โ 5.768 ms โ 100 โ 100
โ โ โโ "none" 5.229 ms โ 5.533 ms โ 5.287 ms โ 5.295 ms โ 100 โ 100
โ โ โโ "normalize" 5.081 ms โ 13.27 ms โ 5.251 ms โ 5.4 ms โ 100 โ 100
โ โ โโ "pinyin" 28.37 ms โ 40.86 ms โ 29.45 ms โ 29.54 ms โ 100 โ 100
โ โ โโ "pinyinchar" 15.52 ms โ 17.1 ms โ 15.75 ms โ 15.81 ms โ 100 โ 100
โ โ โโ "worddelete_textdelete" 5.3 ms โ 5.666 ms โ 5.359 ms โ 5.369 ms โ 100 โ 100
โ โ โฐโ "worddelete_textdelete_normalize" 5.281 ms โ 10.33 ms โ 5.416 ms โ 5.555 ms โ 100 โ 100
โ โฐโ build_cn_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 468.9 ยตs โ 630.7 ยตs โ 506.3 ยตs โ 509.7 ยตs โ 100 โ 100
โ โโ 1000 5.065 ms โ 6.205 ms โ 5.152 ms โ 5.249 ms โ 100 โ 100
โ โโ 10000 49.95 ms โ 61.21 ms โ 51.37 ms โ 51.78 ms โ 97 โ 97
โ โฐโ 50000 185.9 ms โ 205.1 ms โ 190.8 ms โ 192 ms โ 27 โ 27
โโ build_en โ โ โ โ โ
โ โโ build_en_by_combined_times โ โ โ โ โ
โ โ โโ 1 5.965 ms โ 6.952 ms โ 6.16 ms โ 6.177 ms โ 100 โ 100
โ โ โโ 2 13.53 ms โ 24.89 ms โ 14.08 ms โ 14.18 ms โ 100 โ 100
โ โ โโ 3 21.58 ms โ 22.98 ms โ 21.92 ms โ 21.99 ms โ 100 โ 100
โ โ โโ 4 29.43 ms โ 40.54 ms โ 30.19 ms โ 30.5 ms โ 100 โ 100
โ โ โฐโ 5 37.01 ms โ 50.59 ms โ 37.75 ms โ 37.96 ms โ 100 โ 100
โ โโ build_en_by_multiple_simple_match_type 16.26 ms โ 20.51 ms โ 16.34 ms โ 16.43 ms โ 100 โ 100
โ โโ build_en_by_simple_match_type โ โ โ โ โ
โ โ โโ "none" 12.61 ms โ 20.9 ms โ 13.04 ms โ 13.13 ms โ 100 โ 100
โ โ โโ "normalize" 11.87 ms โ 13.03 ms โ 12.33 ms โ 12.21 ms โ 100 โ 100
โ โ โโ "worddelete_textdelete" 12.41 ms โ 13.24 ms โ 12.78 ms โ 12.74 ms โ 100 โ 100
โ โ โฐโ "worddelete_textdelete_normalize" 12.6 ms โ 23.45 ms โ 12.96 ms โ 13.07 ms โ 100 โ 100
โ โฐโ build_en_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 821.4 ยตs โ 1.074 ms โ 880 ยตs โ 886.2 ยตs โ 100 โ 100
โ โโ 1000 12.82 ms โ 26.07 ms โ 13.3 ms โ 13.48 ms โ 100 โ 100
โ โโ 10000 164.8 ms โ 179 ms โ 168.7 ms โ 169.4 ms โ 30 โ 30
โ โฐโ 50000 732.9 ms โ 769.2 ms โ 744.8 ms โ 747.2 ms โ 7 โ 7
โโ search_cn โ โ โ โ โ
โ โโ search_cn_baseline โ โ โ โ โ
โ โ โโ 100 2.814 ms โ 3.043 ms โ 2.97 ms โ 2.953 ms โ 100 โ 100
โ โ โโ 1000 2.994 ms โ 3.434 ms โ 3.171 ms โ 3.146 ms โ 100 โ 100
โ โ โโ 10000 8.954 ms โ 9.901 ms โ 9.006 ms โ 9.053 ms โ 100 โ 100
โ โ โฐโ 50000 31.95 ms โ 47.99 ms โ 32.92 ms โ 33.28 ms โ 100 โ 100
โ โโ search_cn_by_combined_times โ โ โ โ โ
โ โ โโ 1 3.954 ms โ 4.253 ms โ 4.119 ms โ 4.112 ms โ 100 โ 100
โ โ โโ 2 5.733 ms โ 15.43 ms โ 6.134 ms โ 6.209 ms โ 100 โ 100
โ โ โโ 3 6.917 ms โ 7.764 ms โ 6.967 ms โ 6.985 ms โ 100 โ 100
โ โ โโ 4 6.596 ms โ 7.489 ms โ 6.649 ms โ 6.666 ms โ 100 โ 100
โ โ โฐโ 5 8.324 ms โ 9.099 ms โ 8.371 ms โ 8.39 ms โ 100 โ 100
โ โโ search_cn_by_multiple_simple_match_type 50.94 ms โ 66.2 ms โ 51.14 ms โ 51.88 ms โ 100 โ 100
โ โโ search_cn_by_simple_match_type โ โ โ โ โ
โ โ โโ "fanjian" 8.353 ms โ 8.783 ms โ 8.401 ms โ 8.413 ms โ 100 โ 100
โ โ โโ "fanjian_worddelete_textdelete_normalize" 19.95 ms โ 31.51 ms โ 20.31 ms โ 20.72 ms โ 100 โ 100
โ โ โโ "none" 4.908 ms โ 5.399 ms โ 5.108 ms โ 5.115 ms โ 100 โ 100
โ โ โโ "normalize" 9.632 ms โ 10.78 ms โ 9.677 ms โ 9.706 ms โ 100 โ 100
โ โ โโ "pinyin" 62.56 ms โ 79.62 ms โ 63.77 ms โ 65.14 ms โ 77 โ 77
โ โ โโ "pinyinchar" 54.22 ms โ 67.27 ms โ 55 ms โ 55.62 ms โ 90 โ 90
โ โ โโ "worddelete_textdelete" 13.13 ms โ 13.97 ms โ 13.17 ms โ 13.2 ms โ 100 โ 100
โ โ โฐโ "worddelete_textdelete_normalize" 17.27 ms โ 27.16 ms โ 18.46 ms โ 18.07 ms โ 100 โ 100
โ โฐโ search_cn_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 2.914 ms โ 3.151 ms โ 2.931 ms โ 2.937 ms โ 100 โ 100
โ โโ 1000 5.374 ms โ 5.699 ms โ 5.528 ms โ 5.525 ms โ 100 โ 100
โ โโ 10000 17.89 ms โ 27.38 ms โ 19.08 ms โ 18.94 ms โ 100 โ 100
โ โฐโ 50000 66.72 ms โ 81.68 ms โ 68.4 ms โ 69.01 ms โ 73 โ 73
โฐโ search_en โ โ โ โ โ
โโ search_en_baseline โ โ โ โ โ
โ โโ 100 233.6 ยตs โ 378.4 ยตs โ 249.8 ยตs โ 252.9 ยตs โ 100 โ 100
โ โโ 1000 241.7 ยตs โ 355.2 ยตs โ 261.3 ยตs โ 265.1 ยตs โ 100 โ 100
โ โโ 10000 861.4 ยตs โ 997.3 ยตs โ 927.5 ยตs โ 926.6 ยตs โ 100 โ 100
โ โฐโ 50000 864.6 ยตs โ 946.3 ยตs โ 926.4 ยตs โ 927.1 ยตs โ 100 โ 100
โโ search_en_by_combined_times โ โ โ โ โ
โ โโ 1 1.332 ms โ 1.55 ms โ 1.344 ms โ 1.351 ms โ 100 โ 100
โ โโ 2 2.176 ms โ 2.417 ms โ 2.187 ms โ 2.195 ms โ 100 โ 100
โ โโ 3 2.273 ms โ 2.601 ms โ 2.286 ms โ 2.293 ms โ 100 โ 100
โ โโ 4 2.401 ms โ 2.991 ms โ 2.559 ms โ 2.531 ms โ 100 โ 100
โ โฐโ 5 2.539 ms โ 2.982 ms โ 2.548 ms โ 2.557 ms โ 100 โ 100
โโ search_en_by_multiple_simple_match_type 9.411 ms โ 18.13 ms โ 9.461 ms โ 9.572 ms โ 100 โ 100
โโ search_en_by_simple_match_type โ โ โ โ โ
โ โโ "none" 2.042 ms โ 2.545 ms โ 2.121 ms โ 2.129 ms โ 100 โ 100
โ โโ "normalize" 2.589 ms โ 2.773 ms โ 2.609 ms โ 2.614 ms โ 100 โ 100
โ โโ "worddelete_textdelete" 5.161 ms โ 5.614 ms โ 5.316 ms โ 5.324 ms โ 100 โ 100
โ โฐโ "worddelete_textdelete_normalize" 5.647 ms โ 30.43 ms โ 5.98 ms โ 6.273 ms โ 100 โ 100
โฐโ search_en_by_simple_word_map_size โ โ โ โ โ
โโ 100 984.7 ยตs โ 1.166 ms โ 1.055 ms โ 1.041 ms โ 100 โ 100
โโ 1000 2.066 ms โ 2.272 ms โ 2.078 ms โ 2.086 ms โ 100 โ 100
โโ 10000 2.971 ms โ 4.241 ms โ 2.988 ms โ 3.01 ms โ 100 โ 100
โฐโ 50000 4.268 ms โ 6.721 ms โ 4.601 ms โ 4.705 ms โ 100 โ 100
```
## Contributing
Contributions to `matcher_rs` are welcome! If you find a bug or have a feature request, please open an issue on the GitHub repository. If you would like to contribute code, please fork the repository and submit a pull request.
## License
`matcher_rs` is licensed under the MIT OR Apache-2.0 license.
## More Information
For more details, visit the [GitHub repository](https://github.com/Lips7/Matcher).