PHP/levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7)

تقيس الدالة levenshtein()‎ مسافة Levenshtein بين سلسلتين نصيتين.

الوصف

int levenshtein ( string $str1 , string $str2 )

int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )

تُقاس مسافة Levenshtein بعدد المحارف الواجب استبدالها أو إضافتها أو حذفها لتحويل السلسلة النصية str1 إلى السلسلة النصية str2.

يُعَد تعقيد خوارزمية الدالة levenshtein()‎ من الدرجة (O(m*n، حيث تمثل m و n طول السلسلتين النصيتين str1 و str2 (الأمر الذي يعدّ جيدًا إلى حدٍ ما مقارنة مع درجة تعقيد خوارزمية الدالة similar_text()‎ التي تكون من الدرجة (O(max(n,m)**3، لكن مع ذلك ستبقى مُكلِفةً حسابيًا).

في نُسخَتِها المبسطة، تأخذ الدالة levenshtein()‎ السلسلتين النصيتين str1 و str2 كمعاملات  وتُعيد عدد المحارف الواجب استبدالها أو إضافتها أو حذفها لتحويل السلسلة النصية str1 إلى السلسلة النصية str2.

في نسختها الثانية تأخذ الدالة levenshtein()‎ ثلاث معاملات إضافية تحدد تكلفة كلٍ من عمليات  الاستبدال والحذف والإضافة. وهي نسخة أكثر شمولية من النسخة المبسطة لكن ليست بنفس الكفاءة.

المعاملات

str1

السلسلة النصية الأولى.

str2

السلسلة النصية الثانية.

cost_ins

يُعَرِف تكلفة إضافة المحارف.

cost_rep

يُعَرِف تكلفة استبدال المحارف.

cost_del

يُعَرِف تكلفة حذف المحارف.

القيم المعادة

تُعيد الدالة levenshtein()‎ مسافة Levenshtein بين المعاملين str1 و str2، أو القيمة (1-) إذا كان طول أحد السلسلتين str1 أو str2 يفوق عدد 255 حرف وهو عدد المحارف المسموح به.

أمثلة

المثال 1: مثال عن استعمالات الدالة levenshtein()‎ (تقديم اقتراحات لتصحيح الكلمات المُدخلة)

<?php

// كلمة مكتوبة خطأً
$input = 'carrrot';

// مصفوفة فيها كلمات للتحقق من كتابة المتغير السابق
$words  = array('apple','pineapple','banana','orange',
               'radish','carrot','pea','bean','potato');
// لم نجد أقصر طريق لتحويل السلسلة النصية الأولى إلى الثانية
$shortest = -1;

// المرور على عناصر المصفوفة لمعرفة أقرب الكلمات إلى الكلمة التي نريد مراجعتها
foreach ($words as $word) {
   // حساب المسافة بين الكلمة المدخلة والكلمة الحالية
   $lev = levenshtein($input, $word);
   // التحقق من وجود مطابقة كاملة
   if ($lev == 0) {
       // أقرب كلمة هي الكلمة الصحيحة (المماثلة لها تمامًا)
       $closest = $word;
       $shortest = 0;
       // الخروج من حلقة التكرار، إذ وجدنا مطابقة للكلمة
       break;
   }

   // إذا كانت المسافة أقل من المسافة التي حسبناها سابقًا
   // أو لم نجد كلمةً تشبهها
   if ($lev <= $shortest || $shortest < 0) {
       // ضبط أقرب كلمة تشبه الكلمة الأصل
       $closest  = $word;
       $shortest = $lev;
   }
}
echo "Input word: $input\n";
if ($shortest == 0) {
   echo "Exact match found: $closest\n";
} else {
   echo "Did you mean: $closest?\n";
}
?>

يُعيد المثال السابق ما يلي:

Input word: carrrot

Did you mean: carrot?

انظر أيضًا

• soundex()‎: حساب مفتاح soundex لسلسلة نصية.
• similar_text()‎: قياس درجة التشابه بين سلسلتين نصيتين.
• metaphone()‎: حساب مفتاح metaphone لسلسلة نصية.

مصادر

• صفحة الدالة levenshtein في توثيق PHP الرسمي.