Trước hết, chúng ta hãy xem xét các hạn chế của vấn đề. Bạn muốn lưu trữ danh sách từ cho một trò chơi trong cấu trúc dữ liệu hỗ trợ hiệu quả bài toán "đảo chữ". Tức là, cho một "giá đỡ" gồm n chữ cái, tất cả các từ gồm n hoặc ít hơn trong danh sách từ có thể được tạo ra từ giá đỡ đó là bao nhiêu. danh sách từ sẽ có khoảng 400 nghìn từ và do đó có thể là khoảng một đến mười megs dữ liệu chuỗi khi được giải nén.
Một trie là cấu trúc dữ liệu cổ điển được sử dụng để giải quyết vấn đề này vì nó kết hợp cả hiệu quả bộ nhớ với hiệu quả tìm kiếm. Với một danh sách từ khoảng 400K từ có độ dài hợp lý, bạn sẽ có thể lưu giữ trie đó trong bộ nhớ. (Trái ngược với giải pháp theo kiểu b-tree, trong đó bạn giữ phần lớn cây trên đĩa vì nó quá lớn để có thể vừa trong bộ nhớ cùng một lúc.)
Một trie về cơ bản không hơn gì một cây 26-ary (giả sử bạn đang sử dụng bảng chữ cái La Mã) trong đó mỗi nút có một chữ cái và một bit bổ sung trên mỗi nút cho biết đó có phải là phần cuối của từ hay không.
Vì vậy, hãy phác thảo cấu trúc dữ liệu:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Tất nhiên đây chỉ là một bản phác thảo; bạn có thể muốn làm cho chúng có các trình truy cập và xây dựng thuộc tính thích hợp và không. Ngoài ra, có thể một danh sách phẳng không phải là cấu trúc dữ liệu tốt nhất; có lẽ một số loại từ điển tốt hơn. Lời khuyên của tôi là làm cho nó hoạt động trước, sau đó đo lường hiệu suất của nó, và nếu nó không thể chấp nhận được, thì hãy thử nghiệm thực hiện các thay đổi để cải thiện hiệu suất của nó.
Bạn có thể bắt đầu với một bộ ba trống:
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
Đó là, đây là nút trie "gốc" đại diện cho phần bắt đầu của một từ.
Làm thế nào để bạn thêm từ "AA", từ đầu tiên trong từ điển Scrabble? Tốt, trước tiên hãy tạo một nút cho chữ cái đầu tiên:
root.Children.Add('A', false, new List<TrieNode>());
OK, bộ ba của chúng ta bây giờ là
^
|
A
Bây giờ, hãy thêm một nút cho chữ cái thứ hai:
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
Bộ ba của chúng tôi bây giờ là
^
|
A
|
A$ -- we notate the end of word flag with $
Tuyệt quá. Bây giờ, giả sử chúng ta muốn thêm AB. Chúng tôi đã có một nút cho "A", vì vậy hãy thêm vào đó nút "B $":
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
và bây giờ chúng tôi có
^
|
A
/ \
A$ B$
Cứ tiếp tục như vậy. Tất nhiên, thay vì viết "root.Children [0] ...", bạn sẽ viết một vòng lặp tìm kiếm trie để xem liệu nút bạn muốn có tồn tại hay không, và nếu không, hãy tạo nó.
Để lưu trữ trie của bạn trên đĩa - thành thật mà nói, tôi sẽ chỉ lưu trữ danh sách từ dưới dạng tệp văn bản thuần túy và xây dựng lại trie khi bạn cần. Sẽ không mất quá 30 giây hoặc lâu hơn, và sau đó bạn có thể sử dụng lại trie trong bộ nhớ. Nếu bạn muốn lưu trữ trie ở một số định dạng giống trie hơn, thì không khó để nghĩ ra định dạng tuần tự hóa.
Để tìm kiếm bộ ba để khớp với một giá đỡ, ý tưởng là khám phá mọi bộ phận của bộ ba, nhưng để loại bỏ những khu vực mà giá đỡ có thể không khớp. Nếu bạn chưa có bất kỳ nút "A" nào trên giá, bạn không cần phải đi xuống bất kỳ nút "A" nào. Tôi đã phác thảo thuật toán tìm kiếm trong câu hỏi trước của bạn.
Tôi đã có một triển khai của một bộ ba liên tục theo phong cách chức năng mà tôi đã định viết blog trong một thời gian nhưng chưa bao giờ hiểu được nó. Nếu cuối cùng tôi đăng, tôi sẽ cập nhật câu hỏi này.
