Levenshtein combinazione di distanza
-
05-07-2019 - |
Domanda
LD = Levenshtein Distance
Sto solo facendo alcuni esempi su carta, questo sembra funzionare, ma qualcuno sa se questo è sempre vero?
Diciamo che ho 3 stringhe
BOT
BOB
BOM
LD (BOT, BOB) = 1
e
LD (BOB, BOM) = 1
quindi
LD (BOT, BOM) = max (LD (BOT, BOB), LD (BOB, DOM)) = 1
o
BAAB
BBAB
BCCD
LD (BBAB, BAAB) = 1
e
LD (BBAB, BCCD) = 3
quindi
LD (BAAB, BCCD) = max (LD (BBAB, BAAB), LD (BBAB, BCCD)) = 3
Mi piacerebbe sapere se questo vale sempre.
Cioè,
LD (B, C) = max (LD (A, C), LD (A, B))
MODIFICA - Aggiunta il 22/10/2009 alle 19:08 PST
Sto iniziando a pensare che questo valga per le parole della stessa lunghezza, altrimenti puoi ancora farlo ma devi aggiungere il valore assoluto della differenza nella lunghezza delle parole.
In sostanza LD (B, C) = max (LD (A, C), LD (A, B)) + abs (lunghezza (B) -lunghezza (C))
Soluzione
Non funziona.
LD("BOB", "BOT") == 1
LD("BOT", "BOB") == 1
LD("BOB", "BOB") == 0
max(LD("BOB", "BOT"), LD("BOT", "BOB")) == 1
0 != 1
probabilmente ci sono anche esempi più difficili ...
Altri suggerimenti
No, ma questo fa:
lev (a, c) < = lev (a, b) + lev (b, c) (a.k.a " disuguaglianza del triangolo)
... ed è ampiamente usato come euristico da VP-Trees e BK-Trees.
Essendo una metrica, la distanza di Levenshtein segue la disuguaglianza del triangolo:
http://en.wikipedia.org/wiki/Triangle_inequality
Niente è meglio di un test. Se conosci C # eseguilo attraverso questo.
public Int32 CalculateDistance(String x, String y)
{
Int32 xl = x.Length;
Int32 yl = y.Length;
Int32[,] matrix = new Int32[xl + 1, yl + 1];
for (Int32 i = 0; i <= xl; i++)
{
matrix[i, 0] = i;
}
for (Int32 i = 0; i <= yl; i++)
{
matrix[0, i] = i;
}
for (Int32 j = 1; j <= yl; j++)
{
for (Int32 i = 1; i <= xl; i++)
{
if (x[i - 1] == y[j - 1])
{
matrix[i, j] = matrix[i - 1, j - 1];
}
else
{
matrix[i, j] = Min((matrix[i - 1, j] + 1), (matrix[i, j - 1] + 1), (matrix[i - 1, j - 1] + 1));
}
}
}
return matrix[xl, yl];
}
Questo è un normale problema di programmazione dinamica. La voce di Wikipedia ha una parte Proof of Correctness. Stai cercando qualcos'altro?
Non valido per questo caso
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LevenshteinDistance
{
class Program
{
static void Main(string[] args)
{
LevenshteinDistance ld = new LevenshteinDistance();
string a="B";
string b="Book";
string c = "Sick";
Console.WriteLine("{0} = Max( {1}, {2} )", ld.Compute(b, c), ld.Compute(a, c), ld.Compute(a, b));
if (ld.Compute(b, c) == Math.Max(ld.Compute(a, c), ld.Compute(a, b)))
Console.WriteLine("Equal");
else
Console.WriteLine("Not Equal");
Console.ReadKey();
}
}
class LevenshteinDistance
{
//****************************
// Get minimum of three values
//****************************
private int Minimum(int a, int b, int c)
{
int min;
min = a;
if (b < min)
{
min = b;
}
if (c < min)
{
min = c;
}
return min;
}
//*****************************
// Compute Levenshtein distance
//*****************************
public int Compute(string s, string t)
{
int[,] matrix; // matrix
int n; // length of s
int m; // length of t
int i; // iterates through s
int j; // iterates through t
char s_i; // ith character of s
char t_j; // jth character of t
int cost; // cost
// Step 1
n = s.Length;
m = t.Length;
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
matrix = new int[n + 1, m + 1];
// Step 2
for (i = 0; i <= n; i++)
{
matrix[i, 0] = i;
}
for (j = 0; j <= m; j++)
{
matrix[0, j] = j;
}
// Step 3
for (i = 1; i <= n; i++)
{
s_i = s[(i - 1)];
// Step 4
for (j = 1; j <= m; j++)
{
t_j = t[(j - 1)];
// Step 5
if (s_i == t_j)
{
cost = 0;
}
else
{
cost = 1;
}
// Step 6
matrix[i, j] = Minimum(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1, matrix[i - 1, j - 1] + cost);
}
}
// Step 7
return matrix[n, m];
}
}
}