单词级别编辑句子的距离

Question

是否有算法可以让您找到2个句子之间的单词级编辑距离？例如,"大肥狗"和"肥狗大房子"有1个替代品,3个插入物

Answer 1

您可以使用相同的算法来查找字符串中的编辑距离,以查找句子中的编辑距离.您可以将句子视为从字母表中绘制的字符串,其中每个字符都是英语中的单词(假设空格用于标记一个"字符"开始和下一个结束的位置).用于计算编辑距离的任何标准算法,例如用于计算Levenshtein距离的标准动态编程方法,可以适用于解决该问题.

Answer 2

通常,这称为序列比对问题.实际上,对齐哪些实体(位,字符,单词或DNA库)并不重要 - 只要该算法适用于一种类型的项目,它将适用于其他所有项目.重要的是您是否需要全局或局部对齐.

当序列相似且大小大致相同时,尝试对齐每个序列中的每个残基的全局比对是最有用的.一般的全局对齐技术是Needleman-Wunsch算法算法,该算法基于动态编程.当人们谈论Levinstain距离时,他们通常意味着全球一致.该算法非常简单,有几个人独立发现它,有时您可能会遇到Wagner-Fischer算法,这个算法本质上是相同的,但在两个字符串之间编辑距离的上下文中更常提到.

局部比对对于怀疑在其较大序列环境中包含相似区域或相似序列基序的不同序列更有用.所述 Smith-Waterman算法是一般的局部比对方法也是基于动态规划.它很少用于自然语言处理,更常用于生物信息学.