Khoảng cách Levenshtein

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]. Bài toán này có phần tương tự với bài toán chuỗi con chung dài nhất

Tham khảo

[sửa | sửa mã nguồn]

Hjelmqvist, Sten (26 Mar 2012), Fast, memory efficient Levenshtein algorithm

Chúng tôi bán
Bài viết liên quan
Cẩm nang La Hoàn Thâm Cảnh 2.4 - Genshin Impact
Cẩm nang La Hoàn Thâm Cảnh 2.4 - Genshin Impact
Phiên bản 2.4 này mang đến khá nhiều sự thú vị khi các buff la hoàn chủ yếu nhắm đến các nhân vật đánh thường
Giới thiệu về Kakuja - Tokyo Ghou
Giới thiệu về Kakuja - Tokyo Ghou
Kakuja (赫者, red one, kakuja) là một loại giáp với kagune biến hình bao phủ cơ thể của ma cà rồng. Mặc dù hiếm gặp, nhưng nó có thể xảy ra do ăn thịt đồng loại lặp đi lặp lại
Đức Phật Thích Ca trong Record of Ragnarok
Đức Phật Thích Ca trong Record of Ragnarok
Buddha là đại diện của Nhân loại trong vòng thứ sáu của Ragnarok, đối đầu với Zerofuku, và sau đó là Hajun, mặc dù ban đầu được liệt kê là đại diện cho các vị thần.
Hiệu ứng Brita và câu chuyện tự học
Hiệu ứng Brita và câu chuyện tự học
Bạn đã bao giờ nghe tới cái tên "hiệu ứng Brita" chưa? Hôm nay tôi mới có dịp tiếp xúc với thuật ngữ này