Trong công tác hàng ngày, đôi khi bạn sẽ gặp phải buộc phải chỉnh sửa lại những trong khoảng, cụm từ gần giống nhau bởi phổ thông lý do: với thể là người khác lỡ nhập liệu sai, hoặc sở hữu thể do nhiều bên nhập liệu không hợp nhất, hoặc tiêu dùng cách thức bỏ dấu khác nhau làm 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 mang bao giờ tò mò rằng tính năng tự động gợi ý trong khoảng hoạt động ra sao? Tất nhiên, mang gần như bí quyết để làm điều đó, và trong bài viết này, Học Excel Online sẽ giới thiệu tới Cả nhà Levenshtein distance (khoảng phương pháp Levenshtein) cũng như vận dụng của nó để tìm chuỗi sắp giống nhau.
ví như bạn đã hiểu về Levenshtein Distance và muốn mua bí quyết dùng hài hòa VBA để so sánh cùng lúc phổ thông chuỗi cùng lúc, hãy đọc bài viết này
Levenshtein Distance?
nói 1 phương pháp thuần tuý, Levenshtein Distance là sự dị 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 1 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 lớn transform one string into the other."
thí dụ, ta mang 2 chuỗi: một. cat; 2. cap
Theo định nghĩa Levenshtein Distance, sự dị biệt của 2 chuỗi trên là một bởi chỉ cần 1 phép biến đổi trong khoảng cat sang cap (thay t bằng p).
như vậy, với hai chuỗi: một. KPMG và 2. KPMGLLp, sự dị biệt là 3 bởi cần 3 phép biến đổi thêm vào từ KPMG sang KPMGLLp hoặc trái lại.
Công thức
bí quyết tính số dị biệt được viết như sau:
Trong đó:
a là chuỗi thứ một, 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 bí quyết đơn giản:
-Nếu i hoặc j = 0 thì số khác biệt là số to 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ỉ ứng dụng lúc người nào <> bj (kí tự ở vị trí i, chuỗi a khác sở hữu kí tự ở vị trí j, chuỗi b)
Ví dụ:
Ta tính từ lúc lev(a,b)(1,1) và chấm dứt ở 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ì người nào = 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] = hai (+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] = một (+1 vì ai <> bj)
Kết quả ta mang được là 1.
tìm chuỗi sắp giống nhau trong Excel có Levenshtein distance
từ bài toán trên, ta với thể vận 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 sở hữu thể mở mang thêm cho phổ thông chuỗi kí tự). Bài toán giả định đơn thuần ở đây là ta sở hữu 2 chuỗi cần so sánh độ giống nhau. Những bước tiến hành cụ thể:
Thiết lập vị trí nhập chuỗi
Trong tỉ 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 hai chuỗi:
Thiết lập khuông cho mô hình
Ta sẽ bắt đầu ở vị trí 0 cho cả hai chuỗi. Để đánh dấu vị trí 0, đặt 1 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ó phần nhiều công thức sở hữu thể ứng dụng để khiến điều này. sở hữu 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ứ hai tại ô E2. Trong những phiên bản khác, bạn với thể dùng công thức mảng làm như vậy.
Đ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 bí quyết Levenshtein chính bằng các số một, 2, 3,… n, hay chính bằng vị trí của kí tự tại điểm đó. Ta sẽ dùng hàm để đáp ứng 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 với thể tiêu dùng tại ô D4: =ROW(INDIRECT("1:"&LEN(A1))), tại ô E3: =TRANSPOSE(MID(A2,ROW(INDIRECT("1:"&LEN(A2))),1)). dùng công thức mảng giả dụ 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 sở hữu 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] = một (+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] = hai (+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à trị giá nhỏ nhất dựa theo giá trị của 3 ô còn lại theo quy tắc: giá trị ô thứ 2 +1, trị giá ô thứ 3 +1; trị giá ô thứ 1 + một nếu như kí tự chuỗi a ở vị trí i khác mang kí tự chuỗi b ở vị trí j và giữ nguyên trong trường hợp ngược lại. Kể 1 cách trực giác, 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 thức kéo thả để điền dữ liệu vào. Bạn mang thể tạo ra 1 bảng có kích cỡ 10×10 hoặc 20×20 để xử lý chuỗi to 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 như tiêu dùng thuần Levenshtein distance sẽ với độ khác biệt là 4. Khi mà kết hợp có 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 sở hữu can hệ gì tới việc so sánh 2 chuỗi với 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 thức Levenshtein hai chuỗi)/(độ dài chuỗi a + độ dài chuỗi b)
Hoặc:
1 – khoảng phương pháp Levenshtein 2 chuỗi/tổng độ dài 2 chuỗi.
Công thức ứng 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): Độ dài hai chuỗi tại A1 và A2
- INDIRECT("R"&LEN(A1)+3&"C"&LEN(A2)+4,FALSE): tậu ra giá trị tại ô rút cuộc trong bảng – chính là khoảng cách thức Levenshtein.
Qua chỉ dẫn đơn giản này, Học Excel Online kỳ vọng bạn đã biết cách thức tự setup cho mình một khung đơn thuần để tậu chuỗi sắp giống nhau trong Excel.
Tham khảo cách tạo Levenshtein distance trong VBA để so sánh chuỗi hàng loạt, đa dạng chuỗi với nhau cộng lúc: So sánh, tậu chuỗi sắp đúng sở hữu Levenshtein trong VBA.
Tham khảo cách sử dụng Power Query để khắc phục bài toán match những trị giá sắp giống nhau: Group đối tượng tiêu dùng Fuzzy Matching trong Power Query
0 nhận xét:
Đăng nhận xét