Số kết nối mờ

Question

Tôi đã làm việc với Double Metaphone và Caverphone2 để so sánh String và chúng hoạt động tốt trên những thứ như tên, địa chỉ, v.v. (Caverphone2 hoạt động tốt nhất với tôi). Tuy nhiên, chúng tạo ra quá nhiều kết quả sai khi bạn nhận được các giá trị số, chẳng hạn như số điện thoại, địa chỉ ip, số thẻ tín dụng, v.v.

Vì vậy, tôi đã xem xét các thuật toán Luhn và Verhoeff Tôi muốn, nhưng không hoàn toàn. Họ có vẻ tốt khi xác nhận, nhưng dường như không được xây dựng cho phù hợp mờ. Có bất cứ điều gì cư xử như Luhn và Verhoeff, có thể phát hiện lỗi một chữ số và chuyển vị lỗi liên quan đến hai chữ số liền kề, cho mục đích mã hóa và so sánh tương tự như các thuật toán chuỗi mờ?

Tôi muốn mã hóa một số, sau đó so sánh nó với 100.000 số khác để tìm các kết quả trùng khớp giống nhau. Vì vậy, một cái gì đó như 7041234 sẽ phù hợp với 7041324 như là một lỗi phiên mã có thể, nhưng một cái gì đó giống như 4213704 sẽ không.

Answer 1

Levenshteinandfriends có thể tốt cho việc tìm khoảng cách giữa các chuỗi hoặc số cụ thể. Tuy nhiên nếu bạn muốn xây dựng một sửa lỗi chính tả bạn không muốn chạy qua toàn bộ cơ sở dữ liệu từ của bạn tại mọi truy vấn.

Peter Norvig đã viết a very nice article trên trình đơn sửa lỗi chính tả "phù hợp mờ" đơn giản dựa trên một số công nghệ đằng sau các đề xuất chính tả của google.

Nếu từ điển của bạn có các mục nhập N và từ trung bình có chiều dài L, cách tiếp cận "Lực lượng vũ phu Levenshtein" sẽ mất thời gian O(N*L^3). Cách tiếp cận của Peter Norvig thay vì tạo ra tất cả các từ trong một khoảng cách chỉnh sửa nhất định từ đầu vào và tìm chúng trong từ điển. Do đó nó đạt được O(L^k), trong đó k là khoảng cách chỉnh sửa xa nhất được xem xét.