किसी दिए गए पाठ को शब्दकोश से शब्दों में कैसे विभाजित करें?

Question

यह एक साक्षात्कार प्रश्न है। मान लें कि आपके पास स्ट्रिंग text और dictionary (तारों का एक सेट) है। आप text को सबस्ट्रिंग में कैसे विभाजित करते हैं जैसे कि प्रत्येक सबस्ट्रिंग dictionary में पाई जाती है।

उदाहरण के लिए आप "thisisatext"["this", "is", "a", "text"]/usr/share/dict/words का उपयोग कर तोड़ सकते हैं।

मैं इस समस्या को हल कर सकते हैं (छद्म जावा में) उलटे पांव लौटने से विश्वास:

 
void solve(String s, Set<String> dict, List<String> solution) { 
    if (s.length == 0) 
     return 
    for each prefix of s found in dict 
     solve(s without prefix, dict, solution + prefix) 
} 

List<String> solution = new List<String>() 
solve(text, dict, solution) 

यह मतलब है? क्या आप शब्दकोश में उपसर्गों को खोजने का चरण अनुकूलित करेंगे? आप किस डेटा संरचना की सिफारिश करेंगे?

Answer 1

यह समाधान शब्दकोश के लिए Trie डेटा संरचना के अस्तित्व को मानता है। इसके अलावा, ट्री में प्रत्येक नोड के लिए, निम्नलिखित कार्य मानते हैं:

1. नोड।IsWord(): वास्तविक लौटता है यदि उस नोड के लिए पथ एक शब्द
2. node.IsChild (चार एक्स) है: वास्तविक लौटता है यदि लेबल के साथ एक बच्चे x
3. node.GetChild (चार एक्स) मौजूद है: बच्चे को देता है लेबल के साथ नोड एक्स

Function annotate(String str, int start, int end, int root[], TrieNode node): 
i = start 
while i<=end: 
    if node.IsChild (str[i]): 
     node = node.GetChild(str[i]) 
     if node.IsWord(): 
      root[i+1] = start 
     i+=1 
    else: 
     break; 

end = len(str)-1 
root = [-1 for i in range(len(str)+1)] 
for start= 0:end: 
    if start = 0 or root[start]>=0: 
     annotate(str, start, end, root, trieRoot) 

index 0 1 2 3 4 5 6 7 8 9 10 11 
str: t h i s i s a t e x t 
root: -1 -1 -1 -1 0 -1 4 6 -1 6 -1 7 

मैं तुम्हें ऐसे शब्द हैं जो रिवर्स जड़ traversing द्वारा स्ट्रिंग को बनाने वाली सूची के लिए हिस्सा छोड़ देंगे।

समय जटिलता हे (nk) जहां n स्ट्रिंग की लंबाई और कश्मीर शब्दकोश में सबसे लंबा शब्द की लंबाई है।

पुनश्च: मैं शब्दकोश में इन शब्दों संभालने हूँ:, यह, एक, पाठ, खा लिया।

Answer 2

दृष्टिकोण 1- Trie यहां एक करीबी फिट होने लगते हैं। अंग्रेजी शब्दकोश में शब्दों का trie उत्पन्न करें। यह त्रिभुज इमारत एक बार लागत है। त्रिभुज के निर्माण के बाद आपके string आसानी से पत्र द्वारा पत्र की तुलना की जा सकती है। यदि किसी भी समय आप त्रिभुज में एक पत्ता का सामना करते हैं तो आप मान सकते हैं कि आपको एक शब्द मिला है, इसे एक सूची में जोड़ें & अपने ट्रैवर्सल के साथ आगे बढ़ें। जब तक आप अपने string के अंत तक पहुंच गए हैं तब तक ट्रैवर्सल करें। सूची आउटपुट है।

खोज के लिए समय जटिलता - ओ (word_length)।

स्पेस कॉम्प्लेक्सिटी - ओ (वर्णमाला * word_length * no_words)। आपके शब्दकोश का आकार

दृष्टिकोण 2 - मैं Suffix Trees बारे में सुना है, कभी नहीं उन्हें इस्तेमाल किया, लेकिन यह यहाँ उपयोगी हो सकता है।

दृष्टिकोण 3 - अधिक पंडिताऊ & एक घटिया विकल्प नहीं है। आपने पहले ही यह सुझाव दिया है।

आप दूसरी तरफ कोशिश कर सकते हैं। dict के माध्यम से चलाएं उप-स्ट्रिंग मिलान की जांच है। यहां मुझे लगता है कि dict में कुंजियां /usr/share/dict/words के words हैं। (1) सबस्ट्रिंग मिलान के लिए पूरे dict + O के माध्यम से हे (एन) चल रहा है -

