edit distance Archives -

Tìm chuỗi gần giống trong Excel với Levenshtein distance

Written by Minh Lai on 07/01/2022. Posted in Excel cơ bản. Leave a Comment

Trong công việc hàng ngày, đôi khi bạn sẽ gặp phải yêu cầu chỉnh sửa lại các từ, cụm từ gần giống nhau bởi nhiều lý do: có thể là người khác lỡ nhập liệu sai, hoặc có thể do nhiều bên nhập liệu không thống nhất, hoặc sử dụng cách bỏ dấu khác nhau khiến cho các từ tưởng giống nhau hóa ra lại khác (như trường hợp được nêu tại đây). Hay bạn có bao giờ tò mò rằng tính năng tự động gợi ý từ hoạt động ra sao? Tất nhiên, có rất nhiều phương pháp để làm điều đó, và trong bài viết này, Học Excel Online sẽ giới thiệu tới các bạn Levenshtein distance (khoảng cách Levenshtein) cũng như ứng dụng của nó để tìm chuỗi gần giống nhau.

Nếu bạn đã hiểu về Levenshtein Distance và muốn tìm cách sử dụng kết hợp VBA để so sánh đồng thời nhiều chuỗi cùng lúc, hãy đọc bài viết này

Levenshtein Distance?

Nói một cách đơn giản, Levenshtein Distance là sự khác biệt giữa 2 chuỗi kí tự. Cụ thể hơn, nó là số kí tự cần xóa đi, thêm vào hoặc thay thế để biến đổi một chuỗi kí tự thành chuỗi khác.

“The Levenshtein distance between two strings is the number of single character deletions, insertions, or substitutions required to transform one string into the other.”

Ví dụ, ta có 2 chuỗi: 1. cat; 2. cap

Theo định nghĩa Levenshtein Distance, sự khác biệt của 2 chuỗi trên là 1 bởi chỉ cần 1 phép biến đổi từ cat sang cap (thay t bằng p).

Tương tự, với 2 chuỗi: 1. KPMG và 2. KPMGLLp, sự khác biệt là 3 bởi cần 3 phép biến đổi thêm vào từ KPMG sang KPMGLLp hoặc ngược lại.

Công thức

Cách tính số khác biệt được viết như sau:

Trong đó:

a là chuỗi thứ 1, b là chuỗi thứ 2, i,j là vị trí đầu cuối (tính từ kí tự đầu đến kí tự i, j của 2 chuỗi).

Hiểu một cách đơn giản:

-Nếu i hoặc j = 0 thì số khác biệt là số lớn nhất trong i và j.

-Trường hợp còn lại, số khác biệt là số nhỏ nhất trong 3 công thức:

 lev(i-1,j)+1
 lev(i,j-1)+1
 lev(i-1,j-1)+1*

*Trường hợp +1 chỉ áp dụng khi ai <> bj (kí tự ở vị trí i, chuỗi a khác với kí tự ở vị trí j, chuỗi b).

Ví dụ:

Ta bắt đầu từ lev(a,b)(1,1) và kết thúc ở lev(a,b)(3,3)



lev(a,b)(1,1) = min[lev(a,b)(0,1)+1, lev(a,b)(1,0)+1, lev(a,b)(0,0)] = 0 (không +1 vì ai = a1 = "c" = bj = b1 = "c")


lev(a,b)(1,2) = min[lev(a,b)(0,2)+1, lev(a,b)(1,1)+1, lev(a,b)(0,1)+1] = 1 (+1 vì ai <> bj)


lev(a,b)(1,3) = min[lev(a,b)(0,3)+1, lev(a,b)(1,2)+1, lev(a,b)(0,2)+1] = 2 (+1 vì ai <> bj)


lev(a,b)(2,1) = min[lev(a,b)(1,1)+1, lev(a,b)(2,0)+1, lev(a,b)(1,0)+1] = 1 (+1 vì ai <> bj)


...


lev(a,b)(3,3)= min[lev(a,b)(2,3)+1, lev(a,b)(3,2)+1, lev(a,b)(2,2)+1] = 1 (+1 vì ai <> bj)

Kết quả ta có được là 1.

Tìm chuỗi gần giống nhau trong Excel với Levenshtein distance

Từ bài toán trên, ta có thể áp dụng vào trong Excel để xây dựng một mô hình so sánh 2 chuỗi kí tự (và còn có thể mở rộng thêm cho nhiều chuỗi kí tự). Bài toán giả định đơn giản ở đây là ta có 2 chuỗi cần so sánh độ giống nhau. Các bước tiến hành cụ thể:

Thiết lập vị trí nhập chuỗi

Trong ví dụ này, ta đặt chuỗi a vào ô A1, chuỗi b vào ô A2 trong trang tính, ta quy định đây là nơi cố định chứa 2 chuỗi:

Thiết lập khung cho mô hình

