فاصله لون اشتاین (Levenshtein distance) چیه؟!

فاصله لون اشتاین (Levenshtein distance) که به افتخار ولادیمیر لون اشتاین (Vladimir Levenshtein) ریاضیدان روسی نامگذاری شده و توی علوم کامپیوتر یه معیاری برای سنجش شباهت دو تا رشته هست. یه جورایی محاسبه میکنه که با حداقل چند تا اعمال میتونیم متن اول رو مثل متن دوم کنیم. اگه دقت کنیم میتونیم بفهمیم که این معیار کاربرد های خوبی داره. توی این مقاله قراره با الگوریتم، کاربرد هاش و پیاده سازیش آشنا بشیم.

کاربرد الگوریتم لون اشتاین

احتمالا چند تا از کاربرد هاش به ذهنتون اومده باشه. اینجا با اونا آشنا میشیم:

1. پیدا کردن غلط املایی: با الگوریتم فاصله لون اشتاین کلمه های متن رو با دیکشنری حساب میکنیم و اگه این فاصله بیشتر از یه مقداری بشه، احتمال غلط املایی بالاتر میره.
2. تصحیح کردن متن: همونجور که توی پیدا کردن غلط املایی فهمیدیم، اینجا هم میشه کلماتی که فاصله لون اشتاین کمتری دارن رو پیشنهاد بدیم.
3. پیشنهاد دادن کلمه: خب هممون دیدیم وقتی داریم تایپ میکنیم کیبورد کلمات پیشنهادی هم نشون میده. میتونیم فاصله لون اشتاین کلمه هایی که با کلمه تایپ شده کمتر هستن رو نشون بدیم.
4. تشخیص هویت: به این صورت که رمز عبور وارد شده توسط کاربر با رمز عبور ذخیره شده قبلی مقایسه میشه و اگه فاصله لون اشتاین اینا کمتر از یه مقداری بشه، هویت تایید میشه.
5. ترجمه ماشینی: این الگوریتم میتونه کلمات معادل در زبان های مختلف رو پیدا کنه.
6. بازیابی اطلاعات: اینجا هم عبارتی که جستجو میشه با عبارت های موجود توی اسناد مختلف مقایسه میشه و نزدیک ترین رو پیشنهاد میکنه.
7. خوشه بندی کردن: توی الگوریتم های طبقه بندی، داده هایی که فاصله کمتری دارن یه خوشه میشن.
8. تشخیص دادن تقلب: یکی از کاربرد های مهم این الگوریتم به شمار میاد.
9. ویرایش کردن ژن ها: پرکاربرد ترین الگوریتم هست که میتونه دو تا DNA رو مقایسه کنه.

الگوریتم لون اشتاین

برای اینکه درک الگوریتم آسون تر باشه مرحله به مرحله جلو میریم. خب این یه الگوریتم برنامه نویسی پویا (Dynamic Programming) هست و اگه طول دو تا رشته هامون a و b باشه، ماتریس مورد نظرمون ابعادش میشه (a+1) در (b+1) که بعدا توضیح میدیم چرا +1 کردیم.

سوال اینجوریه که دو تا رشته ورودی داریم. حداقل اعمالی که میتونیم روی رشته اول انجام بدیم به طوری که به رشته دومی برسیم چند تاست. اعمال هایی که میتونیم انجام بدیم:

1. یه کاراکتر حذف (delete) کنیم.
2. یه کاراکتر اضافه (insert) کنیم.
3. یه کاراکتر جایگزین (replace) کنیم.

خب با یه مثال بریم جلو. دو تا رشته abd و acd داریم. میخوایم رشته abd رو به acd تبدیل کنیم. خب دو تا پوینتر i و j میخوایم تا به کاراکتر های رشته اول و دوم اشاره کنه.

• خب کاراکتر های اول هر دو رشته a هست و برابره پس وقتی برابر میشه ما صفر اعمال نیاز داریم و پوینتر ها رو اینبار به i+1 و j+1 نشون میدیم. یعنی انگار میریم کاراکتر های بعدی رو مد نظر میگیریم.
• کاراکتر دوم b و c هست:

