Tôi lấy khái niệm đằng sau một số trie. Nhưng tôi hơi bối rối khi nói đến việc thực hiện.Điều gì sẽ là một cách hợp lý để thực hiện một Trie trong .NET?
Cách rõ ràng nhất tôi có thể nghĩ đến cấu trúc loại Trie sẽ là để có một Trie duy trì một nội bộ Dictionary<char, Trie>. Tôi có trong thực tế bằng văn bản một cách này, và nó hoạt động, nhưng ... điều này có vẻ như quá mức cần thiết. Ấn tượng của tôi là một bộ ba phải nhẹ và có một số Dictionary<char, Trie> riêng cho mỗi nút không có vẻ rất nhẹ đối với tôi.
Có cách nào thích hợp hơn để triển khai cấu trúc này mà tôi đang thiếu không?
CẬP NHẬT: OK! Dựa trên đầu vào rất hữu ích từ Jon và leppie, đây là những gì tôi đã đưa ra cho đến nay:
(1) Tôi có các loại Trie, trong đó có một tin _nodes viên của loại Trie.INodeCollection.
(2) Giao diện Trie.INodeCollection có các thành viên sau:
interface INodeCollection
{
bool TryGetNode(char key, out Trie node);
INodeCollection Add(char key, Trie node);
IEnumerable<Trie> GetNodes();
}
(3) Có ba triển khai của giao diện này:
class SingleNode : INodeCollection
{
internal readonly char _key;
internal readonly Trie _trie;
public SingleNode(char key, Trie trie)
{ /*...*/ }
// Add returns a SmallNodeCollection.
}
class SmallNodeCollection : INodeCollection
{
const int MaximumSize = 8; // ?
internal readonly List<KeyValuePair<char, Trie>> _nodes;
public SmallNodeCollection(SingleNode node, char key, Trie trie)
{ /*...*/ }
// Add adds to the list and returns the current instance until MaximumSize,
// after which point it returns a LargeNodeCollection.
}
class LargeNodeCollection : INodeCollection
{
private readonly Dictionary<char, Trie> _nodes;
public LargeNodeCollection(SmallNodeCollection nodes, char key, Trie trie)
{ /*...*/ }
// Add adds to the dictionary and returns the current instance.
}
(4) Khi một Trie được xây dựng đầu tiên, thành viên _nodes của mình là null. Cuộc gọi đầu tiên để Add tạo một SingleNode và các cuộc gọi tiếp theo tới Add sẽ chuyển từ đó, theo các bước được mô tả ở trên.
Điều này có hợp lý không? Điều này cảm thấy như một sự cải tiến theo nghĩa là nó hơi giảm "bulkiness" của một Trie (nút không còn full-blown Dictionary<char, Trie> đối tượng cho đến khi họ có đủ số lượng trẻ em). Tuy nhiên, nó cũng trở nên phức tạp hơn nhiều. Nó có quá phức tạp không? Tôi đã có một con đường phức tạp để đạt được một cái gì đó nên đã được đơn giản?
Bạn cũng có thể nén đuôi, như trường hợp subnode đơn. – leppie