5

トライの概念が理解できません。「トライ」ウィキペディアのエントリから、次の写真があります。 ここに画像の説明を入力

これが正しく表示されている場合、トライのすべてのリーフ ノードには単語全体が綴られており、すべての親ノードは最後のリーフ ノードまでの文字を保持しています。したがって、によって定義された DigitalTreeNode というクラスがある場合

public class DigitalTreeNode {
       public boolean isAWord;
       public String wordToHere; (compiles all the characters in a word together)
       public Map<String, DTN> children;
}

トライで最も長い単語を返すメソッドを実装したい場合、各リーフ ノードで最も長い単語を見つけるだけでよいでしょうか? 次のような方法をどのように実装しますか。

public static String longestWord (DigitalTreeNode d);

最長の文字列変数を設定し、各ノードを再帰的に調べて、それが単語であるかどうか、それが単語であり、その長さが最長の変数よりも大きい場合は、 longest = newWordLength を確認する必要があると思います。しかし、マップの子がどのように収まるかはわかりません。上記の方法を使用して、トライで最も長い単語を見つけるにはどうすればよいでしょうか?

4

2 に答える 2

6

通常、リーフ ノードには文字列全体が含まれているわけではありませんが (可能ですが)、多くの場合、リーフ ノードには、これが文字列の末尾であることを示す '$' 記号が含まれているだけです。

トライで最も長い単語を見つけるには、ツリーでBFSを使用して、最初に「最後の」葉を見つけます。「最後のリーフ」は、BFS キューからポップされた最後の要素です (ポップされた後、BFS のアルゴリズムは空のキューで停止しました)。
このリーフから実際の単語を取得するには、リーフからルートに戻る必要があります。このスレッドでは、それを行う方法について説明しました。

この解はO(|S| * n)で、|S|は文字列の平均の長さ、nは DS 内の文字列の数です。

トライDSを操作できれば、もっとうまくできると思います（ただし、この質問では問題ではないようです）

擬似コード:

findLongest(trie):
  //first do a BFS and find the "last node"
  queue <- []
  queue.add(trie.root)
  last <- nil
  map <- empty map
  while (not queue.empty()):
     curr <- queue.pop()
     for each son of curr:
        queue.add(son)
        map.put(son,curr) //marking curr as the parent of son
     last <- curr
  //in here, last indicate the leaf of the longest word
  //Now, go up the trie and find the actual path/string
  curr <- last
  str = ""
  while (curr != nil):
      str = curr + str //we go from end to start   
      curr = map.get(curr)
  return str
于 2012-11-02T08:53:16.823 に答える