Thuật toán tốt để đi qua một Trie để kiểm tra các gợi ý chính tả là gì?

Question

Giả sử rằng một Trie chung của từ điển được xây dựng, phương pháp nào là tốt nhất để kiểm tra 4 trường hợp lỗi chính tả - thay thế, xóa, chuyển vị trí và chèn trong quá trình truyền tải?

Một phương pháp là tìm ra tất cả các từ trong khoảng cách chỉnh sửa n của một từ nhất định và sau đó kiểm tra chúng trong Trie. Đây không phải là một lựa chọn tồi, nhưng trực giác tốt hơn ở đây dường như sử dụng một phương pháp lập trình động (hoặc đệ quy tương đương) để xác định các thử nghiệm phụ tốt nhất sau khi đã sửa đổi các từ trong quá trình truyền tải.

Bất kỳ ý tưởng nào đều được hoan nghênh!

PS, sẽ đánh giá cao đầu vào thực tế thay vì chỉ liên kết trong câu trả lời.

Answer 1

Tôi thực sự đã viết một số mã để làm điều này ngày khác:

https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py

Nó dựa trên mã của Peter Norvig (http://norvig.com/spell-correct.html) nhưng lưu trữ từ điển trong một Trie để tìm các từ trong một chỉnh sửa cho khoảng cách nhanh hơn.

Thuật toán đi trie đệ quy áp dụng các chỉnh sửa có thể (hoặc không) ở mỗi bước trên đường đi bằng cách tiêu thụ các chữ cái từ từ đầu vào. Tham số cho cuộc gọi đệ quy cho biết có thể thực hiện nhiều chỉnh sửa nữa. Trie giúp thu hẹp không gian tìm kiếm bằng cách kiểm tra những chữ cái thực sự có thể đạt được từ tiền tố đã cho của chúng tôi. Ví dụ: khi chèn ký tự, thay vì thêm từng chữ cái trong bảng chữ cái, chúng tôi chỉ thêm các chữ cái có thể truy cập từ nút hiện tại. Không thực hiện chỉnh sửa tương đương với việc lấy nhánh từ nút hiện tại trong trie dọc theo chữ cái hiện tại từ từ đầu vào. Nếu nhánh đó không có ở đó thì chúng ta có thể quay lại và tránh tìm kiếm một không gian rộng lớn có thể không tìm thấy từ thực sự nào.

Answer 2

Hãy xem tính toán Levenshtein distance cung cấp giải pháp lập trình động để tìm khoảng cách giữa hai chuỗi.

Answer 3

Tôi nghĩ bạn có thể thực hiện điều này với một tìm kiếm đơn giản trên cây: chọn một ngưỡng số lỗi bạn đang tìm kiếm, chỉ cần chạy từng chữ cái của từ để khớp tạo một tập hợp các cặp tiền tố (tiền tố, subtrie) cho đến nay khớp với tiền tố của bạn, và trong khi bạn đang ở dưới ngưỡng lỗi của bạn, hãy thêm vào tập hợp các subgoals tiếp theo của bạn:

1. Không có lỗi tại ký tự này: thêm subgoal của trie tại ký tự tiếp theo trong từ
2. Ký tự được chèn, xóa hoặc thay thế tại địa điểm này: tìm thấy trie thích hợp ở đó và tăng số lượng lỗi;
3. Không phải mục tiêu bổ sung, nhưng lưu ý rằng chuyển đổi là chèn hoặc xóa khớp với lần xóa hoặc chèn trước đó: nếu giữ thử này, thì không tăng số lượng lỗi.

Điều này có vẻ khá ngây thơ: có vấn đề gì với điều này khiến bạn nghĩ đến lập trình động không?

Answer 4

Giả sử mỗi ký tự liên tiếp trong từ của bạn đại diện cho một cấp trong cây của bạn, sau đó bạn có năm trường hợp để kiểm tra từng ký tự (khớp, xóa, chèn, thay thế và chuyển vị trí). Tôi giả định chuyển vị là hai ký tự liền kề.

Bạn sẽ cần một hàm (CheckNode) chấp nhận nút cây và ký tự cần kiểm tra. Nó sẽ cần trả về một tập hợp các nút (con/grand-child) đại diện cho các trận đấu.

Bạn sẽ cần một hàm (CheckWord) chấp nhận một từ. Nó kiểm tra từng nhân vật lần lượt chống lại một tập hợp các nút. Nó sẽ trả về một tập hợp các nút (lá) đại diện cho các từ phù hợp.

Ý tưởng là mỗi cấp trong cây (con, cháu lớn, v.v.), phù hợp với vị trí của ký tự trong từ. Nếu bạn gọi nút cây cấp cao nhất, mức 0, thì bạn sẽ có cấp 1, cấp 2, v.v.

Rõ ràng cho một từ không có lỗi, có một kết hợp một giữa vị trí ký tự và cấp trong cái cây.

Để xóa, bạn cần phải bỏ qua một cấp trong cây.

Để chèn, bạn cần bỏ qua một ký tự trong từ.

Để thay thế, bạn cần phải bỏ qua cả cấp độ và ký tự.

Để chuyển đổi, bạn cần phải (tạm thời) trao đổi các ký tự trong từ.