Trieから与えられた長さのランダムな単語を取り出す方法

Question

私は長さ2〜15の約80k単語を保存するために使用しているシンプルなTrieを持っています。これは文字列が単語;しかし、今私は、任意の長さのランダムな単語を取得する方法が必要です。言い換えれば、5文字の単語を返すために "getRandomWord（5）"が必要で、5文字すべての単語が返される可能性は同じです。

私が考えることができる唯一の方法は、乱数を選んで木の横を横切ることです。最初にその長さの単語をいくつか渡します。これを行うより良い方法はありますか？

おそらく不要ですが、ここに私のトライのコードがあります。

class TrieNode { 
    private TrieNode[] c; 
    private Boolean end = false; 

    public TrieNode() { 
     c = new TrieNode[26]; 
    } 

    protected void insert(String word) { 
     int n = word.charAt(0) - 'A'; 
     if (c[n] == null) 
      c[n] = new TrieNode(); 
     if (word.length() > 1) { 
      c[n].insert(word.substring(1)); 
     } else { 
      c[n].end = true; 
     } 
    } 

    public Boolean isThisAWord(String word) { 
     if (word.length() == 0) 
      return false; 
     int n = word.charAt(0) - 'A'; 
     if (c[n] != null && word.length() > 1) 
      return c[n].isThisAWord(word.substring(1)); 
     else if (c[n] != null && c[n].end && word.length() == 1) 
      return true; 
     else 
      return false; 
    } 
} 

編集：マークされた回答はうまくいきました。同様の問題を抱えている人に役立つ場合は、私の実装を後世のためにここに追加します。

まず、私は、検索に使用していTrieNodesに関するメタデータを保持するためのヘルパークラスを作った：

class TrieBranch { 
    TrieNode node; 
    int letter; 
    int depth; 
    public TrieBranch(TrieNode n, int l, int d) { 
     letter = l; node = n; depth = d; 
    } 
} 

これはトライを保持し、ランダムな単語の検索を実装するクラスです。私は初心者のようなので、これを行うより良い方法があるかもしれませんが、私はこれを少しテストし、それは動作するようです。エラー処理はありませんので、emptorに注意してください。カジュアル辞書（80Kワードの最大長12）getRandomWordへの各呼び出し（）を使用

class Dict { 

    final static int maxWordLength = 13;  
    final static int lettersInAlphabet = 26; 
    TrieNode trie; 
    int lengthFrequencyByLetter[][]; 
    int totalLengthFrequency[]; 

    public Dict() { 
     trie = new TrieNode(); 
     lengthFrequencyByLetter = new int[lettersInAlphabet][maxWordLength + 1]; 
     totalLengthFrequency = new int[maxWordLength + 1]; 
    } 

    public String getRandomWord(int length) { 
     // Returns a random word of the specified length from the trie 
     // First, pick a random number from 0 to [number of words with this length] 
     Random r = new Random(); 
     int wordIndex = r.nextInt(totalLengthFrequency[length]); 

     // figure out what the first letter of this word would be 
     int firstLetter = -1, totalSoFar = 0; 
     while (totalSoFar <= wordIndex) { 
      firstLetter++; 
      totalSoFar += lengthFrequencyByLetter[firstLetter][length]; 
     } 
     wordIndex -= (totalSoFar - lengthFrequencyByLetter[firstLetter][length]); 

     // traverse the (firstLetter)'th node of trie depth-first to find the word (wordIndex)'th word 
     int[] result = new int[length + 1]; 
     Stack<TrieBranch> stack = new Stack<TrieBranch>(); 
     stack.push(new TrieBranch(trie.getBranch(firstLetter), firstLetter, 1)); 
     while (!stack.isEmpty()) { 
      TrieBranch n = stack.pop(); 
      result[n.depth] = n.letter; 

      // examine the current node 
      if (n.depth == length && n.node.isEnd()) { 
       wordIndex--; 
       if (wordIndex < 0) { 
        // search is over 
        String sResult = ""; 
        for (int i = 1; i <= length; i++) { 
         sResult += (char)(result[i] + 'a'); 
        } 
        return sResult; 
       } 
      } 

      // handle child nodes unless they're deeper than target length 
      if (n.depth < length) { 
       for (int i = 25; i >= 0; i--) { 
        if (n.node.getBranch(i) != null) 
         stack.push(new TrieBranch(n.node.getBranch(i), i, n.depth + 1)); 
       } 
      } 
     } 
     return "failure of some sort"; 
    } 
} 

は.2ms abountかかり、及び（250Kワード、最大長24）より完全な辞書を使用して、各コールは1ミリ秒程度かかり。

Answer 1

各5文字の単語を取得する可能性があることを確認するには、ツリーに5文字の単語がいくつあるかを知る必要があります。全体的な周波数カウンタ、およびAによる文字周波数カウンタ：あなたは木を構築するように、あなたは二つのカウンタを追加している単語の長さを追加し

int lengthFrequencyByLetter[letterIndex][maxWordLength-1] 
int totalLengthFrequency[maxWordLength-1] 

ですから、4000 5文字を持っている場合あなたのツリーにすべてのものを追加し終わった後の単語、およびそれらの213は

lengthFrequencyByLetter[3][4] = 213 

と

totalLengthFrequency[4] = 4000 

そして、 "D" で始まります。あなたはnがある与えられたlengthのn番目の単語のための検索を行うことができ、ここから

（文字は「」0で、「b」は1で、...「z」は25です。） （0,totalLengthFrequency[length-1]）の範囲内の均一なランダム分布から選んだランダムな整数です。

あなたの構造に4000文字の英字が4000個あるとします。あなたが1234の合計を超えるまで、あなたは第千二百三十四5文字の単語の先頭文字があるすぐに知っている、今あなたが

lengthFrequencyByLetter[0][4] 
lengthFrequencyByLetter[1][4] 
lengthFrequencyByLetter[2][4] 
lengthFrequencyByLetter[3][4] 

順番に確認することができます乱数1234を選択した後、そこに検索します。毎回木のすべての単語を最初から検索する必要はありません。