# 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 built using `MatcherBuilder` and `MatchTableBuilder`.
* `SimpleMatcher`'s configuration is built using `SimpleMatcherBuilder`. For each `SimpleMatcher`, the added `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 matcher_rs::{MatcherBuilder, MatchTableBuilder, MatchTableType, ProcessType};
let table = MatchTableBuilder::new(1, MatchTableType::Simple { process_type: ProcessType::FanjianDeleteNormalize })
.add_words(["example", "test"])
.build();
let matcher = MatcherBuilder::new()
.add_table(1, table)
.build();
let text = "This is an example text.";
let results = matcher.word_match(text);
```
```rust
use matcher_rs::{ProcessType, SimpleMatcherBuilder};
let matcher = SimpleMatcherBuilder::new()
.add_word(ProcessType::Fanjian, 1, "ไฝ ๅฅฝ")
.add_word(ProcessType::Fanjian, 2, "ไธ็")
.build();
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.
* `dfa`: By enable dfa feature, we could use dfa to perform simple matching, but with significantly increasing memory consumption.
Default feature is `dfa`.
## 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: 10000
Current default combined times: 3
Timer precision: 41 ns
bench fastest โ slowest โ median โ mean โ samples โ iters
โโ build โ โ โ โ โ
โ โโ cn_by_combinations โ โ โ โ โ
โ โ โโ 1 7.761 ms โ 11.14 ms โ 8.053 ms โ 8.153 ms โ 100 โ 100
โ โ โโ 3 25.6 ms โ 59.3 ms โ 28.03 ms โ 29.63 ms โ 100 โ 100
โ โ โฐโ 5 44.68 ms โ 74.26 ms โ 47.95 ms โ 49.66 ms โ 100 โ 100
โ โโ cn_by_process_type โ โ โ โ โ
โ โ โโ "delete" 25.37 ms โ 45.72 ms โ 26.11 ms โ 26.57 ms โ 100 โ 100
โ โ โโ "fanjian" 25.69 ms โ 55.01 ms โ 27.2 ms โ 27.64 ms โ 100 โ 100
โ โ โโ "fanjian_delete_normalize" 25.96 ms โ 48.89 ms โ 27.3 ms โ 27.88 ms โ 100 โ 100
โ โ โฐโ "none" 25.94 ms โ 62.33 ms โ 28.24 ms โ 29.9 ms โ 100 โ 100
โ โโ cn_by_size โ โ โ โ โ
โ โ โโ 1000 2.261 ms โ 3.293 ms โ 2.311 ms โ 2.36 ms โ 100 โ 100
โ โ โโ 10000 25.48 ms โ 28.64 ms โ 25.91 ms โ 25.96 ms โ 100 โ 100
โ โ โฐโ 50000 105.3 ms โ 152.1 ms โ 109.2 ms โ 111.9 ms โ 45 โ 45
โ โโ en_by_combinations โ โ โ โ โ
โ โ โโ 1 9.651 ms โ 10.92 ms โ 9.956 ms โ 9.973 ms โ 100 โ 100
โ โ โโ 3 25.42 ms โ 40.48 ms โ 26.35 ms โ 26.62 ms โ 100 โ 100
โ โ โฐโ 5 43.95 ms โ 73.28 ms โ 46.61 ms โ 48.27 ms โ 100 โ 100
โ โโ en_by_process_type โ โ โ โ โ
โ โ โโ "delete" 24.87 ms โ 31.21 ms โ 25.66 ms โ 25.9 ms โ 100 โ 100
โ โ โโ "delete_normalize" 25.72 ms โ 52.05 ms โ 26.59 ms โ 27.05 ms โ 100 โ 100
โ โ โฐโ "none" 24.98 ms โ 41.02 ms โ 25.74 ms โ 26.04 ms โ 100 โ 100
โ โฐโ en_by_size โ โ โ โ โ
โ โโ 1000 2.443 ms โ 3.13 ms โ 2.56 ms โ 2.575 ms โ 100 โ 100
โ โโ 10000 25.07 ms โ 45.75 ms โ 25.94 ms โ 26.23 ms โ 100 โ 100
โ โฐโ 50000 120.6 ms โ 237.2 ms โ 126.1 ms โ 133.9 ms โ 38 โ 38
โโ search_match โ โ โ โ โ
โ โโ cn_by_combinations โ โ โ โ โ
โ โ โโ 1 1.063 ms โ 1.203 ms โ 1.08 ms โ 1.087 ms โ 100 โ 100
โ โ โโ 3 1.059 ms โ 1.147 ms โ 1.076 ms โ 1.079 ms โ 100 โ 100
โ โ โฐโ 5 1.066 ms โ 1.152 ms โ 1.09 ms โ 1.093 ms โ 100 โ 100
โ โโ cn_by_process_type โ โ โ โ โ
โ โ โโ "delete" 27.72 ms โ 41.91 ms โ 28.84 ms โ 29.35 ms โ 100 โ 100
โ โ โโ "fanjian" 18.27 ms โ 32.56 ms โ 19.08 ms โ 19.51 ms โ 100 โ 100
โ โ โโ "fanjian_delete_normalize" 46.26 ms โ 62.02 ms โ 47.74 ms โ 48.44 ms โ 100 โ 100
โ โ โฐโ "none" 16.23 ms โ 25.45 ms โ 17.66 ms โ 18.2 ms โ 100 โ 100
โ โโ cn_by_size โ โ โ โ โ
โ โ โโ 1000 4.043 ms โ 5.396 ms โ 4.145 ms โ 4.214 ms โ 100 โ 100
โ โ โโ 10000 16.21 ms โ 29.69 ms โ 17.21 ms โ 17.59 ms โ 100 โ 100
โ โ โฐโ 50000 73.82 ms โ 99.08 ms โ 78.3 ms โ 79.59 ms โ 63 โ 63
โ โโ en_by_combinations โ โ โ โ โ
โ โ โโ 1 1.291 ms โ 1.461 ms โ 1.313 ms โ 1.318 ms โ 100 โ 100
โ โ โโ 3 1.903 ms โ 2.698 ms โ 1.938 ms โ 1.971 ms โ 100 โ 100
โ โ โฐโ 5 2.461 ms โ 3.752 ms โ 2.649 ms โ 2.613 ms โ 100 โ 100
โ โโ en_by_process_type โ โ โ โ โ
โ โ โโ "delete" 6.257 ms โ 7.893 ms โ 6.38 ms โ 6.419 ms โ 100 โ 100
โ โ โโ "delete_normalize" 8.506 ms โ 16.98 ms โ 8.736 ms โ 8.926 ms โ 100 โ 100
โ โ โฐโ "none" 1.915 ms โ 3.54 ms โ 1.972 ms โ 2.048 ms โ 100 โ 100
โ โฐโ en_by_size โ โ โ โ โ
โ โโ 1000 1.058 ms โ 1.244 ms โ 1.081 ms โ 1.086 ms โ 100 โ 100
โ โโ 10000 1.912 ms โ 2.699 ms โ 1.955 ms โ 1.984 ms โ 100 โ 100
โ โฐโ 50000 4.652 ms โ 7.093 ms โ 5.15 ms โ 5.155 ms โ 100 โ 100
โฐโ search_no_match โ โ โ โ โ
โโ cn_by_combinations โ โ โ โ โ
โ โโ 1 736.7 ยตs โ 865.3 ยตs โ 761.8 ยตs โ 766.9 ยตs โ 100 โ 100
โ โโ 3 749.9 ยตs โ 818.6 ยตs โ 770.8 ยตs โ 774.1 ยตs โ 100 โ 100
โ โฐโ 5 737.8 ยตs โ 801.4 ยตs โ 755.4 ยตs โ 755.8 ยตs โ 100 โ 100
โโ cn_by_process_type โ โ โ โ โ
โ โโ "delete" 5.502 ms โ 5.986 ms โ 5.551 ms โ 5.57 ms โ 100 โ 100
โ โโ "fanjian" 1.33 ms โ 1.398 ms โ 1.348 ms โ 1.352 ms โ 100 โ 100
โ โโ "fanjian_delete_normalize" 9.571 ms โ 13.16 ms โ 9.693 ms โ 9.823 ms โ 100 โ 100
โ โฐโ "none" 311.4 ยตs โ 344 ยตs โ 318 ยตs โ 319.9 ยตs โ 100 โ 100
โโ cn_by_size โ โ โ โ โ
โ โโ 1000 307.4 ยตs โ 379.1 ยตs โ 319.1 ยตs โ 322.9 ยตs โ 100 โ 100
โ โโ 10000 308 ยตs โ 350.2 ยตs โ 318.3 ยตs โ 321.2 ยตs โ 100 โ 100
โ โฐโ 50000 315.7 ยตs โ 1.691 ms โ 333.2 ยตs โ 481.2 ยตs โ 100 โ 100
โโ en_by_combinations โ โ โ โ โ
โ โโ 1 725 ยตs โ 810.2 ยตs โ 741.7 ยตs โ 744.1 ยตs โ 100 โ 100
โ โโ 3 738.3 ยตs โ 828.4 ยตs โ 758.2 ยตs โ 764.3 ยตs โ 100 โ 100
โ โฐโ 5 727 ยตs โ 787.1 ยตs โ 739.6 ยตs โ 742.7 ยตs โ 100 โ 100
โโ en_by_process_type โ โ โ โ โ
โ โโ "delete" 3.816 ms โ 4.719 ms โ 3.869 ms โ 3.89 ms โ 100 โ 100
โ โโ "delete_normalize" 5.224 ms โ 5.965 ms โ 5.38 ms โ 5.416 ms โ 100 โ 100
โ โฐโ "none" 728.2 ยตs โ 776.1 ยตs โ 745.9 ยตs โ 746.8 ยตs โ 100 โ 100
โฐโ en_by_size โ โ โ โ โ
โโ 1000 729.3 ยตs โ 818.7 ยตs โ 743.9 ยตs โ 748.7 ยตs โ 100 โ 100
โโ 10000 743.1 ยตs โ 828.3 ยตs โ 763.1 ยตs โ 769.6 ยตs โ 100 โ 100
โฐโ 50000 731.1 ยตs โ 783.2 ยตs โ 743.4 ยตs โ 747.2 ยตs โ 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).