Wie man ein zufälliges Wort einer gegebenen Länge von einem Trie

Question

abruft Ich habe eine einfache Trie, die ich verwende, um etwa 80k Wörter der Länge 2 - 15 zu speichern. Es funktioniert hervorragend, um zu überprüfen, ob eine Zeichenfolge ein Wort ist ; Aber jetzt brauche ich eine Möglichkeit, ein zufälliges Wort von einer bestimmten Länge zu bekommen. Mit anderen Worten, ich brauche "getRandomWord (5)", um ein Wort mit 5 Buchstaben zurückzugeben, wobei alle Wörter mit 5 Buchstaben die gleiche Chance haben, zurückgegeben zu werden.

Der einzige Weg, an den ich denken kann, ist eine Zufallszahl auszuwählen und die Baumbreite zuerst zu durchlaufen, bis ich die vielen Wörter der gewünschten Länge passiert habe. Gibt es einen besseren Weg, dies zu tun?

Möglicherweise unnötig, aber hier ist der Code für meine Trie.

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

Edit: Die markierte Antwort hat gut funktioniert; Ich werde meine Implementierung hier für die Nachwelt hinzufügen, falls es jemandem mit einem ähnlichen Problem hilft.

Zuerst habe ich eine Hilfsklasse Metadaten über die TrieNodes zu halten, ich bin in der Suche mit:

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

Dies ist die Klasse, die die Trie und implementiert die Suche nach dem Zufallswort hält. Ich bin ein Anfänger, also könnte es bessere Möglichkeiten geben, dies zu tun, aber ich habe es ein bisschen getestet und es scheint zu funktionieren. Keine Fehlerbehandlung, daher Vorbehalte 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"; 
    } 
} 

eine lässige Wörterbuch (80k Wörter max Länge 12) jeder Aufruf getRandomWord Verwendung() nimmt abount .2ms und eine gründlichere Wörterbuch mit (250K Wörter, max Länge 24), jeder Anruf dauert etwa 1 ms.

Answer 1

Um sicherzustellen, dass Sie eine gleichmäßige Chance haben, jedes 5-Buchstaben-Wort zu erhalten, müssen Sie wissen, wie viele 5-Buchstaben-Wörter es in Ihrem Baum gibt. So wie Sie den Baum konstruieren, fügen Sie die Länge des Wortes Sie zwei Zähler Hinzufügen sind: eine Gesamtfrequenzzähler und ein Neben Brief Frequenzzähler:

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

Also, wenn Sie 4000 mit 5 Buchstaben Worte, und 213 von ihnen mit "d", dann

lengthFrequencyByLetter[3][4] = 213 

und

totalLengthFrequency[4] = 4000 

starten, nachdem Sie alles zu Ihrem Baum fertig sind hinzufügen. (Der Buchstabe "a" 0 ist, "b" ist 1, ... "z" ist 25.)

Von hier aus können Sie eine Suche nach dem n te Wort eines gegebenen length tun können, wo n ist eine zufällige ganze Zahl, ausgewählt aus einer gleichmäßigen Zufallsverteilung, in dem Bereich (0, totalLengthFrequency[length-1]).

Nehmen wir an, Sie haben 4000 Wörter mit 5 Buchstaben in Ihrer Struktur. Sie wählen Zufallszahl 1234. Jetzt können Sie

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

wiederum prüfen, bis Sie insgesamt 1234. überschreiten Dann wissen Sie schnell, was die Startbuchstaben der 1234. 5-Buchstaben-Wort ist, und dann gibt suchen. Sie müssen nicht jedes Wort im Baum von Anfang an jedes Mal suchen.