Bitap

在Rust中实现Bitap算法，用于模糊字符串搜索。

如果你有一大堆文本要搜索，并且有一个要查找的子串，bitap可以高效地找到源文本中与搜索字符串最多相差k个编辑的距离的所有位置，其中“编辑”是以Levenshtein距离或最优字符串对齐距离来衡量的。这会有一些前期成本，但实际上运行时间是O(nk)，如果你需要的话，这是一个相当稳定的解决方案。

用法

编译一个Pattern，然后使用它来搜索。

use bitap::{Pattern,Match};

// Compile the pattern you're searching for.
let pattern = Pattern::new("wxrld")?;

// Run one of the search functions:
// - pattern.lev for levenshtein distance matching
// - pattern.osa for optimal string alignment distance matching
// The second parameter determines the maximum edit distance
// that you want to return matches for.
let max_distance = 1;
let matches = pattern.lev("hello world", max_distance);

// Horray!
assert_eq!(matches.next(), Some(Match{ distance: 1, end: 10 }));

限制

• 模式大小受限于系统字大小（usize），因此你无法搜索超过31/63个字符的内容。这是算法的根本限制。实际上，“Antidisestablishmentarianism”这个单词只有28个字符。

• Bitap可以告诉你匹配结束的位置，但不能告诉你匹配开始的位置。关于匹配高亮显示的部分将更详细地说明这一点。

• Unicode很奇怪。当想到“编辑距离”时，你通常认为它是“字符”。但Unicode码点并不映射到单个“字符”。一个字符可以是“a”或“ă̘̙̤̪̹̰͔͒̃̃͐̂͘”。在1字符/字符规则下，“alyx”实际上与“aléx”相差两个编辑（其中é是e加上̘̙̤̪̹̰͔̆͒̃̃͐̂͘），而你期望它只相差一个编辑。Pattern结构体就是这样工作的，其中char等于一个字符。如果你需要更细致的行为，你可以使用下面描述的迭代器适配器。你也可以对文本进行归一化，以去除额外的修饰，这可能是用户真正想要的。

适配器

Pattern 结构体处理了大多数位图（bitap）的用法；在 Unicode 文本中进行 Unicode 模式的模糊搜索。但它并不完美，位图本身可以推广到更广泛的问题领域。

幸运的是，位图的核心实际上可以以一种方式表示，这种方式不关心你是在处理码点、字符还是甚至核苷酸，我可以把所有这些顾虑推给那些关心它们的人！

关键洞察是，主要的算法是在模式掩码的迭代器上工作的。位图可以实现为一个迭代器适配器，它接收 Iterator<Item = usize> 并返回一个匹配项的迭代器。这就是顶层函数 find、levenshtein 和 optimal_string_alignment 所做的；你编写生成模式掩码迭代器的代码，它们找到匹配项。

静态版本

有几个迭代器适配器的静态版本，分别是 levenshtein_static 和 optimal_string_alignment_static。这是怎么回事？

根据 维基百科

在其开创性的论文中，Damerau 指出，超过 80% 的人类拼写错误都可以通过四种类型之一的一个错误来表达。

此外，我在思考模糊搜索的时候，也玩了很多 algolia，他们只允许最多两个错误。因此，允许最多两个错误可能是一个足够常见的案例，可以对其进行优化，通过避免分配，我们可以获得 ~15% 的更多性能！

匹配高亮显示

不幸的是，位图只能告诉你匹配结束的索引。当编辑距离为零时，匹配的开始是显而易见的 match.end - pattern_length + 1，但是有编辑的情况下是 +- match.distance。这使得完美精确高亮显示变得痛苦，但这里有一些对我有用的策略。