Levenshtein距离为我们提供了一种根据无序个体字符计算两个相似字符串之间距离的方法:
quick brown fox quikc brown fax
Levenshtein距离= 3.
具有相似子序列的两个字符串之间距离的类似算法是什么？例如,在
quickbrownfox brownquickfox
Levenshtein距离是10,但这并没有考虑到弦有两个相似的子序列的事实,这使得它们比完全无序的词更像"相似"
quickbrownfox qburiocwknfox
然而,这个完全无序的版本的Levenshtein距离为8.
考虑到子序列的长度,存在哪些距离度量,而不假设子序列可以很容易地分成不同的词？