模糊匹配器

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 使用，这是一个模糊查找器。

浏览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 超过限制，它将回退到线性搜索。