Combinaison de distance de Levenshtein

Question

LD = Distance de Levenshtein

Juste quelques exemples sur papier, cela semble fonctionner, mais est-ce que quelqu'un sait si cela est toujours vrai?

Disons que j'ai 3 chaînes

BOT

BOB

Nomenclature

LD (BOT, BOB) = 1

et

LD (BOB, BOM) = 1

puis

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

OU

BAAB

BBAB

BCCD

LD (BBAB, BAAB) = 1

et

LD (BBAB, BCCD) = 3

puis

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

J'aimerais savoir si cela s'applique toujours.

C’est-à-dire

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

MODIFIER - Ajouté le 22/10/2009 à 19h08 HNP

Je commence à penser que cela s'applique aux mots de la même longueur, sinon vous pouvez toujours le faire, mais vous devez ajouter la valeur absolue de la différence de longueur de mot.

En substance, LD (B, C) = max (LD (A, C), LD (A, B)) + abs (longueur (B) -longueur (C))

Answer 1

Ne fonctionne pas.

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

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

0 != 1

il y a probablement des exemples plus difficiles aussi ...

Answer 2

Non, mais ceci:

lev (a, c) < = lev (a, b) + lev (b, c) (a.k.a & "inégalité triangulaire)

... et est largement utilisé comme heuristique par VP-Trees et BK-Trees.

Étant une métrique, la distance de Levenshtein suit l'inégalité du triangle:
http://fr.wikipedia.org/wiki/Triangle_inequality

Answer 3

Rien n’est meilleur qu’un test. Si vous savez que C # l'exécute.

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

Il s'agit d'un problème de programmation dynamique classique. La l'entrée de Wikipedia comporte une partie preuve de correction. Cherchez-vous autre chose?

Answer 5

N'est pas valable pour ce cas

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

    }

}

}