Cấu trúc dữ liệu tốt nhất để triển khai từ điển?

Question

Cấu trúc dữ liệu tốt nhất để lưu trữ tất cả các từ của từ điển là gì? Điều tốt nhất tôi có thể nghĩ đến là sử dụng một số HashMap, sẽ được ánh xạ tới một số HashTable. Về cơ bản, tùy thuộc vào nhân vật đầu tiên, chúng tôi sẽ nhận được HashTable liên quan và sau đó sử dụng điều này, chúng tôi có thể thêm các từ bắt đầu từ nhân vật đó. Sau đó, chúng tôi sẽ chọn một hàm băm tốt dựa trên chuỗi.

Có cách tiếp cận nào tốt hơn không?

Answer 1

Tùy thuộc vào những gì bạn muốn làm, có nhiều cấu trúc dữ liệu tốt.

Nếu bạn chỉ muốn lưu trữ các từ và hỏi "là từ này ở đây hay không?", Một bảng băm tiêu chuẩn không có máy móc ưa thích khác là một cách tiếp cận hợp lý. Nếu từ đó là danh sách được sửa trước, hãy cân nhắc sử dụng perfect hash table để có hiệu suất tuyệt vời và sử dụng không gian.

Nếu bạn muốn có thể kiểm tra xem một tiền tố có tồn tại trong khi hỗ trợ tra cứu nhanh, trie là một lựa chọn tốt, mặc dù nó có thể là một chút không hiệu quả. Nó cũng hỗ trợ chèn nhanh hoặc xóa. Nó cũng cho phép lặp lại theo thứ tự bảng chữ cái, mà băm không cung cấp. Về cơ bản, đây là cấu trúc bạn đã mô tả trong câu trả lời của bạn, nhưng tùy thuộc vào trường hợp sử dụng, các biểu diễn khác của các lần thử có thể tốt hơn.

Nếu ngoài những điều trên, bạn biết thực tế là danh sách từ đã được sửa, hãy xem xét sử dụng DAWG (đồ thị từ tuần hoàn hướng), về bản chất là DFA tối thiểu cho ngôn ngữ. Đó là đáng kể nhỏ gọn hơn so với trie, nhưng hỗ trợ nhiều hoạt động tương tự.

Nếu bạn muốn hành vi giống như trie nhưng không muốn trả tiền phạt không gian lớn, ternary search tree là một tùy chọn khả thi khác, như là radix tree. Đây là những cấu trúc rất khác nhau, nhưng có thể tốt hơn nhiều so với trie trong những hoàn cảnh khác nhau.

Nếu không gian là một mối quan tâm nhưng bạn muốn có một trie, nhìn vào đại diện succinct trie, trong đó có tra cứu chậm hơn nhưng chỉ về cách sử dụng không gian lý thuyết tối ưu. Liên kết thảo luận về cách nó được sử dụng trong JavaScript như một cách dễ dàng để truyền tải một lượng lớn dữ liệu. Một đại diện nhỏ gọn thay thế là double-array trie, mặc dù thừa nhận rằng tôi biết rất ít về nó.

Nếu bạn muốn sử dụng từ điển cho các hoạt động như kiểm tra lỗi chính tả nơi bạn cần tìm các từ tương tự với các từ khác, thì BK-tree là một cấu trúc dữ liệu tuyệt vời để xem xét.

Hy vọng điều này sẽ hữu ích!