محاسبه فاصله لِوِن‌اِشتاین؛ یافتن کلمات مشابه در پی اچ پی

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

از اونجایی که اکثر جستجوها دچار اشتباه تایپی و نگارشی بود و یا از نگارشهای مختلف برای رسیدن به خواسته ها توسط کاربرها استفاده میشد (سرچ ها رو لاگ میکردیم) و معمولا سیستم نتیجه ای رو به کاربر نشون نمیداد و از لحاظ تجربه کاربری این خیلی خیلی برای سایت گرون تموم میشد، پس دست به کار شدیم و شروع کردیم توی گوگل به تحقیق و تفحص و خلاصه کار به شکل زیر شد.

فاصله لون‌اشتاین

از ویکی‌پدیا، دانشنامهٔ آزاد

فاصله لون‌اشتاین یا فاصله ویرایش در نظریه داده و علوم کامپیوتر متری برای محاسبه میزان تفاوت میان دو رشته است.

فاصله لون‌اشتاین بین دو رشته بوسیله کمترین تعداد عملیات مورد نیاز برای تبدیل یک رشته به رشته دیگر معین می‌شود، که یک عملیات می‌تواند یک ضمیمه، یا جایگزینی یک کاراکتر باشد.تعمیم فاصله لون‌اشتاین (فاصله دامرا-لون‌اشتاین) اجازه ترانهش دو کاراکتر را به عنوان یک عملیات می‌دهد.

این معیار به افتخار ولادمیر لون‌اشتاین، که این فاصله را در سال ۱۹۵۶ مطرح کرد، نام گذاری شده‌است.

همچنین از این موضوع در برنامه‌هایی که نیاز به یافتن مقدار شباهت، یا تفاوت دو رشته را دارند، مانند مقابله گر املائی، استفاده می‌شود.

به عنوان مثال فاصله لوناشتاین بین "kitten" و "sitting" برابر 3 است. همانطور که می‌بینیم حداقل سه ویرایش برای تبدیل یکی به دیگری وجود دارد و کمتر از آن ممکن نیست:

  1. kitten → sitten(با جایگزینی 's' به جای 'k')
  2. sitten → sittin(با جایگزینی 'i' به جای 'e')
  3. sittin → sitting(با وارد کردن 'g' در انتها)

این موضوع را می‌توان به عنوان تعمیم فاصله همینگ در نظر گرفت، که برای رشته‌های هم اندازه استفاده می‌شد و فقط می‌توانستیم در آن از جایگزینی استفاده کنیم.

از این مفهوم برای تصحیح، غلط‌یابی و پیشنهاد دادن در موتورهای جست‌وجو استفاده می‌شود.


از توضیحات بالا مشخص شد که ما می تونیم از این نظریه به احتمال زیاد برای رفع مشکلمون استفاده کنیم و در نهایت یک تجربه کاربری بد که اکثر سرچها بدون نتیجه بود رو با یه پیشنهاد واژه تبدیل به تجربه بهتری برای کاربرها کنیم. پس دوباره گوگل کردیم و رسیدیم به تابع ()levenshtein در پی اچ پی.

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

 int levenshtein     ( string $str1    , string $str2    );

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

خوب پس با وجود این تابع ما احساس کردیم کار تمام و مشکلمون رفع شده، ولی بعد از اینکه تست زدیم فهمیدیم این تابع هم مثل اکثر توابع php با حروف فارسی و کاراکترهای اصطلاحا مولتی بایت (Multi Byte) مشکل داره و باید دوباره بگردیم برای راه حل!

یعنی مثلا برای دو کلمه "پنج" و "پنجی" نتیجه این تابع باید 1 میشد؛ ولی تابع عدد 2 رو برمیگردوند و این باعث خطای محاسباتی در پیشنهاد واژه میشد.

بعد از سرچ دوباره در نهایت رسیدیم به این تابع عالی به اسم mb_levenshtein() که یک کاربر احتمالا ژاپنی با نام کاربری @suin برای رفع همین مشکل برای کاراکترهای زبان ژاپنی نوشته و رایگان در اختیار همه قرار داده.

با استفاده از این تابع و ترکیبش با چندتا تابع دیگه و مقداری کدزنی مشکل ما رفع شد و از اونجایی که 120 عنوان محصول ثابت بیشتر نبود توی اون سایت هر بار که کاربری چیزی رو سرچ میکرد و نتیجه 0 می شد ما این تابع رو برای اون 120 محصول ران میکردیم و مقایسات و محاسبات صورت میگرفت و نزدیکترین واژه رو به کاربر به شکل "آیا منظور شما فلان بود؟" نشون میدادیم تا با کلیک روی اون احتمالا به نتیجه دلخواهش برسه.

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

http://php.net/manual/en/function.soundex.php

http://php.net/manual/en/function.metaphone.php

http://php.net/manual/en/function.similar-text.php

http://aurbano.eu/blog/2008/05/30/did-you-mean-in-php/

امیدوارم این تجربه به دردتون بخوره و مفید واقع بشه.
این مطلب فقط بازنشر یک تجربه بود و به هیچ عنوان ادعایی برای نوشتن یک سیستم پیشنهاد واژه در حد گوگل در آن مطرح نیست!