1. خب اگه کاراکتر b رو حذف کنیم اونوقت نیازه که پوینتر i رو یه واحد جلوتر ببریم ولی پوینتر j همچنان به c اشاره داره چون هنوز کاراکتری با اون برابر نشده پس i+1 و j میشه.
2. اگه کاراکتری رو اضافه کنیم (کاراکتر c رو بین a و b تو رشته اول قرار میدیم) اونوقت نیازه که پوینتر i همچنان به خونه b اشاره کنه ولی الان پوینتر j چون c الان توی رشته اول اضافه کردیم حل شد پس j+1 میشه و در نتیجه i و j+1 میشه.
3. اگه کاراکتری رو جایگزین کنیم (که کاراکتر c رو به جای b توی رشته اول جایگزین میکنیم) اونوقت هم باید i یه واحد بره جلوتر و هم j یه واحد بره جلوتر چون هر دو تا کاراکتر برابر میشن. پس i+1 و j+1 میشه.

خب سه تا حالت اولیه هم داریم:

1. اگه هر دو رشته تهی باشن تعداد اعمال 0 میشه.
2. اگه رشته اول تهی و رشته دوم کامل باشه تعداد اعمال به اندازه رشته دوم هست یعنی len(str2)
3. اگه رشته دوم تهی باشه و رشته اول کامل باشه تعداد اعمال به اندازه رشته اول میشه یعنی len(str1)

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

خب برای حل ما توی هر خانه به سه طرف نگاه میکنیم ببینیم تعداد اعمال توی کدوم سمت کمتره اون رو انتخاب میکنیم و با خودمون جمع میکنیم. مثلا توی خانه سطر d ستون d ما خانه های مجاور رو به 1 و 0 و 1 داریم و کمترینش 0 هست. پس انتخاب کرده و با خودمون که صفر هست جمع میکنیم. الان مثلا توی خانه سطر d و ستون c خانه های مجاور 0 و 1 و 2 هست که کمترین 1 هست و ...

شبه کد الگوریتم لون اشتاین

پیاده سازی الگوریتم

خب برای پیاده سازیش کافیه ماتریس رو بسازیم و مینیمم خانه هارو پیدا کنیم و مسئله رو حل کنیم.

def levenshtein_distance(word1, word2):
    len_word1 = len(word1)
    len2_word2 = len(word2)

    # ایجاد کردن جدول برای ذخیره کردن حالت ها
    dp = [[0 for _ in range(len_word2 + 1)] for _ in range(len_word1 + 1)]

    # مقدار دهی کردن جدول
    for i in range(len_word1 + 1):
        dp[i][0] = i  # کاراکتر های رشته اول
    for j in range(len_word2 + 1):
        dp[0][j] = j  # حذف همه کاراکتر های دومی از اولی

    # پر کردن جدول
    for i in range(1, len_word1 + 1):
        for j in range(1, len_word2 + 1):
            if word1[i - 1] == word2[j - 1]:
            # کاراکتر ها برابر اند
            dp[i][j] = dp[i - 1][j - 1]
            else:
           # یافتن کمترین اعمال
            dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1)

   return dp[len_word1][len_word2]

خب خروجی معروفی که همیشه از الگوریتم میگیرن فاصله دو تا کلمه kitten و sitting هست:

distance = levenshtein_distance(&quotkitten&quot, &quotsitting&quot)
print(f&quotThe edit distance between kitten and sitting is: {distance}&quot)

output:
ubuntu>Ehsan> python main.py
The edit distance between kitten and sitting is: 3

یعنی کاراکتر k رو با s جایگرین کردن، کاراکتر e رو حدف کردن و کاراکتر g اضافه کردن که 3 عمل میشه.

خب رسیدیم به آخر و امیداورم خوشت اومده باشه و به دردت خورده باشه.