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

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

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

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

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

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

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

برای مثال:

Code

cat
↓
cut

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

بنابراین:

Code

Levenshtein Distance = 1

یک مثال معروف

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

Code

kitten
sitting

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

Code

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

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

Code

Levenshtein Distance = 3

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

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

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

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

مثلاً:

Code

cat
cats

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

Code

cat → cats

پس:

Code

Distance = 1

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

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

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

Code

word1 = "horse"
word2 = "ros"

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

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

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

Code

dp[i][j]

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

Code

word1[0 ... i-1]

به:

Code

word2[0 ... j-1]

چقدر است.

Base Caseها

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

Code

"" → "abc"

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

بنابراین:

Code

dp[0][j] = j

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

Code

"abc" → ""

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

Code

dp[i][0] = i

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

رابطه اصلی Dynamic Programming

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

Code

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

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

Code

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

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

Insert

Code

dp[i][j - 1] + 1

Delete

Code

dp[i - 1][j] + 1

Replace

Code

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

پس:

Code

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

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

فرض کنید:

Code

word1 = cat
word2 = cut

جدول اولیه:

Code

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

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

Code

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

آخرین خانه:

Code

dp[3][3] = 1

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

پیاده‌سازی TypeScript

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 باشد:

Code

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

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

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

بله.

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

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

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

Code

O(min(n, m))

کاهش دهیم.

نمونه TypeScript:

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

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

Code

programing

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

Code

programming
programmer
processing

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

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

مثلاً:

Code

programing → programming = 1

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

کاربرد در Fuzzy Search

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

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

Code

Alexander

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

Code

Alexnder

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

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

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

Search
CRM
Contact Matching
Product Search
Deduplication

کاربرد دارد.

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

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

Code

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های متنی تصور کرد.

برای مثال:

Code

ACGTAC
ACGTC

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

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

Levenshtein Distance و Hamming Distance

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

Code

Hamming:
cat
cut
Distance = 1

اما:

Code

cat
cats

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

Levenshtein می‌گوید:

Code

Insert s
Distance = 1

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

Levenshtein و Longest Common Subsequence

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

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

Levenshtein می‌پرسد:

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

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

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

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

Weighted Edit Distance چیست؟

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

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

Code

Insert  = 1
Delete  = 1
Replace = 2

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

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

Code

hello → helo

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

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

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

صورت مسئله:

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

مثلاً:

Code

word1 = horse
word2 = ros

پاسخ:

Code

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

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

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

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

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

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

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

اشتباه در Indexها

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

Code

a[i - 1]

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

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

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

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

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

Code

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

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

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

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

Code

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 است.

Code

Operations:
Insert
Delete
Replace

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

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

Code

O(min(n, m))

کاهش داد.

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

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

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

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

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

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

برای مثال:

Code

cat
↓
cut

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

بنابراین:

Code

Levenshtein Distance = 1

یک مثال معروف

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

Code

kitten
sitting

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

Code

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

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

Code

Levenshtein Distance = 3

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

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

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

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

مثلاً:

Code

cat
cats

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

Code

cat → cats

پس:

Code

Distance = 1

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

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

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

Code

word1 = "horse"
word2 = "ros"

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

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

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

Code

dp[i][j]

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

Code

word1[0 ... i-1]

به:

Code

word2[0 ... j-1]

چقدر است.

Base Caseها

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

Code

"" → "abc"

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

بنابراین:

Code

dp[0][j] = j

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

Code

"abc" → ""

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

Code

dp[i][0] = i

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

رابطه اصلی Dynamic Programming

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

Code

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

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

Code

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

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

Insert

Code

dp[i][j - 1] + 1

Delete

Code

dp[i - 1][j] + 1

Replace

Code

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

پس:

Code

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

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

فرض کنید:

Code

word1 = cat
word2 = cut

جدول اولیه:

Code

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

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

Code

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

آخرین خانه:

Code

dp[3][3] = 1

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

پیاده‌سازی TypeScript

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 باشد:

Code

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

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

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

بله.

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

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

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

Code

O(min(n, m))

کاهش دهیم.

نمونه TypeScript:

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

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

Code

programing

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

Code

programming
programmer
processing

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

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

مثلاً:

Code

programing → programming = 1

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

کاربرد در Fuzzy Search

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

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

Code

Alexander

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

Code

Alexnder

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

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

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

Search
CRM
Contact Matching
Product Search
Deduplication

کاربرد دارد.

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

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

Code

Arian Soleimanzadeh
Arian Soleimanzade

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

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

کاربرد در NLP

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

برای مثال:

Typo Detection
Text Normalization
OCR Correction
Transliteration Matching
Approximate String Matching

کاربرد در DNA و Bioinformatics

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

برای مثال:

Code

ACGTAC
ACGTC

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

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

Levenshtein Distance و Hamming Distance

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

Code

Hamming:
cat
cut
Distance = 1

اما:

Code

cat
cats

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

Levenshtein می‌گوید:

Code

Insert s
Distance = 1

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

Levenshtein و Longest Common Subsequence

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

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

Levenshtein می‌پرسد:

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

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

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

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

Weighted Edit Distance چیست؟

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

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

Code

Insert  = 1
Delete  = 1
Replace = 2

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

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

Code

hello → helo

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

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

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

صورت مسئله:

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

مثلاً:

Code

word1 = horse
word2 = ros

پاسخ:

Code

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

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

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

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

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

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

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

اشتباه در Indexها

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

Code

a[i - 1]

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

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

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

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

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

Code

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

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

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

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

Code

up       → Delete
left     → Insert
diagonal → Replace

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

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

Indexing
Prefix Filtering
N-grams
Trigrams
Search Engines

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

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

جمع‌بندی

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

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

Code

Operations:
Insert
Delete
Replace

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

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

Code

O(min(n, m))

کاهش داد.

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

یک مثال معروف

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

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

Base Caseها

رابطه اصلی Dynamic Programming

Insert

Delete

Replace

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

پیاده‌سازی TypeScript

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

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

Levenshtein Distance در Spell Checker

کاربرد در Fuzzy Search

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

کاربرد در NLP

کاربرد در DNA و Bioinformatics

Levenshtein Distance و Hamming Distance

Levenshtein و Longest Common Subsequence

Weighted Edit Distance چیست؟

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

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

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

اشتباه در Indexها

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

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

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

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

جمع‌بندی

B2B CRM و B2C CRM چه تفاوتی دارند؟ از فرآیند فروش تا معماری نرم‌افزار

الگوریتم Kosaraju چیست و اصلاً چه مشکلی را حل می‌کند؟

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

یک مثال معروف

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

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

Base Caseها

رابطه اصلی Dynamic Programming

Insert

Delete

Replace

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

پیاده‌سازی TypeScript

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

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

Levenshtein Distance در Spell Checker

کاربرد در Fuzzy Search

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

کاربرد در NLP

کاربرد در DNA و Bioinformatics

Levenshtein Distance و Hamming Distance

Levenshtein و Longest Common Subsequence

Weighted Edit Distance چیست؟

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

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

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

اشتباه در Indexها

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

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

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

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

جمع‌بندی

B2B CRM و B2C CRM چه تفاوتی دارند؟ از فرآیند فروش تا معماری نرم‌افزار

الگوریتم Kosaraju چیست و اصلاً چه مشکلی را حل می‌کند؟