Комбинация расстояний Левенштейна

Question

LD = Расстояние Левенштейна

Просто приведя несколько примеров на бумаге, кажется, это работает, но кто-нибудь знает, всегда ли это так?

Допустим, у меня есть 3 строки

БОТ

ЛПП

спецификация

ЛД(БОТ,БОБ) = 1

и

ЛД(БОБ,СПЕЦИФИКАЦИЯ)=1

затем

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

ИЛИ

БААБ

ББАБ

BCCD

ЛД(ББАБ,БААБ) = 1

и

ЛД(BBAB,BCCD)=3

затем

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

Я хотел бы знать, всегда ли это применимо.

То есть,

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

---

РЕДАКТИРОВАТЬ - Добавлено 22.10.2009, 19:08 по тихоокеанскому стандартному времени.

Я начинаю думать, что это справедливо для слов одинаковой длины, в противном случае вы все равно можете это сделать, но вам придется добавить абсолютное значение разницы в длине слова.

По сути LD(B,C) = max(LD(A,C),LD(A,B)) + abs(длина(B)-длина(C))

Answer 1

Не работает.

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

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

0 != 1

возможно, есть и более сложные примеры...

Answer 2

Нет, но это делает:

lev(a, c) <= lev(a, b) + lev(b, c) (так называемое «неравенство треугольника»)

...и широко используется в качестве эвристики VP-Trees и BK-Trees.

Будучи метрикой, расстояние Левенштейна следует неравенству треугольника:
http://en.wikipedia.org/wiki/Triangle_inequality

Answer 3

Нет ничего лучше, чем тест.Если вы знаете C#, пройдите через это.

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

Это обычная проблема динамического программирования.А запись в Википедии имеет часть «Доказательство правильности».Вы ищете что-то еще?

Answer 5

Не применимо для этого случая

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

    }

}

}