algorithm - 最佳对齐的字符串相似度

Question

算法的预期行为

我有两个字符串a，b并且a是较短的字符串。我想找到与b具有最大相似性的子字符串a。子字符串必须是 of len(a)，或者必须放在 的末尾b。例如对于以下两个字符串：

a = "aa"
b = "bbaba"

b 的可能子串是

"bb"
"ba"
"ab"
"ba"
"a"
""

编辑距离定义为插入和删除的数量。替换是不可能的（必须使用插入+删除代替）。两个字符串之间的相似度根据以下等式计算：norm = 1 - distance / (len(a) + len(substring)). 因此，上面的子字符串将提供以下结果：

"bb" -> 2 DEL + 2 INS -> 1 - 4 / 4 = 0
"ba" -> 1 DEL + 1 INS -> 1 - 2 / 4 = 0.5
"ab" -> 1 DEL + 1 INS -> 1 - 2 / 4 = 0.5
"ba" -> 1 DEL + 1 INS -> 1 - 2 / 4 = 0.5
"a"  ->         1 INS -> 1 - 1 / 3 = 0.66
""   ->         2 INS -> 1 - 2 / 2 = 0

所以算法应该返回 0.66。

不同的实现

Python 库 FuzzyWuzzy 以fuzz.partial_ratio. 它分两步计算比率：

1. 使用 difflib.SequenceMatcher.get_matching_blocks 在较长序列中搜索匹配的子序列

2. 从匹配的子序列开始计算 len(shorter_string) 的子字符串的比率并返回最大比率

这真的很慢，所以它在可用时使用 python-Levenshtein 进行这种相似度计算。这会根据 Levenshtein 距离执行相同的计算，但速度更快。然而，在边缘情况下，用于比率计算的匹配块是完全错误的（参见问题 16），当正确性相关时，这不会使其成为合适的替代品。

当前实施

我目前使用 difflib 的 C++ 端口与 Levenshtein 距离的快速位并行实现相结合，权重插入 = 1、删除 = 1 和替换 = 2。当前的实现可以在这里找到：

• 提取matching_blocks：matching_blocks
• 计算加权 Levenshtein：加权 Levenshtein
• 将它们结合起来计算最终比率：partial_ratio

问题

有没有更快的算法来计算这种相似度。要求是：

• 仅使用 Replacement/Insertion（或赋予替换权重 2，具有类似效果）
• 允许在较长字符串的开头有一个间隙
• 允许在较长字符串的末尾有一个间隙，只要剩余的子字符串不变得比较短字符串的长度短。
• 最佳情况下，它强制子字符串具有相似的长度（当它不在末尾时），因此它匹配 FuzzyWuzzy 的行为，但是当它也允许匹配更长的子序列时会很好：例如 for aaba：aaa这意味着，它被允许aaba用作最佳子序列而不是aab。

标签： algorithmlevenshtein-distanceedit-distancesequence-alignment