فاصله لونشتاین (Levenshtein Distance) چیست؟ آموزش Edit Distance با Dynamic Programming

Levenshtein Distance که معمولاً با عنوان Edit Distance نیز شناخته می‌شود، معیاری برای اندازه‌گیری میزان تفاوت میان دو رشته است.

ایده اصلی بسیار ساده است:

حداقل چند عملیات لازم است تا یک رشته را به رشته دیگری تبدیل کنیم؟

در نسخه استاندارد Levenshtein سه عملیات مجاز داریم:

• Insert — اضافه کردن یک کاراکتر
• Delete — حذف یک کاراکتر
• Replace — جایگزینی یک کاراکتر

هر عملیات معمولاً هزینه 1 دارد.

برای مثال:

cat
↓
cut

فقط کافی است a را با u جایگزین کنیم.

بنابراین:

Levenshtein Distance = 1

---

یک مثال معروف

دو رشته زیر را در نظر بگیرید:

kitten
sitting

می‌توانیم تبدیل را این‌طور انجام دهیم:

kitten
↓ Replace k → s
sitten
↓ Replace e → i
sittin
↓ Insert g
sitting

در مجموع سه عملیات انجام شده است:

Levenshtein Distance = 3

این مقدار حداقل تعداد عملیات لازم است.

---

چرا مقایسه ساده کافی نیست؟

در Hamming Distance فقط موقعیت‌های متناظر را مقایسه می‌کردیم و دو رشته باید طول برابر می‌داشتند.

اما در Levenshtein Distance می‌توانیم رشته‌هایی با طول متفاوت داشته باشیم.

مثلاً:

cat
cats

فقط یک Insert لازم داریم:

cat → cats

پس:

Distance = 1

این ویژگی باعث می‌شود Levenshtein برای Spell Checking، Fuzzy Search و مقایسه متن بسیار کاربردی‌تر باشد.

---

مسئله را چگونه حل کنیم؟

فرض کنید دو رشته داریم:

word1 = "horse"
word2 = "ros"

می‌خواهیم کمترین تعداد عملیات را پیدا کنیم.

برای این کار معمولاً از Dynamic Programming استفاده می‌کنیم.

یک ماتریس تعریف می‌کنیم که:

dp[i][j]

نشان می‌دهد حداقل هزینه تبدیل:

word1[0 ... i-1]

به:

word2[0 ... j-1]

چقدر است.

---

Base Caseها

اگر رشته اول خالی باشد:

"" → "abc"

باید سه کاراکتر Insert کنیم.

بنابراین:

dp[0][j] = j

اگر رشته دوم خالی باشد:

"abc" → ""

باید تمام کاراکترها حذف شوند:

dp[i][0] = i

این مقادیر سطر و ستون اول جدول DP را تشکیل می‌دهند.

---

رابطه اصلی Dynamic Programming

اگر دو کاراکتر فعلی برابر باشند:

word1[i - 1] === word2[j - 1]

هیچ عملیات جدیدی لازم نیست:

dp[i][j] = dp[i - 1][j - 1]

اما اگر متفاوت باشند، سه انتخاب داریم.

Insert

dp[i][j - 1] + 1

Delete

dp[i - 1][j] + 1

Replace

dp[i - 1][j - 1] + 1

پس:

dp[i][j] = 1 + min(
    dp[i - 1][j],
    dp[i][j - 1],
    dp[i - 1][j - 1]
)

---

مثال ساده با جدول DP

فرض کنید:

word1 = cat
word2 = cut

جدول اولیه:

      ""  c  u  t
""     0  1  2  3
c      1
 a     2
 t     3

پس از تکمیل جدول:

      ""  c  u  t
""     0  1  2  3
c      1  0  1  2
a      2  1  1  2
t      3  2  2  1

آخرین خانه:

dp[3][3] = 1

پس فاصله میان cat و cut برابر 1 است.

---

پیاده‌سازی TypeScript

function levenshteinDistance(a: string, b: string): number {
  const rows = a.length + 1;
  const cols = b.length + 1;

  const dp: number[][] = Array.from(
    { length: rows },
    () => new Array(cols).fill(0)
  );

  for (let i = 0; i < rows; i++) {
    dp[i][0] = i;
  }

  for (let j = 0; j < cols; j++) {
    dp[0][j] = j;
  }

  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],
          dp[i][j - 1],
          dp[i - 1][j - 1]
        );
      }
    }
  }

  return dp[a.length][b.length];
}