Ta sẽ bắt đầu ở vị trí 0 cho cả 2 chuỗi. Để đánh dấu vị trí 0, đặt một kí hiệu bất kì (VD: #) vào chiều ngang và chiều dọc tại 2 ô D2 và C3:

Cắt chuỗi

Ta sẽ tiến hành cắt nhỏ chuỗi thành các kí tự đơn lẻ và đưa vào từng ô. Có rất nhiều công thức có thể áp dụng để làm điều này.

Với phiên bản Office 365, mình chọn công thức

=MID(A1,ROW(INDIRECT("1:"&LEN(A1))),1)

cho chuỗi thứ nhất tại ô C4, và

=TRANSPOSE(MID(A2,ROW(INDIRECT("1:"&LEN(A2))),1))

cho chuỗi thứ 2 tại ô E2. Trong các phiên bản khác, bạn có thể sử dụng công thức mảng làm tương tự.

Điền số

Từ đây, ta có thể bắt đầu điền số vào bảng.

Tại vị trí (0,0), bởi min(0,0) = 0 nên lev(a,b)(0,0) = max(0,0) = 0 => điền 0 vào ô D3
Tại các vị trí (1,0), (2,0), (3,0), (n,0)… và (0,1), (0,2), (0,3), (0,n)… khoảng cách Levenshtein chính bằng các số 1, 2, 3,… n, hay chính bằng vị trí của kí tự tại điểm đó. Ta sẽ sử dụng hàm để tạo ra dãy số này với bắt đầu là 1 và kết thúc ở độ dài của chuỗi. Công thức có thể sử dụng tại ô D4:
```
=ROW(INDIRECT("1:"&LEN(A1))),
```
Tại ô E3:
```
=TRANSPOSE(MID(A2,ROW(INDIRECT("1:"&LEN(A2))),1)). 
```
Sử dụng công thức mảng nếu phiên bản Excel được sử dụng không phải là 365.
Với những vị trí còn lại, ta có thể nhìn ra quy tắc:

lev(a,b)(1,2) = min[lev(a,b)(0,2)+1, lev(a,b)(1,1)+1, lev(a,b)(0,1)+1] = 1 (+1 vì ai <> bj)


lev(a,b)(1,3) = min[lev(a,b)(0,3)+1, lev(a,b)(1,2)+1, lev(a,b)(0,2)+1] = 2 (+1 vì ai <> bj)


lev(a,b)(2,1) = min[lev(a,b)(1,1)+1, lev(a,b)(2,0)+1, lev(a,b)(1,0)+1] = 1 (+1 vì ai <> bj)

Trong phạm vi 4 ô, kết quả cần tìm ở ô bên dưới, góc phải sẽ là giá trị nhỏ nhất dựa theo giá trị của 3 ô còn lại theo quy tắc: giá trị ô thứ 2 +1, giá trị ô thứ 3 +1; giá trị ô thứ 1 + 1 nếu kí tự chuỗi a ở vị trí i khác với kí tự chuỗi b ở vị trí j và giữ nguyên trong trường hợp ngược lại. Nói một cách trực quan, trong hình dưới, để điền vào ô E4, vì ai == bj = “c”, ta xét 3 giá trị: D4+1,E3+1,D3. Vì D3 = 0 nhỏ nhất nên kết quả E4 =0.

Công thức được sử dụng trong trường hợp này như sau (đặt vào ô E4):

=IF(ISTEXT($C4)*ISTEXT(E$2),IF(MIN($D4,E$3)=0,MAX($D4,E$3),MIN(D4+1,E3+1,IF(EXACT(LOWER($C4),LOWER(E$2)),D3,D3+1))),"")

Những vị trí còn lại ta áp dụng tương tự bằng cách kéo thả để điền dữ liệu vào. Bạn có thể tạo ra một bảng với kích cỡ 10×10 hoặc 20×20 để xử lý chuỗi lớn hơn.

*Hàm LOWER được sử dụng trong trường hợp này nhằm xử lý ký tự hoa – thường. Chẳng hạn: KPMG và kpmg nếu dùng thuần Levenshtein distance sẽ có độ khác biệt là 4. Trong khi kết hợp với LOWER, độ khác biệt là 0.

Kết quả:

Tính tỷ lệ trùng khớp

Vậy khoảng cách Levenshtein có liên quan gì tới việc so sánh 2 chuỗi có giống nhau không? Trong trường hợp này, ta sẽ tính tỷ lệ trùng khớp bằng công thức:

Diễn giải:

(độ dài chuỗi a + độ dài chuỗi b – khoảng cách Levenshtein 2 chuỗi)/(độ dài chuỗi a + độ dài chuỗi b)

Hoặc:

1 – khoảng cách Levenshtein 2 chuỗi/tổng độ dài 2 chuỗi.

Công thức áp dụng trong Excel:

=(LEN(A1)+LEN(A2)-INDIRECT("R"&LEN(A1)+3&"C"&LEN(A2)+4,FALSE))/(LEN(A1)+LEN(A2))