22

有没有一种算法可以让你找到两个句子之间的词级编辑距离？例如，“A Big Fat Dog”和“The Big House with the Fat Dog”有 1 个替代品，3 个插入

4

6 回答 6

12

通常，这称为序列比对问题。实际上，对齐什么实体（位、字符、单词或 DNA 碱基）并不重要，只要该算法适用于一种类型的项目，它就适用于其他所有项目。重要的是您想要全局对齐还是局部对齐。

全局比对尝试比对每个序列中的每个残基，当序列相似且大小大致相等时最有用。一种通用的全局对齐技术是基于动态规划的Needleman-Wunsch 算法算法。当人们谈论莱文斯坦距离时，他们通常指的是全局对齐。该算法非常简单，以至于几个人独立发现了它，有时您可能会遇到本质上相同的Wagner-Fischer 算法，但在两个字符串之间的编辑距离的上下文中被更多地提及。

局部比对对于怀疑在其较大序列上下文中包含相似区域或相似序列基序的不同序列更有用。Smith-Waterman 算法是一种通用的 局部对齐方法，也是基于动态规划的。它在自然语言处理中很少使用，在生物信息学中更常见。

于 2014-04-27T23:09:19.727 回答
9

您可以使用用于查找字符串中的编辑距离的相同算法来查找句子中的编辑距离。您可以将句子视为从字母表中提取的字符串，其中每个字符都是英语中的一个单词（假设空格用于标记一个“字符”的开始位置和下一个字符的结束位置）。任何用于计算编辑距离的标准算法，例如用于计算 Levenshtein 距离的标准动态规划方法，都可以适用于解决这个问题。

于 2011-02-20T07:50:34.730 回答
1

从 nltk 包中查看 python 中的 AlignedSent 函数。它在单词级别对齐句子。

https://www.nltk.org/api/nltk.align.html

于 2020-09-15T18:13:12.357 回答
0

这是@templatetypedef 在 ActionScript 中的想法的示例实现（它对我很有用），它计算标准化的 Levenshtein 距离（或者换句话说，给出了 [0..1] 范围内的值）

  private function nlevenshtein(s1:String, s2:String):Number {
     var tokens1:Array = s1.split(" ");
     var tokens2:Array = s2.split(" ");
     const len1:uint = tokens1.length, len2:uint = tokens2.length;
     var d:Vector.<Vector.<uint> >=new Vector.<Vector.<uint> >(len1+1);
     for(i=0; i<=len1; ++i)
        d[i] = new Vector.<uint>(len2+1);

     d[0][0]=0;

     var i:int;
     var j:int;

     for(i=1; i<=len1; ++i) d[i][0]=i; 
     for(i=1; i<=len2; ++i) d[0][i]=i;

     for(i = 1; i <= len1; ++i)
        for(j = 1; j <= len2; ++j)
           d[i][j] = Math.min( Math.min(d[i - 1][j] + 1,d[i][j - 1] + 1),
              d[i - 1][j - 1] + (tokens1[i - 1] == tokens2[j - 1] ? 0 : 1) );

     var nlevenshteinDist:Number = (d[len1][len2]) / (Math.max(len1, len2));

     return nlevenshteinDist;
  }

我希望这个能帮上忙！

于 2014-04-04T06:46:45.647 回答
0

D 中的实现可以泛化到任何范围，因此也可以泛化为数组。因此，通过将您的句子分成字符串数组，它们可以通过算法运行，并且将提供一个编辑编号。

https://dlang.org/library/std/algorithm/comparison/levenshtein_distance.html

于 2017-05-05T16:29:33.460 回答
0

这是使用动态编程方法的句子编辑距离算法的 Java 实现。

public class EditDistance {

    public int editDistanceDP(String sentence1, String sentence2) {
        String[] s1 = sentence1.split(" ");
        String[] s2 = sentence2.split(" ");
        int[][] solution = new int[s1.length + 1][s2.length + 1];

        for (int i = 0; i <= s2.length; i++) {
            solution[0][i] = i;
        }

        for (int i = 0; i <= s1.length; i++) {
            solution[i][0] = i;
        }

        int m = s1.length;
        int n = s2.length;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1].equals(s2[j - 1]))
                    solution[i][j] = solution[i - 1][j - 1];
                else
                    solution[i][j] = 1
                            + Math.min(solution[i][j - 1], Math.min(solution[i - 1][j], solution[i - 1][j - 1]));
            }
        }
        return solution[s1.length][s2.length];
    }

    public static void main(String[] args) {
        String sentence1 = "first second third";
        String sentence2 = "second";
        EditDistance ed = new EditDistance();
        System.out.println("Edit Distance: " + ed.editDistanceDP(sentence1, sentence2));
    }
}
于 2019-10-10T04:51:20.697 回答