Почему я получаю неправильное расстояние Левенштейна?
Я пытаюсь реализовать алгоритм расстояния Левенштейна на С# (для практики и потому, что это было бы удобно). Я использовал реализацию из Страница Википедии, но по какой-то причине я получаю неправильное расстояние для одного набора слов. Вот код (из 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 (что правильно). Я знаю, что что-то не так, но я не могу понять, что мне не хватает.
Онорио, вы должны реализовать это таким образом, потому что я думаю о более простом решении в С#
Ответы 2
В примере в Википедии используются строки с отсчетом от 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];
}
Я заметил, что в Википедии используется 0, а не 1, но, думаю, я просто не учел все потенциальные проблемы, которые могут возникнуть.
Ваша матрица недостаточно велика.
В псевдокоде s и t имеют длины m и n соответственно (char s[1..m], char t[1..n]). Однако матрица имеет размеры [0..m, 0..n], то есть на единицу больше, чем длина строк в каждом направлении. Вы можете увидеть это в таблицах под псевдокодом.
Значит матрица для "сидит" и "котенок" 7х8, а у вас матрица только 6х7.
Вы также неправильно индексируете строки, потому что строки в псевдокоде имеют индекс 1, а строки C# имеют индекс 0.
После их исправления вы получите этот код, который работает с «сидя» и «котенок»:
public static class LevenshteinDistance
{
public static int LevenshteinDistanceCalc(string source, string target)
{
int sourceSize = source.Length + 1, targetSize = target.Length + 1;
int[,] 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 - 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 - 1, targetSize - 1];
}
private static int leastOfThree(int a, int b, int c)
{
return Math.Min(a, (Math.Min(b, c)));
}
}
(Я также позволил себе сделать distance локальную переменную, так как нет необходимости в том, чтобы она была полем (это только делает ваш класс не потокобезопасным), а также сделал его статическим, чтобы избежать ненужного создания экземпляров).
Чтобы отладить это, я поставил точку останова на return distance[sourceSize - 1, targetSize - 1] и сравнил distance с таблицей в Википедии. Было совершенно очевидно, что он слишком мал.
Это отличный момент о том, что расстояние не обязательно должно быть полем.
Это связано с тем, что вы начинаете циклы с 1, а не с 0 — вы увидите, что получаете правильный результат всякий раз, когда входные данные начинаются с одной и той же буквы — «кошка» против «винтика» правильно возвращает 2, «кошка» против «собака» неправильно возвращает 2.