Combinación de distancia Levenshtein

Question

LD = Distancia de Levenshtein

Simplemente haciendo algunos ejemplos en papel, esto parece funcionar, pero ¿alguien sabe si esto siempre es cierto?

Digamos que tengo 3 cadenas

BOT

BOB

BOM

LD (BOT, BOB) = 1

y

LD (BOB, BOM) = 1

luego

LD (BOT, BOM) = max (LD (BOT, BOB), LD (BOB, DOM)) = 1

O

BAAB

BBAB

BCCD

LD (BBAB, BAAB) = 1

y

LD (BBAB, BCCD) = 3

luego

LD (BAAB, BCCD) = max (LD (BBAB, BAAB), LD (BBAB, BCCD)) = 3

Me gustaría saber si esto siempre se aplica.

Es decir,

LD (B, C) = max (LD (A, C), LD (A, B))

---

EDITAR - Agregado el 22/10/2009 7:08 PM PST

Estoy empezando a pensar que esto es válido para palabras de la misma longitud, de lo contrario aún puede hacerlo, pero debe agregar el valor absoluto de la diferencia en la longitud de la palabra.

En esencia LD (B, C) = max (LD (A, C), LD (A, B)) + abs (longitud (B) -longitud (C))

Answer 1

No funciona.

LD("BOB", "BOT") == 1
LD("BOT", "BOB") == 1

LD("BOB", "BOB") == 0
max(LD("BOB", "BOT"), LD("BOT", "BOB")) == 1

0 != 1

probablemente hay ejemplos más difíciles también ...

Answer 2

No, pero esto lo hace:

lev (a, c) < = lev (a, b) + lev (b, c) (a.k.a " desigualdad triangular)

... y es muy usado como heurístico por VP-Trees y BK-Trees.

Siendo una métrica, la distancia levenshtein sigue la desigualdad del triángulo:
http://en.wikipedia.org/wiki/Triangle_inequality

Answer 3

Nada es mejor que una prueba. Si conoce C #, ejecútelo.

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

Este es un problema regular de programación dinámica. La entrada de Wikipedia tiene una parte de Prueba de corrección. ¿Estás buscando algo más?

Answer 5

No fue cierto para este 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];

    }

}

}