Belirli bir uzunluktaki rastgele bir kelimeyi bir Trie'den nasıl alabilirim?

Question

Basit bir Trie'im var, yaklaşık 80k kelimelik uzunluğu 2 - 15 arasında saklamak için kullanıyorum. Bir dizenin bir kelime olup olmadığını kontrol etmek için harika çalışıyor ; Ancak, şimdi belirli bir uzunlukta rastgele bir kelime elde etmenin bir yoluna ihtiyacım var. Başka bir deyişle, 5 harfli bir kelime döndürmek için "getRandomWord (5)" e ihtiyacım var.

Düşünebildiğim tek yol, rastgele bir sayı seçip, ağaç genişliğini çaprazlamaktır; Bunu yapmanın daha iyi bir yolu var mı?

Muhtemelen gereksiz, ama işte benim için çerez.

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

Düzenleme: İşaretli cevap iyi çalıştı; Benzer bir sorunu olan herkese yardımcı olması durumunda, uygulamamı buraya posterciliği için ekleyeceğim.

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

Bu TRIE tutan ve rastgele kelime için arama uygulayan sınıftır:

Birincisi, ben arama kullanıyorum TrieNodes hakkında meta verileri tutmak için bir yardımcı sınıf yaptı. Yeni başlayanlardan biriyim, bu yüzden bunu yapmanın daha iyi yolları olabilir, ama bunu biraz test ettim ve işe yaramış gibi görünüyor. Hata işleme yok, bu yüzden uyarı yap. Rahat bir sözlüğü (80k kelime maksimum uzunluk 12) getRandomWord her() çağrısı kullanarak

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 alır ve (250 bin kelime, maksimum uzunluk 24) her bir arama yaklaşık 1 ms sürer daha kapsamlı sözlük kullanılarak.

Answer 1

Her 5 harfli kelimeyi alma şansınız olduğundan emin olmak için, ağacınızda kaç tane 5 harfli kelime olduğunu bilmeniz gerekir. Eğer ağaç oluşturmak Yani olarak, size iki sayaçları eklemeler yapıyoruz kelimenin uzunluğunu ekleyin: Genel bir frekans sayacı ve bir yan harfi frekans sayacı:

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

4000 5-mektup Yani eğer ve 213 tanesi kelimeleri daha sonra, "d" ile başlayan

lengthFrequencyByLetter[3][4] = 213 

ve size ağacına şeyi eklemeyi tamamladıktan sonra

totalLengthFrequency[4] = 4000 

. Eğer n olan belirli bir length ait n inci kelime, bir arama yapabilir ve Buradan

("a" harfi 0 "b" 1'dir, ... "z" 25'tir) (0, totalLengthFrequency[length-1]) aralığında rastgele bir dağılımdan rastgele seçilen bir tam sayı.

Yapınıza 4000 adet 5 harfli kelimeniz olduğunu varsayalım. Sen, 1234 kadar bir miktarla sınırlı kadar Sonra 1234 5 harfli kelimenin başlangıç ​​harfi hızla biliyorum, Şimdi

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

sırayla kontrol edebilirsiniz rasgele sayı 1234. almak ve sonra orada arayın. Her seferinde ağaçtan her kelimeyi aramak zorunda değilsin.