console.log(
  levenshteinDistance("kitten", "sitting")
); // 3

---

پیچیدگی زمانی و فضایی

اگر طول رشته اول n و رشته دوم m باشد:

Time Complexity: O(n × m)
Space Complexity: O(n × m)

زیرا تقریباً برای هر ترکیب از موقعیت‌های دو رشته یک Cell محاسبه می‌کنیم.

---

آیا می‌توان Space Complexity را کاهش داد؟

بله.

برای محاسبه هر Row فقط به Row قبلی نیاز داریم.

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

می‌توانیم Space Complexity را به:

O(min(n, m))

کاهش دهیم.

نمونه TypeScript:

function levenshteinOptimized(a: string, b: string): number {
  if (a.length < b.length) {
    [a, b] = [b, a];
  }

  let previous = Array.from(
    { length: b.length + 1 },
    (_, i) => i
  );

  for (let i = 1; i <= a.length; i++) {
    const current = new Array(b.length + 1);
    current[0] = i;

    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        current[j] = previous[j - 1];
      } else {
        current[j] = 1 + Math.min(
          previous[j],
          current[j - 1],
          previous[j - 1]
        );
      }
    }

    previous = current;
  }

  return previous[b.length];
}

---

Levenshtein Distance در Spell Checker

فرض کنید کاربر کلمه زیر را تایپ کرده است:

programing

ولی در Dictionary این کلمات وجود دارند:

programming
programmer
processing

می‌توانیم فاصله کاربر با هر کلمه را محاسبه کنیم.

کلمه‌ای که Levenshtein Distance کمتری دارد احتمالاً پیشنهاد مناسب‌تری است.

مثلاً:

programing → programming = 1

زیرا فقط یک m کم است.

---

کاربرد در Fuzzy Search

گاهی کاربر دقیقاً عبارت موجود در Database را وارد نمی‌کند.

برای مثال نام مشتری:

Alexander

ولی جستجو می‌کند:

Alexnder

Exact Matching ممکن است هیچ نتیجه‌ای برنگرداند.

اما با Edit Distance متوجه می‌شویم که دو عبارت بسیار نزدیک‌اند.

این ایده در سیستم‌هایی مانند:

• Search
• CRM
• Contact Matching
• Product Search
• Deduplication

کاربرد دارد.

---

کاربرد در Data Cleaning و Deduplication

فرض کنید در CRM دو رکورد داریم:

Arian Soleimanzadeh
Arian Soleimanzade

ممکن است این دو رکورد متعلق به یک نفر باشند ولی به دلیل Typo دو بار ثبت شده باشند.

Levenshtein Distance می‌تواند یکی از Signalهای تشخیص Duplicate باشد.

البته در سیستم واقعی معمولاً نباید فقط بر اساس نام تصمیم بگیریم؛ داده‌هایی مانند Email، Phone و سایر ویژگی‌ها نیز باید بررسی شوند.

---

کاربرد در NLP

Levenshtein Distance در بعضی مسائل پردازش زبان طبیعی برای مقایسه Tokenها یا Sequenceها استفاده می‌شود.

برای مثال:

• Typo Detection
• Text Normalization
• OCR Correction
• Transliteration Matching
• Approximate String Matching

---

کاربرد در DNA و Bioinformatics

رشته‌های DNA را می‌توان مانند Sequenceهای متنی تصور کرد.

برای مثال:

ACGTAC
ACGTC

Edit Distance می‌تواند میزان اختلاف میان دو Sequence را اندازه‌گیری کند.

البته مسائل واقعی Bioinformatics معمولاً الگوریتم‌ها و Cost Modelهای تخصصی‌تری دارند.

---

Levenshtein Distance و Hamming Distance

Hamming Distance فقط اختلاف موقعیت‌های متناظر را می‌شمارد و در تعریف استاندارد ورودی‌ها باید هم‌طول باشند.

Hamming:
cat
cut
Distance = 1

اما:

cat
cats

برای Hamming استاندارد مناسب نیست.

Levenshtein می‌گوید:

Insert s
Distance = 1

