منبع اصلی نوشتار زیر در این لینک قرار دارد

کلمات مشابه

گاهی لازم میشه که شما میخواید از توی یه لیست از کلمات یه سری کلمه رو که شبیه تر هستن به کلمات دیگه، جدا کنید. توی PHP یه سری تابع برای اینکار معرفی شده (و البته MySQL هم تابعی داره براش) ولی متاسفانه جز یکی از این توابع باقی برای زبان فارسی کار نمیکنن.
من امروز قصد دارم همون ها رو معرفی کنم با یه مثال ساده، در حال حاضر هم (اگه اینهمه مشغله الکی بذاره) میخوام نسخه فارسی یکی از این توابع رو بنویسم.
اولین تابع levenshtein هستش که فاصله دو کلمه رو بر اساس نحوه جایگذاری حروف پیدا میکنه. اطلاعات بیشتر رو توی wiki مربوط به همین الگوریتم ببینید. این تابع برای فارسی هم کم و بیش کار میکنه، هر وقت دو رشته کاملا برابر باشن، بازگشتی صفر میشه و در غیر اینصورت بازگشتی تغییر میکنه هر چی اختلاف بیشتره عدد هم بزرگتره. اینهم مثالی که توی خود راهنمای تابع نوشته شده :

<?php
// input misspelled word
$input = 'carrrot';

// array of words to check against
$words  = array('apple','pineapple','banana','orange',
                'radish','carrot','pea','bean','potato');

// no shortest distance found, yet
$shortest = -1;

// loop through words to find the closest
foreach ($words as $word) {

    // calculate the distance between the input word,
    // and the current word
    $lev = levenshtein($input, $word);

    // check for an exact match
    if ($lev == 0) {

        // closest word is this one (exact match)
        $closest = $word;
        $shortest = 0;

        // break out of the loop; we've found an exact match
        break;
    }

    // if this distance is less than the next found shortest
    // distance, OR if a next shortest word has not yet been found
    if ($lev <= $shortest || $shortest < 0) {
        // set the closest match, and shortest distance
        $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?

این تابع وقتی بحث مقایسه پیش میاد انتخاب خوبیه. اما فرض کنید که میخوایم از توی دیتابیس اینکار رو انجام بدیم، نیاز به یه Stored Procedure احساس میشه :)
من یکی تو این آدرس پیدا کردم که برای من جواب داد (کم و بیش) :

delimiter //

CREATE FUNCTION LEVENSHTEIN (s1 VARCHAR(255), s2 VARCHAR(255))
  RETURNS INT
    DETERMINISTIC
      BEGIN
        DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
        DECLARE s1_char CHAR;
        DECLARE cv0, cv1 VARBINARY(256);
        SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
        IF s1 = s2 THEN
          RETURN 0;
        ELSEIF s1_len = 0 THEN
          RETURN s2_len;
        ELSEIF s2_len = 0 THEN
          RETURN s1_len;
        ELSE
          WHILE j <= s2_len DO
            SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
          END WHILE;
          WHILE i <= s1_len DO
            SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
            WHILE j <= s2_len DO
                SET c = c + 1;
                IF s1_char = SUBSTRING(s2, j, 1) THEN SET cost = 0; ELSE SET cost = 1; END IF;
                SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
                IF c > c_temp THEN SET c = c_temp; END IF;
                SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
                IF c > c_temp THEN SET c = c_temp; END IF;
                SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
            END WHILE;
            SET cv1 = cv0, i = i + 1;
          END WHILE;
        END IF;
        RETURN c;
      END//

– اون که اول delimiter رو تغییر دادم لازمه تا کد درست کار کنه.
با اضافه کردن این تابع به پایگاه داده (که توی MySQL 5 به بالا هم کار میکنه فقط) اونوقت شما میتونید از این استفاده کنید برای پیدا کردن اسامی مشابه توی پایگاه داده.
مثلا :

SELECT user_name FROM mytable WHERE LEVENSHTEIN('admin',user_name)<3 

اینجوری تمام نامهای توی فیلد که حداکثر سه تفاوت با نام admin دارن پیدا میشن.
خوب این روش رو من بیشتر پسندیدم چون با فارسی خوب کار کرد. اما مشکل اینه که یه کم کنده.
برای انگلیسی الگوریتم soundex وجود داره، که PHP هم تابع soundex و MySQL هم تابع SOUNDEX رو براش معرفی میکنن.

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

اما تابع بعدی تابع similar_text هستش، که برعکس تابع levenshtein هر چی شباهت بیشتر باشه عدد بزرگتری رو به عنوان بازگشتی برمیگردونه، این تابع هم با فارسی کار میکنه، بد هم نیست.
آخرین تابع این سری تابع metaphone هستش که باز هم برای انگلیسی کار میکنه و شبیه soundex عمل میکنه. منتها بر خلاف soundex از قواعد فونوتیک هم اطلاعاتی داره، و نتیجه استفاده از این تابع خیلی به واقعیت نزدیکتره تا soundex.

– اما علت نوشتن این متن، من قصد دارم روی یه تابع مشابه کار کنم برای فارسی، اگه کسی ایده ای داره، یا اینکه میدونه جایی کد GPL یا چیزی تو این مایه ها (نه کد غیر آزاد) هست برای فارسی یا حتی عربی، اینجا بگه.



برچسب ها : , , , , , ,

به سیاره لینوکس امتیاز دهید

به اين صفحه امتياز دهيد