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

تُعد مسافة ليفنشتاين من أكثر المقاييس استخدامًا في معالجة النصوص، إذ تتيح قياس مدى التشابه بين سلسلتين نصيتين من خلال حساب أقل عدد من عمليات التحرير اللازمة لتحويل إحداهما إلى الأخرى.

وتُستخدم على نطاق واسع في تطبيقات مثل المدققات الإملائية، ومحركات البحث، وأنظمة التعرف على النصوص، حيث تساعد على اكتشاف الكلمات المتقاربة واقتراح البدائل المناسبة.

لحساب مسافة ليفنشتاين، تُنشأ مصفوفة تمثل فيها كل خلية أقل تكلفة لتحويل سلسلة جزئية إلى سلسلة جزئية أخرى. ويجري ملء المصفوفة تدريجيًا، خلية بعد أخرى، حتى الوصول إلى أقل عدد ممكن من العمليات.

وعلى خلاف مسافة هامينغ، يمكن تطبيق مسافة ليفنشتاين على السلاسل النصية ذات الأطوال المختلفة.

مثال عملي

لنفترض أن لدينا السلسلتين النصيتين \( s \) و \( t \):

$$ s = "kitten" $$

$$ t = "sitting" $$

نريد حساب مسافة ليفنشتاين بين هاتين الكلمتين، أي تحديد أقل عدد من عمليات التحرير، سواء كانت إدراجًا أو حذفًا أو استبدالًا، اللازمة لتحويل "kitten" إلى "sitting".

1. استبدال
   استبدال الحرف \( k \) بالحرف \( s \): $$ "kitten" \rightarrow "sitten" $$
2. استبدال
   استبدال الحرف \( e \) بالحرف \( i \): $$ "sitten" \rightarrow "sittin" $$
3. إدراج
   إدراج الحرف \( g \) في نهاية الكلمة: $$ "sittin" \rightarrow "sitting" $$

يتطلب هذا التحويل ثلاث عمليات فقط: عمليتا استبدال وعملية إدراج واحدة. لذلك فإن مسافة ليفنشتاين بين "kitten" و"sitting" تساوي 3.

لتمثيل هذه العملية، يمكن إنشاء مصفوفة أبعادها \( (m+1) \times (n+1) \)، حيث يمثل \( m \) عدد أحرف "kitten" (6)، ويمثل \( n \) عدد أحرف "sitting" (7).

وتُضاف صفوف وأعمدة إضافية لتمثيل التحويلات من السلسلة النصية الفارغة وإليها.

تمثل الخلية \( (0, j) \) تكلفة تحويل السلسلة الفارغة إلى الجزء الأول من الكلمة "sitting" حتى الموضع \( j \)، ولذلك تزداد التكلفة تدريجيًا من 0 إلى 7.

وبالمثل، تمثل الخلية \( (i, 0) \) تكلفة تحويل الجزء الأول من الكلمة "kitten" حتى الموضع \( i \) إلى سلسلة فارغة، ولذلك تزداد التكلفة من 0 إلى 6.

عند حساب قيمة كل خلية \( (i, j) \)، تؤخذ ثلاث حالات في الاعتبار:

1. حذف حرف من "kitten"، وتكون التكلفة مساوية لقيمة الخلية العلوية مضافًا إليها 1.
2. إدراج حرف في "kitten"، وتكون التكلفة مساوية لقيمة الخلية اليسرى مضافًا إليها 1.
3. استبدال حرف، وتكون التكلفة مساوية لقيمة الخلية القطرية إذا كان الحرفان مختلفين، أما إذا كانا متطابقين فلا تُضاف أي تكلفة.

بعد ذلك تُملأ المصفوفة خطوة بخطوة:

فعلى سبيل المثال، يؤدي تحويل السلسلة الفارغة إلى "s" ثم "si" ثم "sit" إلى زيادة التكلفة بمقدار 1 مع كل عمود.

وبالمثل، يؤدي تحويل "k" ثم "ki" ثم "kit" إلى سلسلة فارغة إلى زيادة التكلفة بمقدار 1 مع كل صف.

• تمثل الخلية (1,1) تكلفة تحويل "k" إلى "s"، وهي 1، لأن العملية المطلوبة هي استبدال حرف واحد فقط (k→s).
  