(list) splitIntoWords(String str, dict d) 
{ 
    words = [] 
    for (word in d) 
    { 
     if word in str 
      words.append(word); 
    } 
    return words; 
} 

जटिलता - तो छद्म कोड कुछ इस तरह लग रहा है।

स्पेस - सबसे ज्यादा मामले हे (एन) यदि len(words) == len(dict)

के रूप में अन्य लोगों ने बताया है, इस बैक ट्रैकिंग आवश्यकता होती है।

Answer 3

(एन^2) समय इस blog post.

मूल विचार सिर्फ समारोह आपके द्वारा लिखी गई memoize करने के लिए और आप एक हे होगा है में इस समस्या का समाधान करने के लिए एक बहुत ही गहन writeup है, ओ (एन) अंतरिक्ष एल्गोरिदम।

Answer 4

आप इस समस्या Dynamic Programming और Hashing का उपयोग कर हल कर सकते हैं।

शब्दकोश में प्रत्येक शब्द का हैश की गणना। हैश फ़ंक्शन का उपयोग करें जो आपको सबसे ज्यादा पसंद है। मैं कुछ ऐसा उपयोग करूंगा (ए 1 * बी^(एन -1) + ए 2 * बी^(एन -2) + ... + ए * बी^0)% पी, जहां a1a2 ... एक स्ट्रिंग है, n स्ट्रिंग की लंबाई है, बी बहुपद का आधार है और पी एक बड़ी प्रधान संख्या है। यदि आपके पास स्ट्रिंग a1a2 का हैश मान है ... आप स्ट्रिंग a1a2 के एश मान की गणना कर सकते हैं ... ana (n + 1) निरंतर समय में: (हैशवैल्यू (ए 1 ए 2 ... ए) * बी + ए (एन + 1))% पी

इस भाग की जटिलता ओ (एन * एम) है, जहां एन शब्दकोश में शब्दों की संख्या है और एम शब्दकोश में सबसे लंबे शब्द की लंबाई है।

फिर, इस तरह एक डीपी समारोह का उपयोग करें:

bool vis[LENGHT_OF_STRING]; 
    bool go(char str[], int length, int position) 
    { 
     int i; 

     // You found a set of words that can solve your task. 
     if (position == length) { 
      return true; 
     } 

     // You already have visited this position. You haven't had luck before, and obviously you won't have luck this time. 
     if (vis[position]) { 
     return false; 
     } 
     // Mark this position as visited. 
     vis[position] = true; 

     // A possible improvement is to stop this loop when the length of substring(position, i) is greater than the length of the longest word in the dictionary. 
     for (i = position; position < length; i++) { 
     // Calculate the hash value of the substring str(position, i); 
     if (hashValue is in dict) { 
      // You can partition the substring str(i + 1, length) in a set of words in the dictionary. 
      if (go(i + 1)) { 
       // Use the corresponding word for hashValue in the given position and return true because you found a partition for the substring str(position, length). 
       return true; 
      } 
     } 
     } 

     return false; 
    } 

इस एल्गोरिथ्म की जटिलता हे (एन * एम), जहां एन स्ट्रिंग की लंबाई है और एम सबसे लंबा शब्द की लंबाई है शब्दकोश या ओ (एन^2) में, निर्भर करता है कि आपने सुधार को कोड किया है या नहीं।

तो एल्गोरिथ्म की कुल जटिलता हो जाएगा: हे (एन 1 * एम) + O (एन 2 * एम) (या हे (एन 2^2)), जहां एन 1 शब्दकोश में शब्दों की संख्या है, एम है शब्दकोश में सबसे लंबे शब्द की लंबाई और एन 2 स्ट्रिंग का लंबाई है)।

यदि आप एक अच्छा हैश फ़ंक्शन (जहां कोई टक्कर नहीं है) के बारे में नहीं सोच सकते हैं, तो अन्य संभावित समाधान ट्रे या पेट्रीसिया ट्राई का उपयोग करना है (यदि सामान्य ट्राई का आकार बहुत बड़ा है) (मैं नहीं कर सकता इन विषयों के लिए लिंक पोस्ट नहीं करें क्योंकि मेरी प्रतिष्ठा 2 से अधिक लिंक पोस्ट करने के लिए पर्याप्त नहीं है)। लेकिन आप इसका उपयोग करते हैं, आपके एल्गोरिदम की जटिलता ओ (एन * एम) * ओ (ट्राई में एक शब्द खोजने के लिए आवश्यक समय) होगी, जहां एन स्ट्रिंग की लंबाई है और एम सबसे लंबा शब्द की लंबाई है शब्दकोश में।

मुझे आशा है कि यह मदद करता है, और मैं अपने गरीब अंग्रेजी के लिए क्षमा चाहते हैं।