模糊匹配器

Rust 中的模糊匹配算法！

用法

在您的 Cargo.toml 中添加以下内容

[dependencies]
fuzzy-matcher = "*"

以下是一些代码示例

use fuzzy_matcher::FuzzyMatcher;
use fuzzy_matcher::skim::SkimMatcherV2;

let matcher = SkimMatcherV2::default();
assert_eq!(None, matcher.fuzzy_match("abc", "abx"));
assert!(matcher.fuzzy_match("axbycz", "abc").is_some());
assert!(matcher.fuzzy_match("axbycz", "xyz").is_some());

let (score, indices) = matcher.fuzzy_indices("axbycz", "abc").unwrap();
assert_eq!(indices, [0, 2, 4]);

• fuzzy_match 只返回分数，而 fuzzy_indices 返回匹配的索引。
• 两个函数如果模式不匹配，都返回 None。
• 分数越高越好。

更多示例

echo "axbycz" | cargo run --example fz "abc" 然后检查发生了什么。

关于算法

浏览

浏览当前由 skim 使用， skim 是一个模糊查找器。

浏览 V2

• 与 fzf v2 类似，该算法基于 Smith-Waterman 算法，通常用于 DNA 序列比对。
• 有关更多详细信息，请参阅 https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/gaps.pdf
• 时间复杂度为 O(mn)，其中 m, n 分别是模式和输入行的长度。
• 对于 fuzzy_indices，空间复杂度为 O(mn)，对于 fuzzy_match，空间复杂度为 O(2n)，它将压缩动态规划的表。
• V2 匹配器有一个选项可以设置分数矩阵的最大元素，如果 m*n 超过限制，它将回退到线性搜索。