0

サブ文字列とその出現回数の両方を文字列に格納するトライを実装しています。私のトライの各ノードには、メインノードのサブノードを格納するchildrenというマップがあります。

私の問題は、最終的にはそれらのサブノードに独自のサブノードがあり、いわば「マップ内のマップ内のマップ...」からデータを取得する方法がわからないことです。

これが私がこれまでに持っているものです：

private class TrieNode
{
    private T data; //will hold the substring
    int count; //how many occurrences of it were in the string
    private Map<TrieNode, Integer> children; //will hold subnodes
    private boolean isWord; //marks the end of a word if a substring is the last substring of a String

    private TrieNode(T data)
    {
        this.data = data;
        count = 1;
        children = new HashMap<TrieNode, Integer>();
        isWord = false;
    }
}

サブノードからデータを取得するにはどうすればよいですか？サブノードの下に他のサブノードがある可能性がありますか？

PS十分に明確に説明できなかった場合は、お詫び申し上げます。再帰に問題があります。ありがとう。

4

2 に答える 2

1

Tという型に文字列を格納する理由がわかりません。これはジェネリック型のように聞こえますが、クラスで宣言していません。

Map<T, TrieNode>とにかく、サブストリングでキー設定された各子を保持するが必要になると思います。そうすればTrieNode、同じ種類の別のマップを持つ別のマップに戻ります。

于 2012-10-28T21:40:30.077 に答える
1

いくつか必要です。まず第一にMap<T, TrieNode>、データの一部をサブトライにマッピングしているため、必要です。

次に、データを頭と尾に分割する方法と、後でそれらを再結合する方法を知る必要があります。文字列の標準的なケースでは、部分文字列と連結を使用します。例えば：

private TrieNode(String currChar, String rest) {
   this.data = currChar;
   this.children = new HashMap<String, TrieNode>();
   if(rest.isEmpty()) {
      this.isWord = true;
   } else {
      String head = rest.substring(0, 1);
      String tail = rest.substring(1, rest.length());
      this.children.add(head, new TrieNode(head, tail);
   }
}

T同様のことを行う必要があるか、そもそも Trie を使用しても意味がありません。

さらに、Trie から文字列を再コンパイルする必要はほとんどありません。通常、Trie に文字列が存在するかどうか、または部分文字列である文字列の数を確認するだけです。

于 2012-10-28T22:23:24.790 に答える