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 }));

限制

• 模式大小限制为系统字大小（mem::size_of::<usize>() - 1），因此你无法搜索超过31/63个字符的内容，具体取决于架构。这是算法的一个基本限制。这看起来似乎是一个非常糟糕的限制，但至少对于模糊搜索来说，你可能需要将查询拆分成标记并运行bitap n 次。Antidisestablishmentarianism毕竟只有28个字符。

• Bitap可以告诉你匹配的结束位置，但不能告诉你开始位置。关于匹配高亮的章节将更详细地介绍这一点。

• Unicode很奇怪。当你想到“编辑距离”时，你通常会从“字符”的角度去思考。但Unicode码点并不映射到单个“字符”。一个字符可能是“a”，也可能是“ă̘̙̤̪̹̰͔͒̃̃͐̂͘”。一个单个字符可能包含十个字符。根据每个字符一个字符的规则，“alyx”实际上距离“aléx”（其中é是e加上`́`）有两个编辑距离，而实际上你期望它只有一个。`Pattern`结构体在内部就是这样工作的，其中`char`等于一个字符。如果你需要更细致的行为，你可以使用下文所述的迭代器适配器。你也可以规范化文本以删除不必要的装饰，这可能是你的用户想要的。

适配器

`Pattern`结构体处理了`bitap`的大多数常见用法；在Unicode文本中搜索Unicode模式的模糊搜索。但它并不完美，`bitap`本身也可以推广到更广泛的范围的问题。

幸运的是，`bitap`的核心实际上可以用一种方式表示，它不关心你是否处理的是码点、图形符号，甚至是核苷酸，我可以把这些顾虑推给关心的人！

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

静态变体

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

根据维基百科

在其开创性的论文中，Damerau指出，所有人类拼写错误中有超过80%可以用四种类型中的一种单一错误来表示。

此外，我在思考模糊搜索时，对algolia进行了大量实验，并且他们只允许最多两个错误。所以允许最多两个错误可能是一个足够常见的案例，值得优化，我们可以通过避免分配来提高约15%的性能！

匹配高亮显示

遗憾的是，`bitap`只能告诉你匹配结束的索引。当编辑距离为零时，匹配的起始点是显而易见的`match.end - pattern_length + 1`，但是当有编辑时，它是`+- match.distance`。这使得完全准确的高亮显示变得痛苦，但这里有一些对我有效的方法。