# 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 is 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](./str_conv/PINYIN.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 special characters are parts of the word, users put them in words deliberately, 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 smt_word_map = HashMap::new();
let mut simple_word_map = HashMap::new();
simple_word_map.insert(1, "ไฝ ๅฅฝ");
simple_word_map.insert(2, "ไธ็");
smt_word_map.insert(SimpleMatchType::Fanjian, simple_word_map);
let matcher = SimpleMatcher::new(&smt_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).
* `dfa`: By enable dfa feature, we could use dfa to perform simple matching, but with significantly incresaing memory consumption.
Default feature is `prebuilt` and `dfa`, `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.468 ms โ 3.355 ms โ 2.506 ms โ 2.536 ms โ 100 โ 100
โ โ โโ 2 5.303 ms โ 5.765 ms โ 5.402 ms โ 5.41 ms โ 100 โ 100
โ โ โโ 3 7.912 ms โ 10.16 ms โ 7.986 ms โ 8.081 ms โ 100 โ 100
โ โ โโ 4 10.59 ms โ 11.31 ms โ 10.73 ms โ 10.75 ms โ 100 โ 100
โ โ โฐโ 5 13.03 ms โ 14.1 ms โ 13.13 ms โ 13.21 ms โ 100 โ 100
โ โโ build_cn_by_multiple_simple_match_type 26.63 ms โ 40.81 ms โ 26.99 ms โ 27.23 ms โ 100 โ 100
โ โโ build_cn_by_simple_match_type โ โ โ โ โ
โ โ โโ "fanjian" 5.296 ms โ 6.12 ms โ 5.348 ms โ 5.398 ms โ 100 โ 100
โ โ โโ "fanjian_worddelete_textdelete_normalize" 5.43 ms โ 5.937 ms โ 5.47 ms โ 5.491 ms โ 100 โ 100
โ โ โโ "none" 5.268 ms โ 5.667 ms โ 5.375 ms โ 5.379 ms โ 100 โ 100
โ โ โโ "normalize" 5.373 ms โ 5.827 ms โ 5.423 ms โ 5.437 ms โ 100 โ 100
โ โ โโ "pinyin" 16.02 ms โ 24.52 ms โ 16.15 ms โ 16.34 ms โ 100 โ 100
โ โ โโ "pinyinchar" 15.81 ms โ 41.81 ms โ 16.29 ms โ 16.99 ms โ 100 โ 100
โ โ โโ "worddelete_textdelete" 5.291 ms โ 6.192 ms โ 5.409 ms โ 5.556 ms โ 100 โ 100
โ โ โฐโ "worddelete_textdelete_normalize" 5.38 ms โ 6.311 ms โ 5.897 ms โ 5.866 ms โ 100 โ 100
โ โฐโ build_cn_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 501.2 ยตs โ 838.9 ยตs โ 545.2 ยตs โ 559.5 ยตs โ 100 โ 100
โ โโ 1000 5.383 ms โ 18.63 ms โ 5.669 ms โ 5.88 ms โ 100 โ 100
โ โโ 10000 49.97 ms โ 99.73 ms โ 53.03 ms โ 54.13 ms โ 93 โ 93
โ โฐโ 50000 194.1 ms โ 366.2 ms โ 204.9 ms โ 212.6 ms โ 24 โ 24
โโ build_en โ โ โ โ โ
โ โโ build_en_by_combined_times โ โ โ โ โ
โ โ โโ 1 5.43 ms โ 6.427 ms โ 5.84 ms โ 5.907 ms โ 100 โ 100
โ โ โโ 2 12.9 ms โ 21.5 ms โ 13.6 ms โ 13.83 ms โ 100 โ 100
โ โ โโ 3 21.99 ms โ 24.19 ms โ 22.89 ms โ 22.8 ms โ 100 โ 100
โ โ โโ 4 29.3 ms โ 50.2 ms โ 30.84 ms โ 31.27 ms โ 100 โ 100
โ โ โฐโ 5 38.12 ms โ 40.88 ms โ 38.44 ms โ 38.58 ms โ 100 โ 100
โ โโ build_en_by_multiple_simple_match_type 16.43 ms โ 19 ms โ 16.79 ms โ 16.95 ms โ 100 โ 100
โ โโ build_en_by_simple_match_type โ โ โ โ โ
โ โ โโ "none" 13.97 ms โ 15.1 ms โ 14.56 ms โ 14.58 ms โ 100 โ 100
โ โ โโ "normalize" 12.35 ms โ 17.97 ms โ 13.05 ms โ 13.13 ms โ 100 โ 100
โ โ โโ "worddelete_textdelete" 13.5 ms โ 14.87 ms โ 13.96 ms โ 13.97 ms โ 100 โ 100
โ โ โฐโ "worddelete_textdelete_normalize" 11.83 ms โ 13.31 ms โ 12.46 ms โ 12.54 ms โ 100 โ 100
โ โฐโ build_en_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 848.1 ยตs โ 1.286 ms โ 925.4 ยตs โ 929 ยตs โ 100 โ 100
โ โโ 1000 12.57 ms โ 16.46 ms โ 13.38 ms โ 13.38 ms โ 100 โ 100
โ โโ 10000 178.1 ms โ 192.3 ms โ 182.2 ms โ 183.7 ms โ 28 โ 28
โ โฐโ 50000 743.3 ms โ 884.1 ms โ 752.2 ms โ 776.2 ms โ 7 โ 7
โโ search_cn โ โ โ โ โ
โ โโ search_cn_baseline โ โ โ โ โ
โ โ โโ 100 2.907 ms โ 11.87 ms โ 3.068 ms โ 3.359 ms โ 100 โ 100
โ โ โโ 1000 2.99 ms โ 3.422 ms โ 3.006 ms โ 3.033 ms โ 100 โ 100
โ โ โโ 10000 5.197 ms โ 5.801 ms โ 5.269 ms โ 5.294 ms โ 100 โ 100
โ โ โฐโ 50000 12.44 ms โ 16.52 ms โ 14.2 ms โ 13.89 ms โ 100 โ 100
โ โโ search_cn_by_combined_times โ โ โ โ โ
โ โ โโ 1 3.702 ms โ 4.091 ms โ 3.728 ms โ 3.749 ms โ 100 โ 100
โ โ โโ 2 4.442 ms โ 4.826 ms โ 4.458 ms โ 4.467 ms โ 100 โ 100
โ โ โโ 3 5.054 ms โ 5.595 ms โ 5.078 ms โ 5.093 ms โ 100 โ 100
โ โ โโ 4 6.136 ms โ 6.777 ms โ 6.159 ms โ 6.177 ms โ 100 โ 100
โ โ โฐโ 5 6.235 ms โ 11.38 ms โ 6.396 ms โ 6.51 ms โ 100 โ 100
โ โโ search_cn_by_multiple_simple_match_type 64.81 ms โ 80.83 ms โ 66.49 ms โ 66.75 ms โ 100 โ 100
โ โโ search_cn_by_simple_match_type โ โ โ โ โ
โ โ โโ "fanjian" 6.781 ms โ 7.486 ms โ 6.841 ms โ 6.927 ms โ 100 โ 100
โ โ โโ "fanjian_worddelete_textdelete_normalize" 21.47 ms โ 45.61 ms โ 21.82 ms โ 22.33 ms โ 100 โ 100
โ โ โโ "none" 4.684 ms โ 5.198 ms โ 4.705 ms โ 4.731 ms โ 100 โ 100
โ โ โโ "normalize" 14.62 ms โ 15.81 ms โ 15.5 ms โ 15.28 ms โ 100 โ 100
โ โ โโ "pinyin" 57.98 ms โ 63.66 ms โ 60.31 ms โ 59.92 ms โ 84 โ 84
โ โ โโ "pinyinchar" 63.8 ms โ 74.02 ms โ 65.47 ms โ 66.22 ms โ 76 โ 76
โ โ โโ "worddelete_textdelete" 13.2 ms โ 14.62 ms โ 13.43 ms โ 13.65 ms โ 100 โ 100
โ โ โฐโ "worddelete_textdelete_normalize" 18.97 ms โ 21.06 ms โ 19.73 ms โ 19.83 ms โ 100 โ 100
โ โฐโ search_cn_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 3.031 ms โ 3.491 ms โ 3.082 ms โ 3.104 ms โ 100 โ 100
โ โโ 1000 4.793 ms โ 5.205 ms โ 4.997 ms โ 5.001 ms โ 100 โ 100
โ โโ 10000 10.12 ms โ 12.74 ms โ 10.7 ms โ 10.66 ms โ 100 โ 100
โ โฐโ 50000 21.12 ms โ 27.96 ms โ 21.77 ms โ 23.13 ms โ 100 โ 100
โฐโ search_en โ โ โ โ โ
โโ search_en_baseline โ โ โ โ โ
โ โโ 100 328.3 ยตs โ 1.576 ms โ 343.1 ยตs โ 364.5 ยตs โ 100 โ 100
โ โโ 1000 343.6 ยตs โ 472.4 ยตs โ 369.9 ยตs โ 369.1 ยตs โ 100 โ 100
โ โโ 10000 1.169 ms โ 1.248 ms โ 1.197 ms โ 1.199 ms โ 100 โ 100
โ โฐโ 50000 1.193 ms โ 1.304 ms โ 1.199 ms โ 1.205 ms โ 100 โ 100
โโ search_en_by_combined_times โ โ โ โ โ
โ โโ 1 1.682 ms โ 4.053 ms โ 1.692 ms โ 1.727 ms โ 100 โ 100
โ โโ 2 2.481 ms โ 2.682 ms โ 2.502 ms โ 2.506 ms โ 100 โ 100
โ โโ 3 2.585 ms โ 2.979 ms โ 2.678 ms โ 2.69 ms โ 100 โ 100
โ โโ 4 2.654 ms โ 3.265 ms โ 2.761 ms โ 2.764 ms โ 100 โ 100
โ โฐโ 5 2.74 ms โ 3.242 ms โ 2.752 ms โ 2.761 ms โ 100 โ 100
โโ search_en_by_multiple_simple_match_type 9.173 ms โ 10.27 ms โ 9.351 ms โ 9.481 ms โ 100 โ 100
โโ search_en_by_simple_match_type โ โ โ โ โ
โ โโ "none" 1.99 ms โ 2.286 ms โ 2.006 ms โ 2.049 ms โ 100 โ 100
โ โโ "normalize" 3.992 ms โ 4.064 ms โ 4.009 ms โ 4.012 ms โ 100 โ 100
โ โโ "worddelete_textdelete" 6.198 ms โ 7.005 ms โ 6.225 ms โ 6.253 ms โ 100 โ 100
โ โฐโ "worddelete_textdelete_normalize" 10.51 ms โ 32.63 ms โ 11.1 ms โ 11.41 ms โ 100 โ 100
โฐโ search_en_by_simple_word_map_size โ โ โ โ โ
โโ 100 1.384 ms โ 1.616 ms โ 1.458 ms โ 1.471 ms โ 100 โ 100
โโ 1000 2.395 ms โ 2.587 ms โ 2.427 ms โ 2.432 ms โ 100 โ 100
โโ 10000 3.091 ms โ 4.291 ms โ 3.113 ms โ 3.127 ms โ 100 โ 100
โฐโ 50000 3.668 ms โ 5.738 ms โ 3.831 ms โ 3.853 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).