查找具有不同长度[闭合]的特征向量的相似性度量

正如有人已经说过的,一个可能的替代方案是 Levenshtein距离 ,有时也称为 编辑距离 .

Levenshtein距离是分配给每对字符串的函数 A 和 B 自然数 n ,表示需要转换的最小操作数 A. 到 B 。允许的操作为

1. 从中删除符号 A. ,
2. 将符号插入 A. ,
3. 替换中的符号 A. .

请注意,编辑距离是对称的(对于任何转换操作序列 A. 到 B )可以构造一个“反转”的操作序列 B 到 A. .

维基百科关于 Levenshtein distance 列出了一些有用的财产。

最后,作为示例,让我们转换两个向量:

[10011]
// Insert 1 into position 2:
[101011]
// Insert 0 into position 5:
[1010101]
// Insert 0 into position 7:
[10101010]

我们发现了一系列3次操作。如果我们能够证明没有更短的序列,那么我们可以得出结论: V1 和 V2 为3。考虑到莱文施泰因距离总是 至少 两个字符串之间的大小差异(想想原因),然后我们得出结论:

levenshtein_distance(V1,V2) == 3 // returns true!

希望这有帮助!