测量无序序列之间距离的算法

Question

Levenshtein 距离为我们提供了一种根据无序单个字符计算两个相似字符串之间距离的方法:

quick brown foxquikc brown fax

编辑距离 = 3。

对于具有相似子序列的两个字符串之间的距离，有什么相似算法？例如，在

quickbrownfoxbrownquickfox

Levenshtein 距离为 10，但这没有考虑字符串具有两个相似子序列的事实，这使得它们比完全无序的单词更“相似”

quickbrownfoxqburiocwknfox

然而这个完全无序的版本的编辑距离为 8。

存在哪些考虑子序列长度的距离度量，而不假设子序列可以很容易地分解成不同的词？

Answer 1

我觉得你可以试试shingles或者它们与 Levenshtein 距离的一些组合。