# Matcher
A high-performance matcher designed to solve **LOGICAL** and **TEXT VARIATIONS** problems in word matching, implemented in Rust.
For detailed implementation, see the [Design Document](../DESIGN.md).
## Features
- **Multiple Matching Methods**:
- Simple Word Matching
- Regex-Based Matching
- Similarity-Based Matching
- **Text Transformation**:
- **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 `SimpleTable = HashMap<ProcessType, HashMap<u32, &str>>` type, the value `HashMap<u32, &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_process_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 `process_type`.
* 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.
#### ProcessType
* `None`: No transformation.
* `Fanjian`: Traditional Chinese to simplified Chinese transformation. Based on [FANJIAN](./process_map/FANJIAN.txt).
* `ๅฆณๅฅฝ` -> `ไฝ ๅฅฝ`
* `็พโพ` -> `็ฐ่บซ`
* `Delete`: Delete all punctuation, special characters and white spaces. Based on [TEXT_DELETE](./process_map/TEXT-DELETE.txt) and `WHITE_SPACE`.
* `hello, world!` -> `helloworld`
* `ใไฝ โทๅฅฝใ` -> `ไฝ ๅฅฝ`
* `Normalize`: Normalize all English character variations and number variations to basic characters. Based on [NORM](./process_map/NORM.txt) and [NUM_NORM](./process_map/NUM-NORM.txt).
* `โะโใ ร` -> `he11o`
* `โฦงใ` -> `123`
* `PinYin`: Convert all unicode Chinese characters to pinyin with boundaries. Based on [PINYIN](./process_map/PINYIN.txt).
* `ไฝ ๅฅฝ` -> ` ni hao `
* `่ฅฟๅฎ` -> ` xi an `
* `PinYinChar`: Convert all unicode Chinese characters to pinyin without boundaries. Based on [PINYIN](./process_map/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`.
### 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, ProcessType};
let result = text_process(ProcessType::Delete, "ไฝ ๅฅฝ๏ผไธ็๏ผ");
let result = reduce_text_process(ProcessType::FanjianDeleteNormalize, "ไฝ ๅฅฝ๏ผไธ็๏ผ");
```
```rust
use std::collections::HashMap;
use matcher_rs::{Matcher, MatchTableMap, MatchTable, MatchTableType, ProcessType};
let match_table_map: MatchTableMap = HashMap::from_iter(vec![
(1, vec![MatchTable {
table_id: 1,
match_table_type: MatchTableType::Simple { process_type: ProcessType::FanjianDeleteNormalize},
word_list: vec!["example", "test"],
exemption_process_type: ProcessType::None,
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::{ProcessType, SimpleMatcher};
let mut simple_table = HashMap::new();
let mut simple_word_map = HashMap::new();
simple_word_map.insert(1, "ไฝ ๅฅฝ");
simple_word_map.insert(2, "ไธ็");
simple_table.insert(ProcessType::Fanjian, simple_word_map);
let matcher = SimpleMatcher::new(&simple_table);
let text = "ไฝ ๅฅฝ๏ผไธ็๏ผ";
let results = matcher.process(text);
```
For more detailed usage examples, please refer to the [test.rs](./tests/test.rs) file.
## Feature Flags
* `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 increasing memory consumption.
Default feature is `dfa`. 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: ProcessType(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.421 ms โ 3.108 ms โ 2.433 ms โ 2.468 ms โ 100 โ 100
โ โ โโ 2 4.98 ms โ 5.647 ms โ 5.047 ms โ 5.073 ms โ 100 โ 100
โ โ โโ 3 7.651 ms โ 10.03 ms โ 7.802 ms โ 7.947 ms โ 100 โ 100
โ โ โโ 4 10.23 ms โ 12.06 ms โ 10.5 ms โ 10.61 ms โ 100 โ 100
โ โ โฐโ 5 12.93 ms โ 14.1 ms โ 13.15 ms โ 13.24 ms โ 100 โ 100
โ โโ build_cn_by_multiple_process_type 25.3 ms โ 59.86 ms โ 26 ms โ 26.53 ms โ 100 โ 100
โ โโ build_cn_by_process_type โ โ โ โ โ
โ โ โโ "delete" 5.053 ms โ 5.439 ms โ 5.176 ms โ 5.191 ms โ 100 โ 100
โ โ โโ "delete_normalize" 4.962 ms โ 5.768 ms โ 5.069 ms โ 5.1 ms โ 100 โ 100
โ โ โโ "fanjian" 5.109 ms โ 8.929 ms โ 5.19 ms โ 5.366 ms โ 100 โ 100
โ โ โโ "fanjian_delete_normalize" 4.987 ms โ 8.449 ms โ 5.26 ms โ 5.424 ms โ 100 โ 100
โ โ โโ "none" 5.03 ms โ 14.95 ms โ 5.159 ms โ 5.353 ms โ 100 โ 100
โ โ โโ "normalize" 5.039 ms โ 5.872 ms โ 5.214 ms โ 5.247 ms โ 100 โ 100
โ โ โโ "pinyin" 6.722 ms โ 14.46 ms โ 7.347 ms โ 7.344 ms โ 100 โ 100
โ โ โฐโ "pinyinchar" 6.603 ms โ 9.37 ms โ 7.147 ms โ 7.197 ms โ 100 โ 100
โ โฐโ build_cn_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 471.7 ยตs โ 681.7 ยตs โ 501.9 ยตs โ 512.3 ยตs โ 100 โ 100
โ โโ 1000 5.186 ms โ 5.858 ms โ 5.292 ms โ 5.321 ms โ 100 โ 100
โ โโ 10000 47.09 ms โ 51.62 ms โ 47.4 ms โ 47.77 ms โ 100 โ 100
โ โฐโ 50000 180.3 ms โ 194.4 ms โ 185.7 ms โ 186.1 ms โ 27 โ 27
โโ build_en โ โ โ โ โ
โ โโ build_en_by_combined_times โ โ โ โ โ
โ โ โโ 1 5.629 ms โ 6.387 ms โ 5.733 ms โ 5.759 ms โ 100 โ 100
โ โ โโ 2 13.33 ms โ 17.14 ms โ 13.51 ms โ 13.55 ms โ 100 โ 100
โ โ โโ 3 19.83 ms โ 23.14 ms โ 20.85 ms โ 20.85 ms โ 100 โ 100
โ โ โโ 4 27.55 ms โ 30.19 ms โ 27.73 ms โ 27.8 ms โ 100 โ 100
โ โ โฐโ 5 35.21 ms โ 37.18 ms โ 35.55 ms โ 35.6 ms โ 100 โ 100
โ โโ build_en_by_multiple_process_type 15.21 ms โ 16.72 ms โ 15.8 ms โ 15.79 ms โ 100 โ 100
โ โโ build_en_by_process_type โ โ โ โ โ
โ โ โโ "delete" 12.63 ms โ 26.19 ms โ 13.2 ms โ 13.32 ms โ 100 โ 100
โ โ โโ "delete_normalize" 11.76 ms โ 12.68 ms โ 11.94 ms โ 11.95 ms โ 100 โ 100
โ โ โโ "none" 12.21 ms โ 13.52 ms โ 12.67 ms โ 12.71 ms โ 100 โ 100
โ โ โฐโ "normalize" 11.45 ms โ 12.09 ms โ 11.59 ms โ 11.61 ms โ 100 โ 100
โ โฐโ build_en_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 820 ยตs โ 1.184 ms โ 830.6 ยตs โ 851.1 ยตs โ 100 โ 100
โ โโ 1000 13 ms โ 14.52 ms โ 13.65 ms โ 13.62 ms โ 100 โ 100
โ โโ 10000 151.4 ms โ 169.1 ms โ 157.5 ms โ 157.6 ms โ 32 โ 32
โ โฐโ 50000 640.3 ms โ 677.1 ms โ 655 ms โ 655.3 ms โ 8 โ 8
โโ search_cn โ โ โ โ โ
โ โโ search_cn_baseline โ โ โ โ โ
โ โ โโ 100 2.904 ms โ 7.824 ms โ 2.927 ms โ 2.986 ms โ 100 โ 100
โ โ โโ 1000 3.046 ms โ 3.81 ms โ 3.066 ms โ 3.095 ms โ 100 โ 100
โ โ โโ 10000 7.651 ms โ 8.541 ms โ 7.77 ms โ 7.854 ms โ 100 โ 100
โ โ โฐโ 50000 26.67 ms โ 47.51 ms โ 28.74 ms โ 30.15 ms โ 100 โ 100
โ โโ search_cn_by_combined_times โ โ โ โ โ
โ โ โโ 1 3.967 ms โ 4.308 ms โ 4.031 ms โ 4.039 ms โ 100 โ 100
โ โ โโ 2 5.201 ms โ 5.742 ms โ 5.246 ms โ 5.264 ms โ 100 โ 100
โ โ โโ 3 6.405 ms โ 7.174 ms โ 6.442 ms โ 6.47 ms โ 100 โ 100
โ โ โโ 4 7.012 ms โ 7.671 ms โ 7.039 ms โ 7.067 ms โ 100 โ 100
โ โ โฐโ 5 8.471 ms โ 9.027 ms โ 8.606 ms โ 8.621 ms โ 100 โ 100
โ โโ search_cn_by_multiple_process_type 61.42 ms โ 92.44 ms โ 64.06 ms โ 65.2 ms โ 100 โ 100
โ โโ search_cn_by_process_type โ โ โ โ โ
โ โ โโ "delete" 14.44 ms โ 15.15 ms โ 14.59 ms โ 14.59 ms โ 100 โ 100
โ โ โโ "delete_normalize" 20.58 ms โ 21.86 ms โ 21.19 ms โ 21.08 ms โ 100 โ 100
โ โ โโ "fanjian" 6.902 ms โ 7.653 ms โ 7.232 ms โ 7.179 ms โ 100 โ 100
โ โ โโ "fanjian_delete_normalize" 21.72 ms โ 23.12 ms โ 21.98 ms โ 22.11 ms โ 100 โ 100
โ โ โโ "none" 5.013 ms โ 5.628 ms โ 5.053 ms โ 5.073 ms โ 100 โ 100
โ โ โโ "normalize" 15.25 ms โ 16.69 ms โ 15.44 ms โ 15.62 ms โ 100 โ 100
โ โ โโ "pinyin" 41.1 ms โ 45.53 ms โ 43.78 ms โ 43.21 ms โ 100 โ 100
โ โ โฐโ "pinyinchar" 42.93 ms โ 48.92 ms โ 45.06 ms โ 44.83 ms โ 100 โ 100
โ โฐโ search_cn_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 3.205 ms โ 3.498 ms โ 3.242 ms โ 3.268 ms โ 100 โ 100
โ โโ 1000 5.057 ms โ 5.674 ms โ 5.273 ms โ 5.277 ms โ 100 โ 100
โ โโ 10000 16.31 ms โ 19.4 ms โ 17.24 ms โ 17.12 ms โ 100 โ 100
โ โฐโ 50000 53.87 ms โ 93.62 ms โ 58.71 ms โ 62.27 ms โ 81 โ 81
โโ search_en โ โ โ โ โ
โ โโ search_en_baseline โ โ โ โ โ
โ โ โโ 100 353.9 ยตs โ 471.7 ยตs โ 376.6 ยตs โ 381.7 ยตs โ 100 โ 100
โ โ โโ 1000 369 ยตs โ 452.2 ยตs โ 389.1 ยตs โ 393.8 ยตs โ 100 โ 100
โ โ โโ 10000 1.027 ms โ 1.06 ms โ 1.034 ms โ 1.035 ms โ 100 โ 100
โ โ โฐโ 50000 1.004 ms โ 1.055 ms โ 1.016 ms โ 1.018 ms โ 100 โ 100
โ โโ search_en_by_combined_times โ โ โ โ โ
โ โ โโ 1 1.788 ms โ 4.898 ms โ 1.915 ms โ 1.94 ms โ 100 โ 100
โ โ โโ 2 2.477 ms โ 2.747 ms โ 2.489 ms โ 2.494 ms โ 100 โ 100
โ โ โโ 3 2.792 ms โ 3.142 ms โ 2.805 ms โ 2.813 ms โ 100 โ 100
โ โ โโ 4 2.691 ms โ 3.115 ms โ 2.711 ms โ 2.717 ms โ 100 โ 100
โ โ โฐโ 5 2.786 ms โ 3.342 ms โ 2.803 ms โ 2.824 ms โ 100 โ 100
โ โโ search_en_by_multiple_process_type 10.12 ms โ 11.85 ms โ 10.76 ms โ 10.56 ms โ 100 โ 100
โ โโ search_en_by_process_type โ โ โ โ โ
โ โ โโ "delete" 7.104 ms โ 13.92 ms โ 7.145 ms โ 7.235 ms โ 100 โ 100
โ โ โโ "delete_normalize" 8.588 ms โ 9.469 ms โ 8.71 ms โ 8.848 ms โ 100 โ 100
โ โ โโ "none" 2.436 ms โ 2.711 ms โ 2.456 ms โ 2.466 ms โ 100 โ 100
โ โ โฐโ "normalize" 4.047 ms โ 4.338 ms โ 4.07 ms โ 4.076 ms โ 100 โ 100
โ โฐโ search_en_by_simple_word_map_size โ โ โ โ โ
โ โโ 100 1.355 ms โ 3.969 ms โ 1.429 ms โ 1.483 ms โ 100 โ 100
โ โโ 1000 2.064 ms โ 2.279 ms โ 2.077 ms โ 2.084 ms โ 100 โ 100
โ โโ 10000 3.381 ms โ 4.793 ms โ 3.396 ms โ 3.415 ms โ 100 โ 100
โ โฐโ 50000 4.561 ms โ 6.879 ms โ 4.659 ms โ 4.824 ms โ 100 โ 100
โฐโ single_line โ โ โ โ โ
โโ search_cn_single_line โ โ โ โ โ
โ โโ 100 252.2 ns โ 426.8 ns โ 262.7 ns โ 271.7 ns โ 100 โ 1600
โ โโ 1000 309.6 ns โ 338.2 ns โ 317.4 ns โ 317.5 ns โ 100 โ 1600
โ โโ 10000 540.7 ns โ 10.04 ยตs โ 624.7 ns โ 725.5 ns โ 100 โ 100
โ โฐโ 50000 1.29 ยตs โ 43.45 ยตs โ 1.374 ยตs โ 1.848 ยตs โ 100 โ 100
โฐโ search_en_single_line โ โ โ โ โ
โโ 100 56.04 ns โ 58.64 ns โ 57.01 ns โ 56.92 ns โ 100 โ 12800
โโ 1000 56.69 ns โ 68.4 ns โ 57.99 ns โ 58.17 ns โ 100 โ 12800
โโ 10000 374.7 ns โ 5.291 ยตs โ 457.7 ns โ 512.6 ns โ 100 โ 100
โฐโ 50000 457.7 ns โ 16.99 ยตs โ 540.7 ns โ 701.9 ns โ 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).