Thuật toán tốt nhất cho từ gần nhất

Question

Thuật toán tốt nhất cho từ gần nhất là gì.

Từ điển có thể có được cung cấp và các ký tự đầu tiên trong từ nhập liệu có thể sai.

Answer 1

Một lựa chọn là BK-cây -. Xem bài đăng blog của tôi về chúng here. Một tùy chọn khác, nhanh hơn nhưng phức tạp hơn là Levenshtein Automata, mà tôi cũng đã viết về, here.

Answer 2

Có những công cụ như HunSpell (trình kiểm tra chính tả mã nguồn mở rộng rãi bao gồm OpenOffice) đã tiếp cận vấn đề từ nhiều góc độ. Một tiêu chí được sử dụng rộng rãi để quyết định mức độ gần gũi của các từ là Levenshtein distance cũng được sử dụng trong HunSpell.

Answer 3

Bạn có thể sử dụng BLAST

và sửa đổi nó để sử dụng thực tế là từ trong một từ điển có đơn vị rời rạc mà làm cho quá trình kết hợp cụ thể hơn không giống như một chuỗi ADN dài.

BLAST đã tích hợp sẵn khái niệm khoảng cách chỉnh sửa.

Ngoài ra, bạn có thể sử dụng cây hậu tố (Dan Gusfeld có một cuốn sách tuyệt vời trên các thuật toán chuỗi kết hợp cơ bản) và xây dựng trong ý tưởng chỉnh sửa khoảng cách trong