مزيج المسافة Levenshtein

Question

LD = مسافة ليفنشتاين

مجرد القيام ببعض الأمثلة على الورق، يبدو أن هذا ينجح، ولكن هل يعرف أحد ما إذا كان هذا صحيحًا دائمًا؟

لنفترض أن لدي 3 سلاسل

بوت

بوب

بوم

إل دي (بوت، بوب) = 1

و

لدن (بوب، بوم) = 1

ثم

LD(BOT,BOM)=الحد الأقصى(LD(BOT,BOB) , LD(BOB,DOM))=1

أو

باب

بباب

BCCD

إل دي (بباب، باب) = 1

و

إل دي (BBAB، BCCD) = 3

ثم

LD(BAAB,BCCD)=الحد الأقصى(LD(BBAB,BAAB), LD(BBAB,BCCD))=3

أود أن أعرف إذا كان هذا ينطبق دائمًا.

إنه،

LD(B,C) = الحد الأقصى (LD(A,C),LD(A,B))

---

تحرير - تمت الإضافة في 22/10/2009 الساعة 7:08 مساءً بتوقيت المحيط الهادئ

بدأت أعتقد أن هذا ينطبق على الكلمات ذات الطول نفسه، وإلا فلا يزال بإمكانك القيام بذلك ولكن عليك إضافة القيمة المطلقة للفرق في طول الكلمة.

المضمون LD(B,C) = الحد الأقصى(LD(A,C),LD(A,B)) + القيمة المطلقة(الطول(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

لا، ولكن هذا يفعل:

ليف (أ، ج) <= ليف (أ، ب) + ليف (ب، ج) (ويعرف أيضًا باسم "عدم المساواة المثلثية"

... ويستخدم بكثرة كدليل إرشادي بواسطة 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];

    }

}

}