تابع levenshtein() در PHP

تابع levenshtein() در PHP برای محاسبهٔ فاصلهٔ لِوِنش‌اشتاین میان دو رشته به‌کار می‌رود؛ یعنی حداقل تعداد عملیات درج (insert)، حذف (delete) یا جایگزینی (replace) که برای تبدیل یک رشته به رشتهٔ دیگر لازم است. این تابع ابزار قدرتمندی برای تشخیص شباهت رشته‌ها، پیاده‌سازی جستجوی فازی، تصحیح املا و مقایسهٔ داده‌های متنی است.

امضای تابع و پارامترها

• basic: levenshtein(string $str1, string $str2)
• with costs: levenshtein(string $str1, string $str2, int $cost_ins, int $cost_rep, int $cost_del)
• خروجی: یک عدد صحیح (>=0) که نشان‌دهندهٔ فاصله است.

ویژگی‌ها و محدودیت‌ها

• حساس به حروف بزرگ/کوچک — اگر می‌خواهید حساسیت را حذف کنید از mb_strtolower() یا strtolower() استفاده کنید.
• پیاده‌سازی بایت‌محور است — برای رشته‌های UTF-8 باید مراقب باشید چون ممکن است کاراکترهای چندبایتی شکسته شوند.
• پیچیدگی زمانی: O(n*m) (n طول اولین رشته، m طول دومین رشته).

مثال پایه

<?php
echo levenshtein("kitten", "sitting"); // خروجی 3
?>

این کد فاصلهٔ بین “kitten” و “sitting” را محاسبه می‌کند که سه عملیات لازم است (replace k→s, replace e→i, insert g).

کاربردهای معمول

• جستجوی فازی در لیست اسامی یا محصولات (پیشنهاد نزدیک‌ترین مورد)
• تطبیق داده‌های وارد شده توسط کاربر با رکوردهای پایگاه‌داده
• تصحیح املا و پیشنهادهای خودکار
• پاکسازی داده‌ها (deduplication) بر اساس شباهت رشته‌ها

مثال: پیدا کردن نزدیک‌ترین رشته از یک آرایه

<?php
$words = ['apple', 'apply', 'pineapple', 'apricot'];
$input = 'aple';

$closest = null;
$minDistance = PHP_INT_MAX;
foreach ($words as $word) {
    $d = levenshtein($input, $word);
    if ($d < $minDistance) {
        $minDistance = $d;
        $closest = $word;
    }
}

echo "Closest to $input is $closest with distance $minDistance";
?>

در این مثال برای هر کلمه فاصله محاسبه می‌شود و کمترین مقدار انتخاب می‌گردد تا نزدیک‌ترین رشته به ورودی پیدا شود.

بهبود عملکرد و محدود کردن محاسبات

برای مجموعه‌های بزرگ محاسبهٔ levenshtein برای همهٔ آیتم‌ها گران است. نکات بهینه‌سازی:

• قابلیت فیلتر بر اساس تفاوت طول: اگر اختلاف طول دو رشته بیشتر از حد آستانه باشد، می‌توان محاسبه را نادیده گرفت.
• استفادهٔ دو مرحله‌ای: ابتدا از soundex() یا metaphone() یا مقایسهٔ طول برای کاهش مجموعهٔ کاندیدها، سپس محاسبهٔ دقیق با levenshtein().
• اگر به نتایج بسیار سریع نیاز دارید از ساختارهایی مثل BK-tree یا الگوریتم‌های ایندکس‌بندی مشابه استفاده کنید.

نمونهٔ بهینه: محدود کردن بر اساس طول

<?php
$words = ['apple', 'apply', 'pineapple', 'apricot', 'ap'];
$input = 'aple';
$threshold = 2;

$closest = null;
$minDistance = PHP_INT_MAX;
foreach ($words as $word) {
    if (abs(strlen($word) - strlen($input)) > $threshold) continue;
    $d = levenshtein($input, $word);
    if ($d < $minDistance) {
        $minDistance = $d;
        $closest = $word;
    }
}
echo $closest;
?>