بنابراین Levenshtein انعطاف بیشتری دارد ولی محاسبه آن گران‌تر است.

---

Levenshtein و Longest Common Subsequence

این دو مسئله ارتباط مفهومی نزدیکی دارند، زیرا هر دو معمولاً با Dynamic Programming حل می‌شوند.

اما هدف متفاوت است.

Levenshtein می‌پرسد:

حداقل چند Edit لازم است؟

در حالی که LCS می‌پرسد:

طول بلندترین زیرتوالی مشترک چقدر است؟

درک این تفاوت در مسائل مصاحبه بسیار مهم است.

---

Weighted Edit Distance چیست؟

همیشه لازم نیست هزینه Insert، Delete و Replace برابر 1 باشد.

مثلاً می‌توانیم تعریف کنیم:

Insert  = 1
Delete  = 1
Replace = 2

یا در یک Keyboard Correction System، جایگزینی کلیدهای نزدیک هزینه کمتری داشته باشد.

مثلاً اشتباه:

hello → helo

ممکن است Cost متفاوتی نسبت به یک تغییر کاملاً نامرتبط داشته باشد.

این نسخه‌ها به Weighted Edit Distance معروف‌اند.

---

یک سؤال رایج مصاحبه

صورت مسئله:

دو رشته word1 و word2 داده شده‌اند. حداقل تعداد عملیات Insert، Delete و Replace را برای تبدیل word1 به word2 پیدا کنید.

مثلاً:

word1 = horse
word2 = ros

پاسخ:

3

این مسئله نمونه کلاسیک Dynamic Programming است.

---

چرا Greedy به‌سادگی جواب نمی‌دهد؟

ممکن است تصور کنیم در هر mismatch بهترین عملیات فعلی را انتخاب کنیم.

اما یک انتخاب محلی می‌تواند روی ادامه رشته اثر بگذارد.

به همین دلیل باید حالت‌های مختلف Insert، Delete و Replace را مقایسه کنیم.

Dynamic Programming نتیجه مسائل کوچک‌تر را ذخیره می‌کند تا بهترین مسیر کلی پیدا شود.

---

اشتباهات رایج در پیاده‌سازی

اشتباه در Indexها

در جدول DP، موقعیت i معمولاً مربوط به:

a[i - 1]

است، زیرا Row صفر برای رشته خالی استفاده شده است.

فراموش کردن Base Caseها

سطر و ستون اول باید به شکل صحیح مقداردهی شوند.

اضافه کردن هزینه هنگام Match

اگر دو کاراکتر برابر باشند:

dp[i][j] = dp[i - 1][j - 1]

و نباید 1 اضافه کنیم.

اشتباه گرفتن Insert و Delete

درک معنای Cellهای مجاور بسیار مهم است:

up       → Delete
left     → Insert
diagonal → Replace

---

چه زمانی Levenshtein انتخاب خوبی نیست؟

اگر میلیون‌ها رشته را بخواهیم با یک Query مقایسه کنیم، اجرای مستقیم Edit Distance برای همه آن‌ها ممکن است بسیار گران باشد.

در سیستم‌های Search واقعی معمولاً ابتدا Candidateها با روش‌هایی مانند:

• Indexing
• Prefix Filtering
• N-grams
• Trigrams
• Search Engines

محدود می‌شوند و سپس Similarity دقیق‌تر محاسبه می‌شود.

بنابراین Levenshtein یک ابزار مهم است، اما همیشه نباید آن را روی کل Dataset به صورت Brute Force اجرا کرد.

---

جمع‌بندی

Levenshtein Distance حداقل تعداد عملیات Insert، Delete و Replace برای تبدیل یک رشته به رشته دیگر را محاسبه می‌کند.

نسخه استاندارد آن یکی از مثال‌های کلاسیک Dynamic Programming است.

Operations:
Insert
Delete
Replace

Time:  O(n × m)
Space: O(n × m)

و با بهینه‌سازی حافظه می‌توان Space را به:

O(min(n, m))

کاهش داد.

مهم‌ترین نکته این است که Levenshtein فقط یک الگوریتم دانشگاهی نیست؛ مفاهیم آن در Spell Checking، Fuzzy Search، CRM Deduplication، Data Cleaning، NLP، OCR و بسیاری از سیستم‌های واقعی کاربرد دارند.