Khoảng cách Levenshtein

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong các thuật toán của bộ môn khoa học máy tính, khái niệm Khoảng cách Levenshtein thể hiện khoảng cách khác biệt giữa 2 chuỗi kí tự. Khoảng cách Levenshtein giữa chuỗi S và chuỗi T là số bước ít nhất biến chuỗi S thành chuỗi T thông qua 3 phép biến đổi là

  • xoá 1 kí tự.
  • thêm 1 kí tự.
  • thay kí tự này bằng kí tự khác.

Khoảng cách này được đặt theo tên Vladimir Levenshtein, người đã đề ra khái niệm này vào năm 1965. Nó được sử dụng trong việc tính toán sự giống và khác nhau giữa 2 chuỗi, như chương trình kiểm tra lỗi chính tả của winword spellchecker. Ví dụ: Khoảng cách Levenshtein giữa 2 chuỗi "kitten" và "sitting" là 3, vì phải dùng ít nhất 3 lần biến đổi.

  1. kitten -> sitten (thay "k" bằng "s")
  2. sitten -> sittin (thay "e" bằng "i")
  3. sittin -> sitting (thêm kí tự "g")

Thuật toán[sửa | sửa mã nguồn]

Để tính toán Khoảng cách Levenshtein, ta sử dụng thuật toán quy hoạch động, tính toán trên mảng 2 chiều (n+1)*(m+1), với n, m là độ dài của chuỗi cần tính. Sau đây là đoạn mã (S, T là chuỗi cần tính khoảng cách, n, m là độ dài của chuỗi S, T):

   int LevenshteinDistance(char s[1..m], char t[1..n])
     // d is a table with m+1 rows and n+1 columns
     declare int d[0..m, 0..n]

     for i from 0 to m
         d[i, 0]:= i
     for j from 0 to n
         d[0, j]:= j

     for i from 1 to m
        for j from 1 to n
        {
          if s[i] = t[j] then cost:= 0
                         else cost:= 1
          d[i, j]:= minimum(
                               d[i-1, j] + 1,     // trường hợp xoá
                               d[i, j-1] + 1,     // trường hợp thêm
                               d[i-1, j-1] + cost   // trường hợp thay thế
                          )
        }

   return d[m, n]

ví dụ, giá trị của bảng d:

k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
S a t u r d a y
0 1 2 3 4 5 6 7 8
S 1 0 1 2 3 4 5 6 7
u 2 1 1 2 2 3 4 5 6
n 3 2 2 2 3 3 4 5 6
d 4 3 3 3 3 4 3 4 5
a 5 4 3 4 4 4 4 3 4
y 6 5 4 4 5 5 5 4 3

Như vậy, kết quả cần tính chính là giá trị của d[n, m]. Thực chất, thuật toán này là một phần trong giải pháp Longest common subsequence problem