Levenshtein combinazione di distanza

Question

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))

Answer 1

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 ...

Answer 2

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

Answer 3

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];
}

Answer 4

Questo è un normale problema di programmazione dinamica. La voce di Wikipedia ha una parte Proof of Correctness. Stai cercando qualcos'altro?

Answer 5

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];

    }

}

}