• تمثل الخلية (2,2) تكلفة تحويل "ki" إلى "si"، وتبقى مساوية لـ1 لأن الحرف الثاني متطابق (i).
• تمثل الخلية (3,3) تكلفة تحويل "kit" إلى "sit"، وتظل مساوية لـ1 لأن الحرف الثالث متطابق (t).
• تمثل الخلية (4,4) تكلفة تحويل "kitt" إلى "sitt"، وهي أيضًا 1 لأن الحرف الرابع متطابق (t).
• تمثل الخلية (5,5) تكلفة تحويل "kitte" إلى "sitti"، وتساوي 2 بسبب عملية استبدال واحدة (e→i).
  
• تمثل الخلية (6,6) تكلفة تحويل "kitten" إلى "sittin"، وتبقى مساوية لـ2 لأن الحرف السادس متطابق (n).
• تمثل الخلية (6,7) تكلفة تحويل "kitten" إلى "sitting"، وتصبح 3 لأنه يجب إدراج الحرف الإضافي (g).
  

وبذلك نصل إلى الخلية الأخيرة في المصفوفة، وهي التي تحتوي على النتيجة النهائية.

فالخلية الواقعة في أسفل يمين المصفوفة \( (6,7) \) تمثل أقل تكلفة لتحويل "kitten" إلى "sitting"، وهي 3.

وهذه القيمة هي مسافة ليفنشتاين نفسها، لأنها تمثل الحد الأدنى من عمليات التحرير المطلوبة: عمليتا استبدال (`k → s` و`e → i`) وعملية إدراج واحدة (`g`).

الطوبولوجيا المستحثة بمسافة ليفنشتاين

تُعرِّف مسافة ليفنشتاين فضاءً متريًا على مجموعة السلاسل النصية، تمامًا كما تفعل مسافة هامينغ، لأنها تحقق الخصائص الأساسية التي يجب أن تستوفيها أي مسافة في الفضاءات المترية.

1. عدم السلبية: تكون مسافة ليفنشتاين بين سلسلتين نصيتين \( x \) و\( y \) دائمًا أكبر من أو مساوية للصفر، كما أن \( D_L(x, y)=0 \) إذا وفقط إذا كان \( x=y \). وهذا يعني أن السلسلة النصية لا تحتاج إلى أي عملية تحرير لتحويلها إلى نفسها، ولذلك لا تكون المسافة صفرًا إلا إذا كانت السلسلتان متطابقتين.
2. التناظر: تتمتع مسافة ليفنشتاين بخاصية التناظر، أي إن \( D_L(x, y)=D_L(y, x) \). فعدد عمليات التحرير اللازمة لتحويل \( x \) إلى \( y \) يساوي عدد العمليات اللازمة لتحويل \( y \) إلى \( x \)، لأن عمليات الإدراج والحذف والاستبدال يمكن تطبيقها في كلا الاتجاهين.
3. متباينة المثلث: تحقق مسافة ليفنشتاين متباينة المثلث، أي إن \( D_L(x, z)\le D_L(x, y)+D_L(y, z) \). وبعبارة أخرى، لا يمكن أن تكون المسافة المباشرة بين \( x \) و\( z \) أكبر من المسافة الناتجة عن المرور عبر سلسلة وسيطة \( y \). ويرجع ذلك إلى أن أي تسلسل من عمليات التحرير اللازمة لتحويل \( x \) إلى \( z \) يمكن تقسيمه إلى مرحلتين: من \( x \) إلى \( y \)، ثم من \( y \) إلى \( z \).

وبفضل هذه الخصائص، تولِّد مسافة ليفنشتاين فضاءً متريًا على السلاسل النصية.

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

إذا اخترنا نصف قطر \( r \) وسلسلة نصية \( x \)، فإن الكرة المفتوحة ذات المركز \( x \) تُعرَّف بأنها مجموعة جميع السلاسل النصية \( y \) التي تقل مسافة ليفنشتاين بينها وبين \( x \) عن \( r \):

$$ B(x,r)=\{\,y\mid D_L(x,y)<r\,\} $$

وتنشأ المجموعات المفتوحة في هذه الطوبولوجيا من اتحادات الكرات المفتوحة.

يُستخدم هذا الإطار الرياضي في العديد من التطبيقات العملية التي تعتمد على قياس درجة التقارب بين السلاسل النصية. فعلى سبيل المثال، في أنظمة التصحيح الإملائي الآلي، يمكن اقتراح كلمة من القاموس إذا كانت تفصلها عن الكلمة التي أدخلها المستخدم مسافة ليفنشتاين صغيرة.

