我在阅读的一篇论文中发现了一个粗略的字符串比较，如下所示：
他们使用的公式如下（从纸上提取，稍加改动，使其更通用和可读）
由于作者的描述不太清楚（以作者为例），我试着用自己的话多解释一点
例如，对于两个序列ABCDE和BCEFA，有两个可能的图
图1）将B与B、C与C、E与E连接起来
图2）将A与
当我连接其他三个（图1）时，我无法将A与A连接，因为这将是交叉线（假设您在B-B、C-C和E-E之间绘制线）；即，墨水A-A将交叉连接B-B、C-C和E-E的线。
所以这两个序列产生了两个可能的图，一个有三个连接（BB，CC和EE），另一个只有一个（AA），然后我按照下面的公式计算得分d。
因此，定义两者之间的相似程度
五弦我们计算它们之间的距离d。对齐
两个五弦，我们寻找它们之间的所有身份
字符，无论这些字符位于何处。如果每个身份是
我们定义了一个图，它由两个五元字符串之间的链接表示
为了这对。我们称此图的任何部分为配置。
接下来，我们保留所有那些没有字符的配置
交叉配对（我在上面的例子中解释了其含义，即相同字符之间没有链接交叉，只保留那些图）。
每一个都作为
与图形相关的字符数p，移动量Δi
对应对与连通特征间的间隙δij
每根五弦。选择最小值作为特征，并且
称为距离d:d Min（50–10p+∑Δi+∑δij），虽然非常粗糙，
这项措施与定性的观点大体上是一致的
引导估计。例如，abcde和abcfg之间的距离
是20，而abcde和abfcg之间是23=（50-30+1+2）。
我不知道该怎么做。任何帮助我的建议都将不胜感激。
我尝试了左旋恩施坦和蛋白质序列比较中使用的简单序列比对
该报的链接是：
http://peds.oxfordjournals.org/content/16/2/103.long
我找不到关于第一作者阿兰·费罗的任何信息，我给马索托的电子邮件也没有得到回复（截至今天）。
谢谢你
最佳答案
当然不是Levenshtein：
>>> from nltk import metrics
>>> metrics.distance.edit_distance('abcde','abcfg')
2
>>> metrics.distance.edit_distance('abcde','abfcg')
3
>>> help(metrics.distance.edit_distance)
Help on function edit_distance in module nltk.metrics.distance:
edit_distance(s1, s2)
Calculate the Levenshtein edit-distance between two strings.
The edit distance is the number of characters that need to be
substituted, inserted, or deleted, to transform s1 into s2. For
example, transforming "rain" to "shine" requires three steps,
consisting of two substitutions and one insertion:
"rain" -> "sain" -> "shin" -> "shine". These operations could have
been done in other orders, but at least three steps are needed.
@param s1, s2: The strings to be analysed
@type s1: C{string}
@type s2: C{string}
@rtype C{int}