خوارزمية مسافة ليفنشتاين

خوارزمية مسافة ليفنشتاين

Levenshtein Distance Algorithm

 سميت هذه الخوارزمية باسم فلاديمير ليفنشتاين Vladimir Levenshtein، الذي وضعها عام 1965.

وتحسب هذه الخوارزمية المسافة بين نصين، حيث تقاس هذه المسافة بعدد التغييرات المطلوب إجراؤها على النص الأول، ليصير مطابقا للنص الثاني.. هذا التغيير يحدث بتبديل حرف مكان حرف، أو حذف حرف، أو إضافة حرف.. فإذا كانت المسافة بين النصين صفرا، كان هذا معناه أنهما متطابقان، وإذا كانت 1 فهذا يعني أن أحدهما يختلف عن الآخر بحرف (زيادة أو نقصا أو تغيّرا) وهكذا...

على سبيل المثال: لكي تتحول كلمة ضلعك إلى كلمة لاعب، يجب أن تحدث لها التغييرات التالية:

-      حذف حرف الضاد: لعك.

-      إضافة حرف الألف: لاعك.

-      تبديل الكاف إلى باء: لاعب.

هذا معناه أن المسافة بين الكلمتين تساوي 3.

إذن، كيف تقوم هذه الخوارزمية بقياس هذه المسافة؟

 

تستخدم هذه الخوارزمية القواعد التالية:

- ترقيم أول حرف في النص هو 1 (على عكس ما نتبعه نحن في البرمجة، حيث أول حرف في النص هو صفر.. لهذا سنحتاج لطرح 1 عند استخدام خصائص الفئة String لقراءة الحروف من كل نص).

- أقصر مسافة ممكنة هي صفر (النصان متماثلان).

- أطول مسافة ممكنة، هي عدد حروف أطول نص من النصين (يحدث هذا إذا كانت كل الحروف مختلفة، أو أحد النصين فارغا).

- يتم حساب المسافة بين الحرف رقم I في النص الأول، والحرف رقم J في النص الثاني كالتالي:

1- إذا كان I  يساوي صفرا، فالمسافة هي J.. وإذا كان J تساوي صفرا فالمسافة هي I.. وإذا كان كل منهما صفرا، فالمسافة هي صفر..

(ملحوظة: كما اتفقنا، لا يوجد حرف في النص في هذه الخوارزمية رقمه صفر.. لكن القيمة صفر تحدث بسبب طريقة عمل الخوارزمية، فحساب المسافة بلين أي حرفين يعتمد على قيمة المسافة بين حرفين سابقين، لهذا تحدث هذه الحالة الخاصة عندما نتعامل مع أول حرف في كل نص).

ويمكنك صياغة القاعدة السابقة بطريقة أخرى كالتالي: إذا كانت أصغر قيمة لـ I و J هي صفر، فالمسافة هي أكبر قيمة لـ I أو J.. على كل حال لن نستخدم أي مقارنات عند كتابة كود الخوارزمية، لأننا سنضع جميع المسافات بين الحروف في مصفوفة ثنائية البعد (سنسميها d) عدد صفوفها يساوي طول النص الأول + 1، وعدد أعمدتها يساوي طول النص الثاني + 1.. حيث سنستخدم الصف الأول (رقم صفر) والعمود الأول (رقم صفر) للتعامل مع هذه الحالة الخاصة التي فيها قيمة I أو J تساوي صفرا، لهذا دائما سيحتوي العمود الأول على الأعداد من 0 إلى طول النص الأول.. بعبارة أخرى: كل خانة في العمود الأول سنضع فيها رقم الصف الذي توجد فيه:

VB Code:

For i = 0 To L1

       d(i, 0) = i

Next

 

C# Code:

for (int i = 0; i <= L1; i++)

      d(i, 0) = i;

 

وسيحتوي الصف الأول على الأعداد من 0 إلى طول النص الثاني.. بعبارة أخرى: كل خانة في الصف الأول سنضع فيها رقم العمود الذي توجد فيه:

VB Code:

For j = 0 To L2

      d(0, j) = j

Next

 

C# Code:

for (int j = 0; j <= L2; j++)

     d(0, j) = j;

 

2- عندما تكون قيمتا I و J أكبر من صفر، يتم حساب المسافة بأخذ التكلفة الأقل من بين التكاليف الثلاث التالية.. (لاحظ أن لفظ التكلفة ولفظ المسافة يستخدمان في هذه النوعية من الخوارزميات التي تحسب الفروق بين كينونتين):

أ- تكلفة استبدال حرف: وهي تساوي المسافة بين الحرف السابق للحرف الحالي في النص الأول (الحرف رقم i-1)، والحرف السابق للحرف الحالي في النص الثاني (الحرف رقم j-1)، مضافا إليها 1 إذا كان الحرفان الحاليان مختلفين، أو صفرا إذا كانا متماثلين (لا حاجة للاستبدال).

VB Code:

