c# - 为什么我的 Levenshtein 距离不正确?
问题描述
我正在尝试在 C# 中实现 Levenshtein 距离算法(用于练习,因为它很方便)。我使用了Wikipedia 页面上的实现,但由于某种原因,我在一组单词上得到了错误的距离。这是代码(来自 LinqPad):
void Main()
{
var ld = new LevenshteinDistance();
int dist = ld.LevenshteinDistanceCalc("sitting","kitten");
dist.Dump();
}
// Define other methods and classes here
public class LevenshteinDistance
{
private int[,] distance;
public int LevenshteinDistanceCalc(string source, string target)
{
int sourceSize = source.Length, targetSize = target.Length;
distance = new int[sourceSize, targetSize];
for (int sIndex = 0; sIndex < sourceSize; sIndex++)
{
distance[sIndex, 0] = sIndex;
}
for (int tIndex = 0; tIndex < targetSize; tIndex++)
{
distance[0,tIndex] = tIndex;
}
// for j from 1 to n:
// for i from 1 to m:
// if s[i] = t[j]:
// substitutionCost:= 0
// else:
// substitutionCost:= 1
// d[i, j] := minimum(d[i - 1, j] + 1, // deletion
// d[i, j - 1] + 1, // insertion
// d[i - 1, j - 1] + substitutionCost) // substitution
//
//
// return d[m, n]
for (int tIndex = 1; tIndex < targetSize; tIndex++)
{
for (int sIndex = 1; sIndex < sourceSize; sIndex++)
{
int substitutionCost = source[sIndex] == target[tIndex] ? 0 : 1;
int deletion = distance[sIndex-1, tIndex]+1;
int insertion = distance[sIndex,tIndex-1]+1;
int substitution = distance[sIndex-1, tIndex-1] + substitutionCost;
distance[sIndex, tIndex] = leastOfThree(deletion, insertion, substitution);
}
}
return distance[sourceSize-1,targetSize-1];
}
private int leastOfThree(int a, int b, int c)
{
return Math.Min(a,(Math.Min(b,c)));
}
}
当我尝试“坐着”和“小猫”时,我得到的 LD 为 2(应该是 3)。然而,当我尝试“星期六”和“星期日”时,我得到的 LD 为 3(这是正确的)。我知道出了点问题,但我无法弄清楚我错过了什么。
解决方案
wikipedia 上的示例使用基于 1 的字符串。在 C# 中,我们使用从 0 开始的字符串。
在他们的矩阵中,确实存在 0 行和 0 列。所以他们的矩阵的大小是 [source.Length + 1, source.Length + 1] 在你的代码中它不存在。
public int LevenshteinDistanceCalc(string source, string target)
{
int sourceSize = source.Length, targetSize = target.Length;
distance = new int[sourceSize + 1, targetSize + 1];
for (int sIndex = 1; sIndex <= sourceSize; sIndex++)
distance[sIndex, 0] = sIndex;
for (int tIndex = 1; tIndex <= targetSize; tIndex++)
distance[0, tIndex] = tIndex;
for (int tIndex = 1; tIndex <= targetSize; tIndex++)
{
for (int sIndex = 1; sIndex <= sourceSize; sIndex++)
{
int substitutionCost = source[sIndex-1] == target[tIndex-1] ? 0 : 1;
int deletion = distance[sIndex - 1, tIndex] + 1;
int insertion = distance[sIndex, tIndex - 1] + 1;
int substitution = distance[sIndex - 1, tIndex - 1] + substitutionCost;
distance[sIndex, tIndex] = leastOfThree(deletion, insertion, substitution);
}
}
return distance[sourceSize, targetSize];
}
推荐阅读
- typescript - 如何使用多个 tsconfig 文件(编译器选项冲突)?
- html - 我怎样才能使下拉菜单的大小与按钮(宽度)相同
- php - CURLE_OPERATION_TIMEDOUT
- java - 如何使用 selenium webdriver 找到将返回所有下拉列表值的 xpath
- c# - 查看组件未正确加载 css 和 js 不适用于 ajax 调用
- java - 更新java spark中结构类型列中的值
- shell - 提交命令时如何在 CLI Unix 中给出今天的日期?
- wordpress - 编辑查看订单页面 WooCommerce
- sql-server - 如何将 SQL Server 选择的结果导入 Azure 逻辑应用中的新 Excel 文件?
- c# - 将对象设置为接口后如何访问类方法?