单词级别编辑句子的距离

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

已邀请:

4 个回复

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

杭难插

通常，这称为序列比对问题。实际上，对齐哪些实体（位，字符，单词或DNA库）并不重要 - 只要该算法适用于一种类型的项目，它将适用于其他所有项目。重要的是您是否需要全局或局部对齐。当序列相似且大小大致相同时，尝试对齐每个序列中的每个残基的全局比对是最有用的。一般的全局对齐技术是Needleman-Wunsch算法算法，该算法基于动态编程。当人们谈论Levinstain距离时，他们通常意味着全球一致。该算法非常简单，有几个人独立发现它，有时您可能会遇到Wagner-Fischer算法，这个算法本质上是相同的，但在两个字符串之间编辑距离的上下文中更常提到。局部比对对于怀疑在其较大序列环境中包含相似区域或相似序列基序的不同序列更有用。 Smith-Waterman算法是一种基于动态规划的通用局部对齐方法。它很少用于自然语言处理，更常用于生物信息学。

敦肌

下面是ActionScript中@ templatetypedef的想法的一个示例实现（它对我很有用），它计算了规范化的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;
  }

我希望这个能帮上忙！

骇毖煽洁铂

D中的实现是在任何范围内推广的，因而是数组。因此，通过将句子分成字符串数组，可以运行算法并提供编辑号。 https://dlang.org/library/std/algorithm/comparison/levenshtein_distance.html

要回复问题请先登录或注册

单词级别编辑句子的距离

4 个回复

发起人

edit_distance

问题状态

单词级别编辑句子的距离

与内容相关的链接

4 个回复

发起人

edit_distance

问题状态