Tìm hai chuỗi tương tự như thế nào là

Question

Tôi đang tìm một thuật toán có 2 chuỗi và sẽ cho tôi trở lại "yếu tố tương tự".

Về cơ bản, tôi sẽ có một đầu vào có thể sai chính tả, có chữ cái transposed, vv, và tôi phải tìm các đối sánh gần nhất trong danh sách các giá trị có thể có.

Đây không phải để tìm kiếm trong cơ sở dữ liệu. Tôi sẽ có một danh sách trong bộ nhớ của 500 hoặc để chuỗi để phù hợp với, tất cả dưới 30 ký tự, do đó, nó có thể tương đối chậm.

Tôi biết điều này tồn tại, tôi đã thấy nó trước đây, nhưng tôi không thể nhớ tên của nó.

---

Chỉnh sửa: Cảm ơn bạn đã chỉ ra Levenshtein và Hamming. Bây giờ, tôi nên triển khai cái nào? Về cơ bản họ đo lường những thứ khác nhau, cả hai đều có thể được sử dụng cho những gì tôi muốn, nhưng tôi không chắc cái nào phù hợp hơn.

Tôi đã đọc các thuật toán, Hamming có vẻ nhanh hơn. Vì sẽ không phát hiện hai nhân vật bị chuyển đổi (tức là Jordan và Jodran), mà tôi tin rằng sẽ là một sai lầm phổ biến, điều này sẽ chính xác hơn cho những gì tôi muốn? Ai đó có thể cho tôi biết một chút về sự cân bằng?

Answer 1

Ok, vì vậy các thuật toán tiêu chuẩn là:

1) Hamming distance Chỉ tốt cho chuỗi chiều dài tương tự, nhưng rất hiệu quả. Về cơ bản nó chỉ đơn giản là đếm số ký tự riêng biệt. Không hữu ích cho tìm kiếm mờ của văn bản ngôn ngữ tự nhiên.

2) . Khoảng cách Levenstein đo khoảng cách về số lượng "hoạt động" cần thiết để chuyển đổi một chuỗi sang chuỗi khác. Các hoạt động này bao gồm chèn, xóa và biến đổi. Cách tiếp cận tiêu chuẩn để tính khoảng cách Levenstein là sử dụng lập trình động.

3) Generalized Levenstein/(Damerau–Levenshtein distance) Khoảng cách này cũng sẽ xem xét việc chuyển đổi các ký tự trong một từ và có thể là khoảng cách chỉnh sửa phù hợp nhất cho phù hợp mờ của văn bản được nhập theo cách thủ công. Thuật toán tính toán khoảng cách có liên quan nhiều hơn một chút so với khoảng cách Levenstein (phát hiện chuyển vị không dễ). Triển khai phổ biến nhất là sửa đổi thuật toán bitap (như grep).

Nói chung bạn có lẽ sẽ muốn xem xét một thực hiện các tùy chọn thứ ba thực hiện trong một số loại tìm kiếm hàng xóm gần nhất dựa trên một cây kd

Answer 2

Bạn đang tìm kiếm Levenshtein distance

Answer 3

• Levenstein khoảng cách
• khoảng cách Hamming
• Soundex
• metaphone

Answer 4

các Damerau-Levenshtein distance cũng tương tự như khoảng cách Levenshtein, nhưng cũng bao gồm chuyển đổi hai ký tự. trang wikipedia (được liên kết) bao gồm mã giả nên khá tầm thường để triển khai.