Sử dụng khoảng cách Levenshtein để tìm kiếm chuỗi tương đồng trong Excel

Khi làm việc mỗi ngày, có khả năng bạn sẽ đối mặt với việc cần chỉnh sửa các từ hoặc cụm từ có độ tương đồng cao vì nhiều nguyên nhân. Có thể là do nhập dữ liệu không chuẩn xác, do không có sự nhất quán trong cách nhập liệu giữa các người dùng, hoặc do sự biến đổi trong cách bỏ dấu khiến các từ có vẻ giống nhau nhưng không giống (tại đây có mô tả một trường hợp như vậy). Hoặc bạn có thể tự hỏi liệu chức năng đề xuất từ tự động hoạt động thế nào? Có nhiều phương pháp để thực hiện điều này và bài viết sau đây từ Siêu Marketing sẽ trình bày về khoảng cách Levenshtein và cách áp dụng nó để tìm kiếm các chuỗi tương đồng.

Nếu bạn đã quen thuộc với Levenshtein Distance và muốn khám phá cách thức vận dụng VBA để so sánh nhiều chuỗi cùng một lúc, bạn nên tham khảo bài viết này.

Khoảng cách Levenshtein là gì?

Một cách dễ hiểu, khoảng cách Levenshtein được định nghĩa là số lượng sự khác biệt giữa hai chuỗi ký tự, tức là số kí tự phải loại bỏ, chèn thêm hoặc thay đổi để chuyển đổi một chuỗi thành chuỗi kia.

Xét cho ví dụ hai chuỗi: 1. cat; 2. cap

Dựa trên khoảng cách Levenshtein, sự khác biệt giữa hai chuỗi trên là 1, vì chỉ cần một bước biến đổi là thay t bằng p để từ cat thành cap.

Còn đối với hai chuỗi: 1. KPMG và 2. KPMGLLp, chênh lệch là 3 vì cần 3 bước thêm vào để từ KPMG chuyển thành KPMGLLp hoặc ngược lại.

Công thức tính

Phương pháp để định lượng sự khác biệt được trình bày sau:

PHP - Is this Levenshtein distance recursive algorithm so slow or am I wrong? - Stack Overflow

 

Trong đó:

Chuỗi a là chuỗi đầu tiên, b là chuỗi thứ hai, i và j đại diện cho các vị trí từ đầu đến cuối (tính từ ký tự đầu tiên đến ký tự thứ i, j của mỗi chuỗi).

Để hiểu một cách cơ bản:

– Nếu i hoặc j bằng 0, thì sự khác biệt chính là giá trị lớn hơn giữa i và j.

– Trong trường hợp khác, sự khác biệt là giá trị nhỏ nhất giữa 3 công thức sau:

  1. lev(i-1,j)+1
  2. lev(i,j-1)+1
  3. lev(i-1,j-1)+1*

.

*Nếu ký tự tại vị trí i của chuỗi a khác với ký tự ở vị trí j của chuỗi b, tức là ai <> bj, thì trường hợp đó mới cộng thêm 1.

Ví dụ:

