Damerau - Distância de Levenshtein, adicionando um limiar
-
27-09-2019 - |
Pergunta
Eu tenho a seguinte implementação, mas quero adicionar um limite; portanto, se o resultado for maior que ele, basta parar de calcular e retornar.
Como eu iria fazer isso?
Editar: aqui está o meu código atual, threshold
ainda não é usado ... o objetivo é que ele é usado
public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
{
// Return trivial case - where they are equal
if (string1.Equals(string2))
return 0;
// Return trivial case - where one is empty
if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
return (string1 ?? "").Length + (string2 ?? "").Length;
// Ensure string2 (inner cycle) is longer
if (string1.Length > string2.Length)
{
var tmp = string1;
string1 = string2;
string2 = tmp;
}
// Return trivial case - where string1 is contained within string2
if (string2.Contains(string1))
return string2.Length - string1.Length;
var length1 = string1.Length;
var length2 = string2.Length;
var d = new int[length1 + 1, length2 + 1];
for (var i = 0; i <= d.GetUpperBound(0); i++)
d[i, 0] = i;
for (var i = 0; i <= d.GetUpperBound(1); i++)
d[0, i] = i;
for (var i = 1; i <= d.GetUpperBound(0); i++)
{
for (var j = 1; j <= d.GetUpperBound(1); j++)
{
var cost = string1[i - 1] == string2[j - 1] ? 0 : 1;
var del = d[i - 1, j] + 1;
var ins = d[i, j - 1] + 1;
var sub = d[i - 1, j - 1] + cost;
d[i, j] = Math.Min(del, Math.Min(ins, sub));
if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
}
}
return d[d.GetUpperBound(0), d.GetUpperBound(1)];
}
}
Solução 4
Finalmente consegui ... embora não seja tão benéfico quanto eu esperava
public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
{
// Return trivial case - where they are equal
if (string1.Equals(string2))
return 0;
// Return trivial case - where one is empty
if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
return (string1 ?? "").Length + (string2 ?? "").Length;
// Ensure string2 (inner cycle) is longer
if (string1.Length > string2.Length)
{
var tmp = string1;
string1 = string2;
string2 = tmp;
}
// Return trivial case - where string1 is contained within string2
if (string2.Contains(string1))
return string2.Length - string1.Length;
var length1 = string1.Length;
var length2 = string2.Length;
var d = new int[length1 + 1, length2 + 1];
for (var i = 0; i <= d.GetUpperBound(0); i++)
d[i, 0] = i;
for (var i = 0; i <= d.GetUpperBound(1); i++)
d[0, i] = i;
for (var i = 1; i <= d.GetUpperBound(0); i++)
{
var im1 = i - 1;
var im2 = i - 2;
var minDistance = threshold;
for (var j = 1; j <= d.GetUpperBound(1); j++)
{
var jm1 = j - 1;
var jm2 = j - 2;
var cost = string1[im1] == string2[jm1] ? 0 : 1;
var del = d[im1, j] + 1;
var ins = d[i, jm1] + 1;
var sub = d[im1, jm1] + cost;
//Math.Min is slower than native code
//d[i, j] = Math.Min(del, Math.Min(ins, sub));
d[i, j] = del <= ins && del <= sub ? del : ins <= sub ? ins : sub;
if (i > 1 && j > 1 && string1[im1] == string2[jm2] && string1[im2] == string2[jm1])
d[i, j] = Math.Min(d[i, j], d[im2, jm2] + cost);
if (d[i, j] < minDistance)
minDistance = d[i, j];
}
if (minDistance > threshold)
return int.MaxValue;
}
return d[d.GetUpperBound(0), d.GetUpperBound(1)] > threshold
? int.MaxValue
: d[d.GetUpperBound(0), d.GetUpperBound(1)];
}
Outras dicas
Isso se refere à sua resposta: Damerau - Distância de Levenshtein, adicionando um limiar(desculpe, não posso comentar, pois ainda não tenho 50 representantes)
Eu acho que você cometeu um erro aqui. Você inicializou:
var minDistance = threshold;
E sua regra de atualização é:
if (d[i, j] < minDistance)
minDistance = d[i, j];
Além disso, seus critérios de saída antecipados são:
if (minDistance > threshold)
return int.MaxValue;
Agora, observe que a condição IF acima nunca se manterá verdadeira! Você deve preferir inicializar minDistance
para int.MaxValue
Aqui está a maneira mais elegante que consigo pensar. Depois de definir cada índice de D, veja se ele excede seu limite. A avaliação é de tempo constante, por isso é uma queda no balde em comparação com a complexidade teórica do algoritmo geral:
public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
{
...
for (var i = 1; i <= d.GetUpperBound(0); i++)
{
for (var j = 1; j <= d.GetUpperBound(1); j++)
{
...
var temp = d[i,j] = Math.Min(del, Math.Min(ins, sub));
if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
temp = d[i,j] = Math.Min(temp, d[i - 2, j - 2] + cost);
//Does this value exceed your threshold? if so, get out now
if(temp > threshold)
return temp;
}
}
return d[d.GetUpperBound(0), d.GetUpperBound(1)];
}
Você também fez isso como uma pergunta SQL CLR UDF, então responderei nesse contexto específico: sua melhor optmiziação não virá da otimização da distância de Levenshtein, mas de reduzir o número de pares que você compara. Sim, um algoritmo mais rápido de Levenshtein melhorará as coisas, mas não tanto quanto reduzir o número de comparações de n quadrado (com n nas milhões de linhas) para n*algum fator. Minha proposta é comparar apenas elementos que têm a diferença de comprimento dentro de um delta tolerável. Em sua mesa grande, você adiciona uma coluna calculada persistida em LEN(Data)
e, em seguida, crie um índice com dados inclui:
ALTER TABLE Table ADD LenData AS LEN(Data) PERSISTED;
CREATE INDEX ndxTableLenData on Table(LenData) INCLUDE (Data);
Agora você pode restringir o espaço problemático, juntando -se a uma diferença máxima no Lenght (por exemplo, digamos 5), Se os seus dados LEN(Data)
varia significativamente:
SELECT a.Data, b.Data, dbo.Levenshtein(a.Data, b.Data)
FROM Table A
JOIN Table B ON B.DataLen BETWEEN A.DataLen - 5 AND A.DataLen+5