是否存在一种算法可以找到两个句子之间的单词级编辑距离? 例如,"A Big Fat Dog" 和 "The Big House with the Fat Dog" 之间有1个替换和3个插入。
是否存在一种算法可以找到两个句子之间的单词级编辑距离? 例如,"A Big Fat Dog" 和 "The Big House with the Fat Dog" 之间有1个替换和3个插入。
本地比对更适用于不相似的序列,这些序列被怀疑包含相似区域或类似的序列模体在其较大的序列上下文中。Smith-Waterman算法是一种基于动态规划的通用本地比对方法。它在自然语言处理中很少使用,更多地用于生物信息学。
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
这里是使用动态规划方法实现的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));
}
}