در این مثال ابتدا بر اساس اختلاف طول فیلتر انجام می‌شود و تنها کلمات نزدیک از نظر طول وارد محاسبهٔ دقیق می‌شوند؛ این کار در مجموعه‌های بزرگ کارایی را به‌شکل قابل‌توجهی بهبود می‌دهد.

مسئلهٔ حروف چندبایتی (UTF-8) و راه‌حل

تابع levenshtein بایت‌محور است، بنابراین در کار با متن‌های UTF-8 ممکن است به‌درستی عمل نکند و کاراکترهای چندبایتی را اشتباه بشکند. دو رویکرد اصلی برای رفع این مشکل:

• رشته‌ها را به آرایهٔ کاراکترها (grapheme clusters) بشکنید و الگوریتم Levenshtein را روی آرایه‌ها پیاده کنید.
• از توابع mb_ برای تبدیل به آرایهٔ کاراکتر استفاده کنید یا یک پیاده‌سازی سفارشی داشته باشید.

مثال سادهٔ حساس به UTF-8 (ساختِ آرایه کاراکتر با preg_split)

<?php
function mb_str_split_utf8($str) {
    return preg_split('//u', $str, -1, PREG_SPLIT_NO_EMPTY);
}

function levenshtein_mb($s1, $s2) {
    $a = mb_str_split_utf8($s1);
    $b = mb_str_split_utf8($s2);
    $n = count($a);
    $m = count($b);
    if ($n === 0) return $m;
    if ($m === 0) return $n;

    $d = array();
    for ($i = 0; $i <= $n; $i++) $d[$i] = $i;
    for ($j = 1; $j <= $m; $j++) {
        $prev = $d[0];
        $d[0] = $j;
        for ($i = 1; $i <= $n; $i++) {
            $temp = $d[$i];
            $cost = ($a[$i-1] === $b[$j-1]) ? 0 : 1;
            $d[$i] = min($d[$i] + 1, $d[$i-1] + 1, $prev + $cost);
            $prev = $temp;
        }
    }
    return $d[$n];
}

echo levenshtein_mb('سلام', 'سَلام');
?>

در این کد ابتدا رشته‌ها با preg_split('//u', ...) به آرایهٔ کاراکترهای UTF-8 تبدیل می‌شوند و سپس الگوریتم Levenshtein روی آن‌ها اجرا می‌شود تا نتیجهٔ صحیح برای زبان‌هایی مثل فارسی به‌دست آید.

مقایسهٔ سریع با توابع مشابه

نکات پایانی و بهترین شیوه‌ها

• برای ورودی‌های کاربر همیشه نرمال‌سازی انجام دهید (حروف بزرگ/کوچک، فاصله‌ها، نویسه‌های ترکیبی).
• برای داده‌های بزرگ از پیش‌فیلترها و ایندکس‌های مناسب استفاده کنید تا بار محاسباتی کاهش یابد.
• برای متن‌های غیرلاتین یا UTF-8 از نسخهٔ حساس به یونیکد استفاده کنید یا رشته‌ها را به کاراکترها تبدیل کنید.
• در انتخاب آستانهٔ پذیرش نتایج فازی واقع‌بین باشید؛ فاصلهٔ کم یعنی شباهت بیشتر ولی متناظر با کاربرد شما باید تنظیم شود.

تابع levenshtein() ابزاری ساده اما قدرتمند برای سنجش شباهت رشته‌هاست؛ فهم محدودیت‌ها، اعمال نرمال‌سازی مناسب و بهینه‌سازی روی مجموعه‌های بزرگ باعث می‌شود این تابع در بسیاری از پروژه‌ها کاربردی و مؤثر باشد.

لطفاً از کمبود ها و مشکلات این محتوا برای ما بنویسید

ارسال