فاصله Levenshtein
Levenshtein DistanceLevenshtein Distance حداقل تعداد insert، delete و substitute تک‌کاراکتری برای تبدیل یک رشته به رشته دیگر است.
اول این مفهوم را در ذهن نگه دار
Levenshtein Distance حداقل تعداد insert، delete و substitute تک‌کاراکتری برای تبدیل یک رشته به رشته دیگر است.
چطور کار می‌کند؟ ساده و مرحله‌ای
در DP معمولاً dp[i][j] فاصله ویرایشی prefixهای طول i و j را نگه می‌دارد.
اگر کاراکترها برابر باشند مقدار قطری می‌آید؛ وگرنه 1 + minimum از insert/delete/replace محاسبه می‌شود.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
فرض‌های Unicode، case و normalization را روشن کن.
indexها یا prefix state را تعریف کن.
اگر الگوریتم اجازه می‌دهد اطلاعات match قبلی را reuse کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای فاصله Levenshtein هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
O(mn)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی جست‌وجو روی متن بزرگ یا تکراری است و روش naive گران می‌شود از الگوریتم تخصصی استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- نادیده گرفتن Unicode.
- قاطی کردن Substring و Subsequence.
- خطای index/prefix.
مدل یک پاسخ حرفه‌ای
قبل از recurrence دقیقاً state جدول DP را تعریف کن؛ این کار جواب را قابل‌فهم می‌کند نه حفظی.
فاصله Levenshtein چه مسئله‌ای را حل می‌کند؟
Levenshtein Distance حداقل تعداد insert، delete و substitute تک‌کاراکتری برای تبدیل یک رشته به رشته دیگر است.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(mn) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نادیده گرفتن Unicode.