Phương pháp dựa trên khoảng cách Levenshtein Vs Soundex

Question

Theo this nhận xét trong một chủ đề liên quan, tôi muốn biết tại sao phương pháp dựa trên khoảng cách Levenshtein tốt hơn Soundex.

Answer 1

Soundex khá nguyên thủy - ban đầu nó được phát triển để được tính toán bằng tay. Nó dẫn đến một khóa có thể được so sánh.

Soundex hoạt động tốt với tên phương Tây, vì ban đầu nó được phát triển cho dữ liệu điều tra dân số của Hoa Kỳ. Nó dành cho so sánh ngữ âm.

Khoảng cách Levenshtein xem xét hai giá trị và tạo ra một giá trị dựa trên sự giống nhau của chúng. Nó đang tìm kiếm các chữ cái bị thiếu hoặc thay thế.

Về cơ bản Soundex tốt hơn cho việc tìm kiếm rằng "Schmidt" và "Smith" có thể là cùng họ.

khoảng cách levenshtein là tốt hơn cho việc tìm kiếm mà người dùng đã gõ sai "Levnshtein" ;-)

Answer 2

@Keith:

Như tôi đã được đăng trên các câu hỏi khác, Daitch-Mokotoff là tốt hơn cho chúng châu Âu (và tôi 'd tranh luận Hoa Kỳ).

Tôi cũng đã đọc Wiki trên Levenshtein. Nhưng tôi không thấy lý do tại sao (trong đời thực) nó là tốt hơn cho người dùng hơn Soundex.

Answer 3

Tôi khuyên bạn nên sử dụng Metaphone, chứ không phải Soundex. Như đã nói, Soundex được phát triển vào thế kỷ 19 cho tên Mỹ. Metaphone sẽ cung cấp cho bạn một số kết quả khi kiểm tra công việc của những người bán hàng nghèo, những người đang "nghe nó ra", và đánh vần đúng ngữ âm.

Chỉnh sửa khoảng cách rất tốt khi đánh bắt lỗi chính tả như chữ cái lặp lại, chữ cái chuyển đổi hoặc nhấn phím sai.

Hãy xem xét ứng dụng để quyết định ứng dụng nào phù hợp nhất với người dùng của bạn — hoặc sử dụng cả hai cùng nhau, với Metaphone bổ sung các đề xuất do Levenshtein sản xuất.

Đối với câu hỏi ban đầu, tôi đã sử dụng n-grams thành công trong các ứng dụng truy xuất thông tin.

Answer 4

Tôi đồng ý với bạn về Daitch-Mokotoff, Soundex bị thiên vị vì các nhà điều tra dân số Hoa Kỳ ban đầu muốn tên 'Mỹ hóa'.

Có lẽ một ví dụ về sự khác biệt sẽ giúp:

Soundex đặt giá trị gia tăng trong sự khởi đầu của một từ - trên thực tế nó chỉ xem xét 4 thanh âm đầu tiên. Vì vậy, trong khi "Schmidt" và "Smith" sẽ khớp với "Smith" và "Wmith" thì không.

Thuật toán của Levenshtein sẽ tốt hơn cho việc tìm lỗi chính tả - một hoặc hai chữ cái bị thiếu hoặc thay thế tạo ra mối tương quan cao, trong khi tác động ngữ âm của những chữ cái còn thiếu là ít quan trọng.

Tôi không nghĩ là tốt hơn và tôi sẽ xem xét cả thuật toán khoảng cách và ngữ âm để giúp người dùng nhập đúng kiểu nhập.