Trong công việc hàng ngày, thỉnh thoảng bạn sẽ gặp phải bắt buộc chỉnh sửa lại các từ, cụm trong khoảng sắp giống nhau bởi nhiều lý do: mang thể là người khác lỡ nhập liệu sai, hoặc mang thể do phổ quát bên nhập liệu không hợp nhất, hoặc sử dụng bí quyết bỏ dấu khác nhau khiến những trong khoảng 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 sở hữu bao giờ tò mò rằng tính năng tự động gợi ý từ hoạt động ra sao? Cố nhiên, mang phần nhiều cách để làm điều đó, và trong bài viết này, Học Excel Online sẽ giới thiệu tới Anh chị em Levenshtein distance (khoảng phương pháp Levenshtein) cũng như ứng dụng của nó để tậu chuỗi sắp giống nhau.
giả dụ bạn đã hiểu về Levenshtein Distance và muốn sắm cách sử dụng hài hòa VBA để so sánh đồng thời phổ biến chuỗi cùng lúc, hãy đọc bài viết này
Levenshtein Distance?
nhắc 1 cách đơn giản, 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 có 2 chuỗi: một. cat; hai. cap
Theo khái niệm Levenshtein Distance, sự khác biệt của 2 chuỗi trên là một bởi chỉ cần một phép biến đổi từ cat sang cap (thay t bằng p).
tương tự, mang 2 chuỗi: 1. KPMG và 2. KPMGLLp, sự dị biệt là 3 bởi cần 3 phép biến đổi thêm vào trong khoảng 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ứ một, b là chuỗi thứ 2, i,j là vị trí đầu cuối (tính trong khoảng kí tự đầu tới kí tự i, j của 2 chuỗi).
Hiểu một cách thức đơn giản:
-Nếu i hoặc j = 0 thì số dị biệt là số to nhất trong i và j.
-Trường hợp còn lại, số dị 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 mang kí tự ở vị trí j, chuỗi b).
Ví dụ:
Ta diễn ra 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ì 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] = một (+1 vì người nào <> 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] = một (+1 vì người nào <> 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ì người nào <> bj)
Kết quả ta với được là một.
tìm chuỗi gần giống nhau trong Excel có Levenshtein distance
trong khoảng bài toán trên, ta với thể ứng dụng vào trong Excel để vun đắp một mô phỏng so sánh 2 chuỗi kí tự (và còn có thể mở mang 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 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 khăng khăng cất 2 chuỗi:
Thiết lập khung cho mô phỏng
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 những kí tự đơn lẻ và đưa vào từng ô. Có đầy đủ công thức có 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 các phiên bản khác, bạn mang thể tiêu dùng công thức mảng khiến tương tự.
Điền số
từ đây, ta mang thể khởi đầ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 những số một, 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 để đá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ể 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 ví như phiên bản Excel được tiêu dùng không phải là 365.
- có các vị trí còn lại, ta với 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ì người nào <> 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ì người nào <> bj)
Trong phạm vi 4 ô, kết quả cần sắ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ứ hai +1, giá trị ô thứ 3 +1; giá trị ô thứ 1 + một nếu 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 phương pháp trực giác, trong hình dưới, để điền vào ô E4, vì người nào == 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 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))),"")
các vị trí còn lại ta ứng dụng như vậy bằng cách thức kéo thả để điền dữ liệu vào. Bạn sở hữu thể tạo ra 1 bảng mang kích cỡ 10×10 hoặc 20×20 để xử lý chuỗi to hơn.
*Hàm LOWER được tiêu 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 ví như dùng thuần Levenshtein distance sẽ mang độ 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 có can dự gì đến 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 phương pháp Levenshtein hai chuỗi)/(độ dài chuỗi a + độ dài chuỗi b)
Hoặc:
1 – khoảng cách thức Levenshtein hai chuỗi/tổng độ dài hai chuỗi.
Công thức vận 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): mua ra giá trị tại ô cuối cùng trong bảng – chính là khoảng phương pháp Levenshtein.
Qua chỉ dẫn đơn thuần này, Học Excel Online kỳ vọng bạn đã biết cách tự setup cho mình một sườn đơn thuần để tìm chuỗi gần giống nhau trong Excel.
Tham khảo cách thức tạo Levenshtein distance trong VBA để so sánh chuỗi hàng loạt, phổ biến chuỗi với nhau cùng lúc: So sánh, mua chuỗi gần đúng có Levenshtein trong VBA.
Tham khảo cách thức sử dụng Power Query để khắc phục bài toán match các giá trị sắp giống nhau: Group đối tượng dùng Fuzzy Matching trong Power Query
0 nhận xét:
Đăng nhận xét