ट्री

Question

से दी गई लंबाई के यादृच्छिक शब्द को कैसे पुनर्प्राप्त करें मेरे पास एक साधारण ट्री है जिसका उपयोग मैं लगभग 80k शब्दों की लंबाई 2 - 15 स्टोर करने के लिए कर रहा हूं। यह जांचने के लिए बहुत अच्छा काम करता है कि स्ट्रिंग एक शब्द है या नहीं ; हालांकि, अब मुझे दी गई लंबाई का यादृच्छिक शब्द प्राप्त करने का एक तरीका चाहिए। दूसरे शब्दों में, मुझे 5 अक्षर शब्द वापस करने के लिए "getRandomWord (5)" की आवश्यकता है, जिसमें सभी 5 अक्षर शब्दों को लौटने का बराबर मौका है।

एकमात्र तरीका मैं सोच सकता हूं कि यादृच्छिक संख्या चुनना और वृक्ष की चौड़ाई को पार करना है- जब तक कि मैं वांछित लंबाई के कई शब्द पारित नहीं कर लेता। क्या ऐसा करने के लिए इससे अच्छा तरीका है?

शायद अनावश्यक है, लेकिन यहां मेरे 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; 
    } 
} 

संपादित करें: चिह्नित उत्तर अच्छी तरह से काम किया; मैं यहां पोस्टरिटी के लिए अपना कार्यान्वयन जोड़ूंगा, अगर यह किसी भी समस्या के साथ किसी को भी मदद करता है।

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

इस वर्ग कि Trie रखती है और यादृच्छिक शब्द के लिए खोज को लागू करता है:

पहले, मैं TrieNodes मैं खोज में उपयोग कर रहा हूँ के बारे में मेटाडेटा धारण करने के लिए एक सहायक वर्ग बनाया है। मैं एक नौसिखिया हूं इसलिए ऐसा करने के बेहतर तरीके हो सकते हैं, लेकिन मैंने इसका थोड़ा परीक्षण किया और ऐसा लगता है कि यह काम करता है। कोई त्रुटि संभाल नहीं, तो चेतावनी 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 की प्रत्येक कॉल() का उपयोग करने के बारे में .2ms लेता है, और अधिक गहन शब्दकोश (250K शब्द है, अधिकतम सीमा 24) प्रत्येक कॉल 1ms के बारे में लेता है का उपयोग कर।

Answer 1

सुनिश्चित करें कि आप प्रत्येक 5 अक्षर का शब्द होने का एक और भी मौका है बनाने के लिए, आप को पता है कि कितने 5 अक्षर का शब्द आपकी पेड़ में हैं की जरूरत है। तो जैसा कि आप पेड़ का निर्माण, आप शब्द आप दो काउंटर करने के लिए जोड़ रहे हैं की लंबाई जोड़ें: एक समग्र आवृत्ति काउंटर, और एक से अक्षर आवृत्ति काउंटर:

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

तो अगर आप 4000 5 अक्षर है शब्द, और उनमें से 213 के साथ "डी" शुरू करते हैं, तो

lengthFrequencyByLetter[3][4] = 213 

और

totalLengthFrequency[4] = 4000 

के बाद आप अपने पेड़ के लिए सब कुछ जोड़ने काम हो गया।

यहाँ से

(पत्र "एक" 0 है, "बी" 1 है, ... "Z" 25 है), आप किसी दिए गए length की n वें शब्द है, जहां n है के लिए एक खोज कर सकते हैं एक यादृच्छिक पूर्णांक एक समान यादृच्छिक वितरण से उठाया, सीमा (0, totalLengthFrequency[length-1]) में।

मान लें कि अपने ढांचे में 4000 5 अक्षर का शब्द करते हैं। आप अब आप जाँच कर सकते हैं

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

बदले में यादृच्छिक संख्या 1234. लेने, जब तक आप 1234 के कुल से अधिक तो आप जानते हैं कि जल्दी से क्या 1234 5 अक्षर शब्द के आरंभ पत्र है, और फिर वहाँ खोज करते हैं। आपको हर बार शुरुआत से पेड़ में हर शब्द खोजना नहीं है।