11
04/2018
多种序列距离汇总
莱文斯坦（Levenshtein）距离
含义：指两个字串之间，由一个转成另一个所需要的最少编辑次数，允许的编辑操作包括：删除一个字符，替换一个字符，增加一个字符。
应用场景：DNA分析；拼写检查；语音识别；抄袭检测；
距离通项公式：
距离通项公式：
最长公共子序列（LCS）
含义：一个字串S=<s1, s2, …, sn>是另一个字串T=<t1, t2, …, tm>的子序列，是指T中去除一些元素但不改变元素的相对位置，能够得到S。最长公共子序列可以看成莱文斯坦距离的变种，允许的操作包括：删除一个元素，增加一个元素。
应用场景：版本控制；Diff工具
长度通项公式：
汉明距离（Hamming Distance）
含义：两个等长字符串之间的汉明距离是指两个字符串对应位置的不同字符个数。汉明距离可以看成莱文斯坦距离的变种，只允许变换操作。
应用场景：信息论，编码理论，密码学
Damerau- Levenshtein Distance
含义：指两个字串之间，由一个转成另一个所需要的最少编辑次数，允许的编辑操作包括：删除一个字符，替换一个字符，增加一个字符，交换相邻的字符。
应用：基因分析，输入错误检测。
距离通项公式：
Dynamic Time Warping (动态时间规整)
https://en.wikipedia.org/wiki/Dynamic_time_warping
Fréchet distance
https://en.wikipedia.org/wiki/Fr%C3%A9chet_distance
Hausdorff distance
https://en.wikipedia.org/wiki/Hausdorff_distance
1 条评论