Chúng ta bắt đầu với lev(a,b)(1,1) và kết thúc tại 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 cần +1 vì ai = a1 = "c" và cũng là 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 (cần cộng thêm 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 (tăng thêm do 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 (phải cộng 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 (tăng do ai <> bj là cần thiết)

Cuối cùng ta nhận ra kết quả chính là 1.

Ứng dụng khoảng cách Levenshtein để tìm kiếm chuỗi gần giống trong Excel

Đối với vấn đề đã nêu ra, ta có thể tận dụng nó để tạo ra một model trong Excel nhằm so sánh độ tương đồng giữa hai chuỗi kí tự (hoặc có thể mở rộng cho nhiều chuỗi hơn). Giả sử một bài toán đơn giản là ta cần so sánh giữa hai chuỗi để xác định mức độ giống nhau. Các bước thực hiện bao gồm:

Chúng ta sẽ thực hiện đặt 2 chuỗi a và b lần lượt vào các ô A1 và A2 trên bảng tính, với định nghĩa đây là vị trí cố định:

Xác định vị trí bắt đầu của chuỗi

Vị trí khởi đầu của cả hai chuỗi sẽ là 0. Đặt một ký hiệu như # để đánh dấu điểm 0 này trên cả hai chiều, ở ô D2 và C3:

Chia nhỏ chuỗi

Sau đó, mỗi chuỗi sẽ được tách thành các ký tự riêng lẻ và đặt vào từng ô tương ứng. Nhiều công thức có thể được áp dụng cho việc này:

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

Đối với chuỗi đầu tiên ở ô C4, và

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

Đối với chuỗi thứ hai ở ô E2. Sử dụng công thức mảng nếu không sử dụng Office 365.

Nhập giá trị số

Chúng ta bây giờ có thể tiến hành điền số vào bảng:

  • Ở vị trí (0,0), do min(0,0) = 0 nên lev(a,b)(0,0) = max(0,0) = 0 => ô D3 sẽ là 0
  • Tại ô D4, ta dùng công thức tạo dãy số bắt đầu từ 1 đến độ dài chuỗi:
    =ROW(INDIRECT("1:"&LEN(A1))),

    Và tại ô E3:

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

    Đối với phiên bản Excel ngoài 365, sử dụng công thức mảng.

  • Đối với các vị trí khác, ta có thể nhận ra một quy luật như sau:
    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 do ai <> bj)

Giá trị tìm được tại ô góc phải dưới cùng sẽ là giá trị nhỏ nhất theo quy tắc đã nêu. Một cách hình ảnh, khi ai == bj, ta xét giá trị của D3, D4+1, E3+1 và lấy giá trị nhỏ nhất, ở đây là D3 = 0.

Áp dụng công thức dưới đây cho ô 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 sẽ được điền theo quy luật tương tự.

Việc điền thông tin vào bảng được thực hiện qua cách kéo và thả tương tự. Bạn có thể thiết kế một bảng toát ra với kích thước lên tới 10×10 hoặc 20×20 để làm việc với những chuỗi dữ liệu dài hơn.*Hàm LOWER được áp dụng trong ví dụ này giúp chuyển đổi các ký tự in hoa sang in thường. Ví dụ: KPMG với kpmg nếu không dùng LOWER mà tính khoảng cách Levenshtein sẽ có sự khác nhau là 4. Nhưng khi dùng kết hợp với hàm LOWER, khoảng cách giảm xuống còn 0.

Kết quả:

Xác định phần trăm sự tương đồng

Làm thế nào để khoảng cách Levenshtein phản ánh độ giống nhau của hai chuỗi? Ở đây, chúng ta sẽ dùng công thức sau để tính tỷ lệ phần trăm trùng khớp:

Fuzzy Joins Tutorial | Python-bloggers

Giải thích công thức:

(tổng độ dài của chuỗi a và chuỗi b – khoảng cách Levenshtein giữa hai chuỗi)/(tổng độ dài của chuỗi a và chuỗi b)

Hoặc:

1 – khoảng cách Levenshtein giữa hai chuỗi/chia cho tổng độ dài của hai chuỗi.

Cong thức này khi sử dụng trong Excel:

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

Trong đó:

  • Len(A1), Len(A2): Đại diện cho độ dài của hai chuỗi tại ô A1 và A2
  • INDIRECT(“R”&LEN(A1)+3&”C”&LEN(A2)+4,FALSE): giúp tìm giá trị tại ô cuối cùng của bảng, tức khoảng cách Levenshtein.

Tìm chuỗi gần giống nhau trong Excel

Thông qua bài viết hướng dẫn cơ bản này từ Siêu Marketing, hy vọng rằng bạn đã có thể tự mình thiết lập được một phương pháp đơn giản để tìm kiếm các chuỗi gần giống nhau sử dụng Excel.
Bạn cũng có thể tham khảo cách tạo khoảng cách Levenshtein trong VBA để so sánh một lượng lớn chuỗi cùng một lúc: So sánh, tìm chuỗi gần đúng với Levenshtein trong VBA.
Ngoài ra, tìm hiểu thêm cách dùng Power Query để giải quyết những vấn đề tương tự với chức năng Fuzzy Matching: Nhóm các đối tượng sử dụng Fuzzy Matching trong Power Query

Trương Thành Tài
0
    0
    Đơn hàng
    Đơn hàng trốngQuay lại Shop