8

私はトライの背後にある概念を理解しています。しかし、実装に関しては少し混乱します。

Trieタイプを構造化するために私が考えることができる最も明白な方法はTrie、内部を維持することDictionary<char, Trie>です。私は実際にこのように書いたので、それは機能しますが...これはやり過ぎのようです。私の印象では、トライは軽量である必要があり、ノードごとDictionary<char, Trie>に個別に設定することは、私にはそれほど軽量ではないように思われます。

私が見逃しているこの構造を実装するためのより適切な方法はありますか？

更新：OK！Jonとleppieからの非常に有益な入力に基づいて、これは私がこれまでに思いついたものです。

（1）Trieタイプのプライベート_nodesメンバーを持つタイプがありTrie.INodeCollectionます。

（2）Trie.INodeCollectionインターフェイスには次のメンバーがあります。 

interface INodeCollection
{
    bool TryGetNode(char key, out Trie node);
    INodeCollection Add(char key, Trie node);
    IEnumerable<Trie> GetNodes();
}

（3）このインターフェースには3つの実装があります。 

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）aTrieが最初に構築されるとき、その_nodesメンバーはnullです。上記の手順に従って、の最初の呼び出しでをAdd作成しSingleNode、その後の呼び出しでそこから移動します。Add

これは意味がありますか？これは、aの「かさばり」をいくらか減らすという意味での改善のように感じます（ノードは、十分な数の子ができるまで、Trie本格的なオブジェクトではなくなります）。Dictionary<char, Trie>ただし、それは非常に複雑になっています。複雑すぎませんか？簡単なはずの何かを達成するために複雑なルートをとったことがありますか？

4

4 に答える 4

4

さて、あなたは各ノードが効果的に実装する何かを持っている必要がありますIDictionary<char, Trie>。サブノードの数に基づいて内部構造を変更する独自のカスタム実装を作成できます。

  • 単一のサブノードの場合は、acharとaだけを使用しますTrie
  • 少数の場合は、List<Tuple<char, Trie>>またはを使用しますLinkedList<Tuple<char,Trie>>
  • 多数の場合は、Dictionary<char, Trie>

（レピーの答えを見たばかりですが、これは彼が話している一種のハイブリッドアプローチだと思います。）

于 2010-09-08T07:07:52.140 に答える
3

私の考えでは、それを辞書として実装することは、Trieを実装することではありません-それは辞書の辞書を実装することです。

私がトライを実装したとき、Damien_The_Unbeliever（そこに+1）によって提案されたのと同じ方法でそれを実行しました：

public class TrieNode
{
  TrieNode[] Children = new TrieNode[no_of_chars];
}

これには、理想的には、トライがで示される文字の限られたサブセットのみをサポートし、no_of_chars入力文字を出力インデックスにマップできることが必要です。たとえば、AZをサポートしている場合は、当然、Aを0に、Zを25にマップします。

次に、ノードの存在を追加/削除/チェックする必要がある場合は、次のようにします。

public TrieNode GetNode(char c)
{
  //mapping function - could be a lookup table, or simple arithmetic
  int index = GetIndex(c);
  //TODO: deal with the situation where 'c' is not supported by the map
  return Children[index];
}

実際には、これが最適化されているのを確認しました。たとえば、AddNodeはref TrieNode、ノードがオンデマンドで新しくなり、親のTrieNodeのChildren正しい場所に自動的に配置されるようになります。

代わりに三分探索木を使用することもできます。これは、トライのメモリオーバーヘッドがかなりクレイジーになる可能性があり（特に、32kのUnicode文字すべてをサポートする場合）、TSTのパフォーマンスはかなり印象的です（プレフィックスとワイルドカードの検索もサポートします。ハミング検索と同様に）。同様に、TSTは、マッピングを行うことなく、すべてのUnicode文字をネイティブにサポートできます。絶対インデックス値ではなく、大なり記号/小なり記号の操作で機能するためです。

私はここからコードを取り、それを少し適応させました（ジェネリックスの前に書かれました）。

TSTに驚かれると思います。実装した後は、Triesから完全に離れました。

唯一注意が必要なのは、TSTのバランスを保つことです。Triesにはない問題。

于 2010-09-08T09:18:39.737 に答える
3

文字が限られたセット（たとえば、大文字のラテンアルファベットのみ）からのものである場合は、26要素の配列を格納でき、各ルックアップは

Trie next = store[c-'A']

ここで、cは現在のルックアップ文字です。

于 2010-09-08T09:20:12.700 に答える
2

いくつかの方法がありますが、単一のリンクリストを使用するのがおそらく最も簡単で軽量です。

各ノードが持つ子ノードの数を確認するために、いくつかのテストを行います。それほど多くない場合（たとえば20以下）、リンクリストアプローチはハッシュテーブルよりも高速である必要があります。子ノードの数に応じて、ハイブリッドアプローチを実行することもできます。

于 2010-09-08T07:04:03.787 に答える