Tỷ lệ phần trăm của các kết quả phù hợp sử dụng Levenshtein Khoảng cách phù hợp với

Question

Tôi đang cố gắng so khớp một cụm từ tìm kiếm với từ điển phù hợp có thể sử dụng thuật toán khoảng cách Levenshtein. Thuật toán trả về khoảng cách được biểu thị bằng số hoạt động cần thiết để chuyển đổi chuỗi tìm kiếm thành chuỗi phù hợp. Tôi muốn trình bày các kết quả trong danh sách phần trăm xếp hạng các kết quả "N" hàng đầu (ví dụ 10).

Vì chuỗi tìm kiếm có thể dài hơn hoặc ngắn hơn các chuỗi từ điển riêng lẻ, nên một logic thích hợp để biểu thị khoảng cách dưới dạng phần trăm, điều này sẽ phản ánh chất lượng "gần như phần trăm". chuỗi, với 100% cho biết kết quả khớp chính xác.

tôi coi các tùy chọn sau:

Q = query string 
M = matched string 
PM = Percentage Match 
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100 
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100 

Lựa chọn 1 có khả năng tỷ lệ tiêu cực trong trường hợp khoảng cách lớn hơn độ dài chuỗi tìm kiếm, nơi mà các chuỗi trận đấu dài. Ví dụ truy vấn "ABC" phù hợp với "ABC Corp." sẽ dẫn đến phần trăm đối sánh phủ định.

Phương án 2 dường như không cung cấp tỷ lệ nhất quán trên một tập hợp Mi, vì mỗi phép tính có thể sử dụng mẫu số khác và do đó giá trị phần trăm kết quả sẽ không được chuẩn hóa.

Chỉ có một cách khác tôi có thể nghĩ là bỏ qua sự so sánh của độ lệch cho chuỗi dài, nhưng thay vào đó là khoảng cách so sánh của kết quả "N" trên cùng với xếp hạng phần trăm nghịch đảo (xếp hạng 100 phần trăm).

Mọi suy nghĩ? Có cách tiếp cận tốt hơn? Tôi phải mất một cái gì đó như Levenshtein khoảng cách có lẽ là thuật toán phổ biến nhất cho các trận đấu mờ và điều này phải là một vấn đề rất phổ biến.

Answer 1

(1 - (levNum/Math.max(s.length,t.length))) *100 

nên đúng

Answer 2

Đây thực chất là phương án 2 đề cập trong câu hỏi của tôi. Tuy nhiên, hãy để tôi trình bày một vấn đề với cách tiếp cận đó.

Q = "ABC Corp" (len = 8) 
M1 = "ABC" 
M2 = "ABC Corporati" 
M3 = "ABC Corp" 

Tôi đã chọn M1 và M2 sao cho khoảng cách Lev của chúng giống nhau (5 lần). Sử dụng phương án 2, tỷ lệ trận đấu sẽ là

M1 = (1 - 5/8)*100 = 37.5% 
M2 = (1 - 5/13)*100 = 61.5% 
M3 = 100% 

Như bạn có thể thấy nếu tôi trình bày các trận đấu theo thứ tự đó, có một sự khác biệt thứ hạng rất lớn giữa M1 và M2, mặc dù họ có chính xác cùng một khoảng cách lev. Bạn thấy vấn đề?

Answer 3

Cách tiếp cận của tôi đối với vấn đề này là bằng cách tính toán các hoạt động tối đa cho phép, đó là khoảng cách Levenshtein. Công thức tôi đã sử dụng là:

percent = 0.75; // at least 75% of string must match 
maxOperationsFirst = s1.length() - s1.length() * percent; 
maxOperationsSecond = s2.length() - s2.length() * percent; 
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond)); 

Nó tính toán hoạt động tối đa cho mỗi chuỗi, tôi tin rằng việc tính toán dễ hiểu. Tôi sử dụng giá trị tối thiểu của cả hai kết quả và làm tròn nó đến số nguyên gần nhất. Bạn có thể bỏ qua phần này và chỉ sử dụng giá trị của các hoạt động tối đa từ một trong hai chuỗi, nó thực sự phụ thuộc vào dữ liệu của bạn.

Khi bạn đã có số hoạt động tối đa, bạn có thể so sánh nó với kết quả levenshtein và xác định xem chuỗi có được chấp nhận hay không. Bằng cách này, bạn có thể sử dụng bất kỳ phương pháp levenshtein mở rộng nào, ví dụ: Damerau–Levenshtein distance, tính số lỗi chính tả, ví dụ:kiểm tra -> tset, chỉ với 1 hoạt động, điều này khá hữu ích khi kiểm tra dữ liệu nhập của người dùng trong đó những lỗi chính tả đó xảy ra rất thường xuyên.

Tôi hy vọng điều này sẽ giúp bạn có ý tưởng về cách giải quyết vấn đề này.

Answer 4

Tôi gặp sự cố tương tự và chuỗi này đã giúp tôi tìm ra giải pháp. Hy vọng nó cũng có thể giúp người khác.

int levDis = Lev_distance(Q, Mi) 
int bigger = max(strlen(Q), strlen(Mi)) 
double pct = (bigger - levDis)/bigger 

Nó phải trả về 100% nếu cả hai chuỗi giống hệt nhau và 0% nếu chúng hoàn toàn khác nhau.

(xin lỗi nếu tiếng Anh của tôi không phải là tốt)

Answer 5

gì về điều này một:

100 - (((2*Lev_distance(Q, Mi))/(Q.length + Mi.length)) * 100) 

Nó cung cấp cho cùng một khoảng cách trên (Q, M1) và (Q,M2)