java - 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;
    }
}

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

まず、検索で使用している TrieNode に関するメタデータを保持するヘルパー クラスを作成しました。

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

これは、Trie を保持し、ランダムな単語の検索を実装するクラスです。私は初心者なので、これを行うより良い方法があるかもしれませんが、これを少しテストしたところ、うまくいくようです。エラー処理はありませんので、emptor に注意してください。

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";
    }
}

カジュアルな辞書 (80k ワード、最大長 12) を使用すると、getRandomWord() への各呼び出しに約 0.2 ミリ秒かかり、より完全な辞書 (250K ワード、最大長 24) を使用すると、各呼び出しに約 1 ミリ秒かかります。