Trước hết, khoảng cách Levenshtein được định nghĩa là số lần chỉnh sửa tối thiểu cần thiết để chuyển đổi chuỗi A thành chuỗi B, trong đó chỉnh sửa là việc chèn hoặc xóa một ký tự hoặc thay thế một ký tự bằng một ký tự khác. Vì vậy, nó rất giống "sự khác biệt giữa hai chuỗi", cho một định nghĩa nhất định về khoảng cách. =)
Có vẻ như bạn đang tìm kiếm một hàm khoảng cách F (A, B) cung cấp khoảng cách giữa các chuỗi A và B và ngưỡng N trong đó các chuỗi có khoảng cách nhỏ hơn N với nhau là ứng cử viên cho lỗi chính tả. Ngoài khoảng cách Levenshtein, bạn cũng có thể xem xét Needleman – Wunsch . Về cơ bản thì nó giống nhau nhưng nó cho phép bạn cung cấp một hàm cho biết mức độ gần của một ký tự nhất định với một ký tự khác. Bạn có thể sử dụng thuật toán đó với một tập hợp các trọng số phản ánh vị trí của các phím trên bàn phím QWERTY để tìm ra lỗi chính tả khá tốt. Tuy nhiên, điều này sẽ có vấn đề với bàn phím quốc tế.
Nếu bạn có k chuỗi và bạn muốn tìm lỗi chính tả tiềm ẩn, số phép so sánh bạn cần thực hiện là O (k ^ 2). Ngoài ra, mỗi so sánh là O (len (A) * len (B)). Vì vậy, nếu bạn có một triệu chuỗi, bạn sẽ thấy mình gặp rắc rối nếu bạn làm mọi thứ một cách ngây thơ. Dưới đây là một số gợi ý về cách tăng tốc:
- Xin lỗi nếu điều này là rõ ràng, nhưng khoảng cách Levenshtein là đối xứng, vì vậy hãy đảm bảo rằng bạn không tính F (A, B) và F (B, A).
- abs (len (A) - len (B)) là giới hạn dưới về khoảng cách giữa các chuỗi A và B. Vì vậy, bạn có thể bỏ qua việc kiểm tra các chuỗi có độ dài quá khác nhau.
Một vấn đề bạn có thể gặp phải là "1st St." có một khoảng cách khá cao so với "Phố đầu tiên", mặc dù bạn có thể muốn coi chúng là giống hệt nhau. Cách dễ nhất để xử lý điều này có lẽ là chuyển đổi các chuỗi thành một dạng chuẩn trước khi thực hiện các phép so sánh. Vì vậy, bạn có thể đặt tất cả các chuỗi là chữ thường, sử dụng từ điển ánh xạ từ "đầu tiên" thành "đầu tiên", v.v. Từ điển đó có thể khá lớn, nhưng tôi không biết cách tốt hơn để giải quyết vấn đề này.
Vì bạn đã gắn thẻ câu hỏi này bằng php, tôi cho rằng bạn muốn sử dụng php cho việc này. PHP có tích hợp sẵn hàm levenshtein () nhưng cả hai chuỗi phải có 255 ký tự trở xuống. Nếu điều đó không đủ lâu, bạn sẽ phải tự làm. Ngoài ra, bạn điều tra bằng cách sử dụng difflib của Python.
