editdistancek

此库计算两个字符串之间的Levenshtein编辑距离。编辑距离表示将一个字符串转换为另一个字符串所需的最小编辑次数。

我们的方法受到Ukkonen、Landau、Myers和Schmidt算法的启发。这些策略提供了计算编辑距离的高效方法。

该算法的运行时间为O(d*min(n,m))，期望运行时间为O(d^2 + n)。在这里，'d'代表两个字符串之间的编辑距离，而'n'和'm'分别代表这些字符串的长度。这种高效的运行时间确保了算法即使在较长的字符串上也能保持高性能。

动机

此库的主要目标是设计一个快速解决方案来解决编辑距离问题的有界版本。具体来说，它旨在处理给定一个阈值'k'的情况下，如果'd'小于或等于'k'，则返回编辑距离'd'。否则，表示距离超过'k'。这种方法解决了经典编辑距离算法的典型缺点，即在这些情况下通常效率低下。

此库的“有界”特性使其特别适用于存在预定义的可接受差异阈值的场景。这可能在对时间敏感的应用程序或处理非常大的字符串时有益，在这些情况下，计算完整的Levenshtein距离可能是计算上不可行的。

备注：editdistancek中的'k'指的是算法的上限。在实际情况中，这意味着算法只计算Levenshtein编辑距离到这个'k'值。

安装

添加到Cargo.toml

[dependecies]
editdistancek = "1.*"

使用方法

edit_distance("kitten".as_bytes(), "sitting".as_bytes()); // => 3
edit_distance_bounded("kitten".as_bytes(), "sitting".as_bytes(), 3); // => Some(3)
edit_distance_bounded("kitten".as_bytes(), "sitting".as_bytes(), 2); // => None

许可证

MIT许可证