Jak odzyskać losowe słowo o określonej długości od Trie

Question

Mam prostego Triego, którego używam do przechowywania około 80k słów o długości 2 - 15. Działa świetnie, sprawdzając, czy ciąg jest słowem ; Jednak teraz potrzebuję sposobu na uzyskanie losowego słowa o określonej długości. Innymi słowy, potrzebuję "getRandomWord (5)", aby zwrócić 5-literowe słowo, przy czym wszystkie 5-literowe słowa mają taką samą szansę na zwrot.

Jedynym sposobem, jaki mogę wymyślić, to wybranie losowej liczby i przemierzenie szerokości drzewa - najpierw dopóki nie przekażę wielu słów o pożądanej długości. Czy jest lepszy sposób to zrobić?

Prawdopodobnie niepotrzebny, ale oto kod dla mojego 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; 
    } 
} 

Edytuj: Zaznaczona odpowiedź działa dobrze; Dodam tutaj moją implementację dla potomności, na wypadek gdyby pomogła ona każdemu z podobnym problemem.

Najpierw zrobiłem klasy pomocnika do przechowywania metadanych o TrieNodes używam w poszukiwaniu:

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

Jest to klasa, która posiada Trie i wdraża poszukiwania losowego słowa. Jestem trochę początkującym, więc mogą być lepsze sposoby na zrobienie tego, ale testowałem to trochę i wydaje się, że działa. Brak obsługi błędów, więc ograniczaj 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"; 
    } 
} 

Stosując swobodna słownika (80k słowa maksymalna długość 12) każdego wywołania getRandomWord() wykonuje abount .2ms lub stosując bardziej dokładne słownika (250K słowa, maksymalna długość 24) każdego połączenia trwające około 1 ms.

Answer 1

Aby mieć pewność, że masz szansę na uzyskanie każdego 5-literowego słowa, musisz wiedzieć, ile jest 5-literowych słów w twoim drzewie. Tak skonstruować drzewo, należy dodać długość słowa jesteś dodając do dwóch liczników: ogólny licznik częstotliwości, a licznik przez pisma Częstotliwość:

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

więc jeśli masz 4000 5-list słowa, a 213 z nich zaczynają się na "d", a następnie

lengthFrequencyByLetter[3][4] = 213 

i

totalLengthFrequency[4] = 4000 

po zakończeniu dodawania wszystko do drzewa. (Litera "a" wynosi 0, "b" wynosi 1, ... "z" jest 25.)

Stąd można zrobić wyszukiwania dla n th słowa danego length, gdzie jest n losowa liczba całkowita wybrana z jednolitego rozkładu losowego, w zakresie (0, totalLengthFrequency[length-1]).

Załóżmy, że masz 4000 pięcioliterowych słów w swojej strukturze. Wybrać losowy numer 1234. Teraz można sprawdzić

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

z kolei, dopóki nie przekroczy łącznie 1234. Wtedy wiesz, co szybko pismo początek 1234th 5-literowego słowa jest, a potem szukać. Nie musisz przeszukiwać każdego słowa w drzewie od początku za każdym razem.