وبذلك يمكن التعامل مع السلاسل النصية بوصفها عناصر في فضاء متري، والاستفادة من الطوبولوجيا المترية المستحثة لدراسة مفهوم التقارب بينها.

مثال عملي

لنفترض أن لدينا المجموعة \( X \) المكونة من السلاسل النصية التالية، وكل سلسلة فيها تتألف من ثلاثة أحرف:

$$ X=\{\text{"cat"},\ \text{"bat"},\ \text{"cut"}\} $$

سنبني أساسًا للطوبولوجيا باستخدام كرات مفتوحة نصف قطرها \( r=2 \)، تتمركز عند كل عنصر من عناصر المجموعة \( X \).

$$ B(x,r)=\{\,y\mid D_L(x,y)<r\,\} $$

وبما أن نصف القطر يساوي \(2\)، فإن كل كرة مفتوحة تضم جميع السلاسل النصية التي تقل مسافة ليفنشتاين بينها وبين مركز الكرة عن 2، أي السلاسل التي يمكن الوصول إليها بعملية تحرير واحدة على الأكثر.

ملاحظة: بما أن الكرة مفتوحة، فهي لا تتضمن نقاط الحد. لذلك يكون الشرط هو: $$ B(x,2)=\{\,y\mid D_L(x,y)<2\,\}. $$ أما إذا أردنا تعريف مجموعة مغلقة تشمل نقاط الحد أيضًا، فنستخدم: $$ C(x,2)=\{\,y\mid D_L(x,y)\le2\,\}. $$ وفي هذه الحالة تضم المجموعة جميع السلاسل النصية التي لا تزيد مسافة ليفنشتاين بينها وبين المركز على عمليتي تحرير.

لنحسب الآن الكرات المفتوحة ذات نصف القطر \(2\) لكل عنصر من عناصر المجموعة \(X\):

1. الكرة المفتوحة ذات المركز "cat" $$ B(\text{"cat"},2)=\{\text{"cat"},\text{"bat"},\text{"cut"}\}. $$ فالمسافة بين "cat" و"bat" تساوي 1، وكذلك المسافة بين "cat" و"cut"، ولذلك تنتمي السلسلتان إلى هذه الكرة المفتوحة.
2. الكرة المفتوحة ذات المركز "bat" $$ B(\text{"bat"},2)=\{\text{"bat"},\text{"cat"}\}. $$ إذ يمكن تحويل "bat" إلى "cat" بعملية استبدال واحدة فقط، بينما يتطلب تحويلها إلى "cut" عمليتي استبدال، ولذلك لا تنتمي "cut" إلى هذه الكرة.
3. الكرة المفتوحة ذات المركز "cut" $$ B(\text{"cut"},2)=\{\text{"cut"},\text{"cat"}\}. $$ فالمسافة بين "cut" و"cat" تساوي 1، في حين أن المسافة بينها وبين "bat" تساوي 2، ولذلك لا تدخل "bat" ضمن الكرة المفتوحة.

وتشكل الكرات المفتوحة \( B(\text{"cat"},2) \)، و\( B(\text{"bat"},2) \)، و\( B(\text{"cut"},2) \) أساسًا للطوبولوجيا المستحثة بمسافة ليفنشتاين عند اختيار نصف القطر \( r=2 \).

وانطلاقًا من هذا الأساس، يمكن توليد جميع المجموعات المفتوحة الأخرى باعتبارها اتحادات اعتباطية لهذه الكرات المفتوحة.

فعلى سبيل المثال، لننظر إلى اتحاد الكرتين المفتوحتين:

$$ B(\text{"bat"},2)\cup B(\text{"cut"},2). $$

وبما أن:

$$ B(\text{"bat"},2)=\{\text{"bat"},\text{"cat"}\}, $$

و

$$ B(\text{"cut"},2)=\{\text{"cut"},\text{"cat"}\}, $$

فإن:

$$ B(\text{"bat"},2)\cup B(\text{"cut"},2)=\{\text{"cat"},\text{"bat"},\text{"cut"}\}. $$

وهذه المجموعة تمثل بدورها مجموعة مفتوحة أخرى في هذه الطوبولوجيا.

وبهذه الطريقة نحصل على طوبولوجيا مترية مستحثة على المجموعة \( X \) بواسطة مسافة ليفنشتاين، حيث يمكن إنشاء أي مجموعة مفتوحة باعتبارها اتحادًا لعناصر هذا الأساس.

ويمكن متابعة بناء بقية المجموعات المفتوحة بالطريقة نفسها.