SubstitutionCost = d(i - 1, j - 1) + If(chr2 = chr1, 0, 1)               

 

C# Code:

SubstitutionCost = d(i - 1, j - 1) + ((chr2 == chr1) ? 0 : 1);

 

ب- تكلفة حذف حرف: في حالة حذف الحرف الحالي في النص الأول، تكون التكلفة هي (المسافة بين الحرف السابق للحرف الحالي في النص الأول، وبين الحرف الحالي في النص الثاني) + 1 (التغيير الناتج عن الحذف).

DeletionCost = d(i - 1, j) + 1

للتوضيح: لو كنا نقارن الكلمتين "لاعب" و "لعب".. تكلفة مقارنة حرف الألف من الكلمة الأولى بحرف اللام من الكلمة الثانية = تكلفة مقارنة ل و ل + 1 = صفر + 1 (ناتج عن حذف الألف من النص الأول).

ج- تكلفة إضافة حرف: في حالة إضافة حرف جديد بعد الحرف الحالي في النص الأول، تكون التكلفة هي (المسافة بين الحرف الحالي في النص الأول، وبين الحرف السابق للحرف الحالي في النص الثاني) + 1 (التغيير الناتج عن الإضافة).

AdditionCost = d(i, j - 1) + 1

للتوضيح: عند مقارنة الكلمتين "لعب" و"لاعب".. تكلفة مقارنة حرف اللام من الكلمة الأولى بحرف الألف من الكلمة الثانية = تكلفة مقارنة ل و ل + 1 = صفر + 1 (ناتج عن إضافة ألف في النص الأول بعد الحرف الحالي).

 

وفي النهاية سنضع المسافة بين الحرفين في الخانة الموجودة في الصف رقم i والعمود رقم j في المصفوفة:

d(i, j) = Math.Min(SubstitutionCost,

                              Math.Min(AdditionCost, DeletionCost))

 

-      من القواعد السابقة، يتضح لنا أننا نحتاج لملء جميع خانات المصفوفة d كاملة لحساب كل المسافات بين كل الحروف، حيث يعتمد حساب كل مسافة على قيمة 3 مسافات سابقة.. وفي النهاية ستكون المسافة الكلية بين النصين، هي المسافة بين أخر حرف في النص الأول وآخر حرف في النص الثاني، وهي المسافة التي وضعناها في الخانة الموجودة في آخر صف وآخر عمود في المصفوفة d.

 

أخيرا أترككم مع كود الدالة التي تحسب مسافة ليفنشتاين كاملا، وإن شاء الله في الموضوع القادم أشرح لكم كيف نستفيد من هذه الخوارزمية وهذه الدالة:

VB Code:

Public Function LevenshteinDistance(ByVal Str1 As String,

                                              ByVal Str2 As String) As Integer

 

        Dim L1 As Integer = Str1.Length

        Dim L2 As Integer = Str2.Length

        Dim d(L1, L2) As Integer

 

        If L1 = 0 Then Return L2

        If L2 = 0 Then Return L1

 

        Dim i As Integer

        Dim j As Integer

 

        For i = 0 To L1

            d(i, 0) = i

        Next

 

        For j = 0 To L2

            d(0, j) = j

        Next

 

        For i = 1 To L1

            Dim chr1 = Str1(i - 1)

            For j = 1 To L2

                Dim chr2 = Str2(j - 1)

                Dim SubstitutionCost = d(i - 1, j - 1) + If(chr2 = chr1, 0, 1)                

                Dim DeletionCost = d(i - 1, j) + 1

                Dim AdditionCost = d(i, j - 1) + 1

                d(i, j) = Math.Min(SubstitutionCost,

                                       Math.Min(AdditionCost, DeletionCost))

            Next

        Next

 

        Return d(L1, L2)

    End Function

 

C# Code:

public int LevenshteinDistance(string Str1, string Str2)

{

         int L1 = Str1.Length;

         int L2 = Str2.Length;

         int[,] d = new int[L1 + 1, L2 + 1];

 

         if (L1 == 0)

                 return L2;

 

         if (L2 == 0)

                 return L1;

 

         int i = 0;

         int j = 0;

 

         for (i = 0; i <= L1; i++)

                 d[i, 0] = i;

 

         for (j = 0; j <= L2; j++)

                 d[0, j] = j;

 

         for (i = 1; i <= L1; i++)

         {

                 char chr1 = Str1[i - 1];

                 for (j = 1; j <= L2; j++)

                 {

                          var chr2 = Str2[j - 1];

                          var SubstitutionCost = d[i - 1, j - 1] + ((chr2 == chr1) ? 0 : 1);

                          var DeletionCost = d[i - 1, j] + 1;

                          var AdditionCost = d[i, j - 1] + 1;

                          d[i, j] = Math.Min(SubstitutionCost,

                                                Math.Min(AdditionCost, DeletionCost));

                 }

         }

         return d[L1, L2];

}