अलग शब्दों का एक अनुक्रम

Question

मैं हाल ही में निम्नलिखित साक्षात्कार प्रश्न में आए में एक स्ट्रिंग को तोड़ने:

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

मुझे जटिलता के संबंध में एक इष्टतम समाधान नहीं मिल रहा है। क्या किसी को यह कुशलता से करने के तरीके पर कोई सुझाव है?

Answer 1

ऐसा लगता है कि प्रश्न वास्तव में मेरी साक्षात्कार समस्या है, उदाहरण के लिए मैंने post में नोसी चैनल में उपयोग किया था। खुशी है कि आपको समाधान पसंद आया। मुझे यकीन है कि आप ओ (एन^2) गतिशील प्रोग्रामिंग/ज्ञापन समाधान को हरा नहीं सकते हैं जो मैं सबसे खराब-केस प्रदर्शन के लिए वर्णन करता हूं।

यदि आपका शब्दकोश और इनपुट पैथोलॉजिकल नहीं है तो आप अभ्यास में बेहतर कर सकते हैं। उदाहरण के लिए, यदि आप रैखिक समय में पहचान सकते हैं तो इनपुट स्ट्रिंग के सबस्ट्रिंग्स शब्दकोश में हैं (उदा।, एक trie के साथ) और यदि इस तरह के substrings की संख्या स्थिर है, तो समग्र समय रैखिक होगा। बेशक, यह बहुत सारी धारणाएं हैं, लेकिन वास्तविक डेटा अक्सर पैथोलॉजिकल सबसे खराब मामले की तुलना में काफी अच्छा है।

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

Answer 2

एक विकल्प सभी मान्य अंग्रेजी शब्दों को एक तिहाई में स्टोर करना होगा। एक बार ऐसा करने के बाद, आप स्ट्रिंग में अक्षरों के बाद रूट को नीचे से ट्राई चलाना शुरू कर सकते हैं।

1. इस बिंदु पर इनपुट तोड़, या
2. शब्द का विस्तार जारी: जब भी आप एक नोड है कि एक शब्द के रूप में चिह्नित है मिल जाए, आप दो विकल्प हैं।

आप दावा कर सकते हैं कि एक बार आपके द्वारा इनपुट को तोड़ने के बाद एक मैच मिला है जो सभी कानूनी हैं और शेष शेष वर्ण शेष नहीं हैं। चूंकि प्रत्येक पत्र में आपके पास एक मजबूर विकल्प होता है (या तो आप एक ऐसा शब्द बना रहे हैं जो वैध नहीं है और रोकना चाहिए- या आप शब्द को विस्तारित रख सकते हैं) या दो विकल्प (विभाजित या चलते रहें), आप इस फ़ंक्शन को कार्यान्वित कर सकते हैं संपूर्ण प्रत्यावर्तन का उपयोग कर:

PartitionWords(lettersLeft, wordSoFar, wordBreaks, trieNode): 
    // If you walked off the trie, this path fails. 
    if trieNode is null, return. 

    // If this trie node is a word, consider what happens if you split 
    // the word here. 
    if trieNode.isWord: 
     // If there is no input left, you're done and have a partition. 
     if lettersLeft is empty, output wordBreaks + wordSoFar and return 

     // Otherwise, try splitting here. 
     PartitinWords(lettersLeft, "", wordBreaks + wordSoFar, trie root) 

    // Otherwise, consume the next letter and continue: 
    PartitionWords(lettersLeft.substring(1), wordSoFar + lettersLeft[0], 
        wordBreaks, trieNode.child[lettersLeft[0]) 

विकृतिविज्ञानी सबसे खराब स्थिति में इस स्ट्रिंग है, जो तेजी से लंबे समय से टी कर सकते हैं के सभी विभाजनों सूची जाएगा। हालांकि, यह केवल तब होता है जब आप स्ट्रिंग को बड़ी संख्या में तरीकों से विभाजित कर सकते हैं जो सभी मान्य अंग्रेजी शब्दों से शुरू होते हैं, और अभ्यास में होने की संभावना नहीं है। यदि स्ट्रिंग में कई विभाजन हैं, तो हम उन्हें ढूंढने में काफी समय व्यतीत कर सकते हैं। उदाहरण के लिए, "dotheredo" स्ट्रिंग पर विचार करें। हम इस कई मायनों विभाजित कर सकते हैं:

do the redo 
do the red o 
doth ere do 
dot here do 
dot he red o 
dot he redo 

इससे बचने के लिए आप उत्तर की संख्या आप रिपोर्ट, शायद दो या तीन की एक सीमा संस्थान कर सकते हैं।

चूंकि हम ट्राई से बाहर निकलने पर रिकर्सन काटते हैं, अगर हम कभी भी एक विभाजन की कोशिश करते हैं जो शेष स्ट्रिंग को वैध नहीं छोड़ता है, तो हम इसे बहुत जल्दी पहचान लेंगे।

आशा है कि इससे मदद मिलती है!

Answer 3

यह link इस समस्या का वर्णन एक संपूर्ण साक्षात्कार प्रश्न के रूप में करता है और इसे हल करने के लिए कई विधियां प्रदान करता है। अनिवार्य रूप से इसमें recursive backtracking शामिल है। इस स्तर पर यह ओ (2^एन) जटिलता उत्पन्न करेगा। ज्ञापन का उपयोग कर एक कुशल समाधान इस समस्या को ओ (एन^2) में ला सकता है।

Answer 4

आयात java.util। *;

class Position { 
    int indexTest,no; 
    Position(int indexTest,int no) 
    { 
     this.indexTest=indexTest; 
     this.no=no; 
    } } class RandomWordCombo { 
    static boolean isCombo(String[] dict,String test) 
    { 
     HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>(); 
     Stack<Position> pos=new Stack<Position>(); 
     for(String each:dict) 
     { 
      if(dic.containsKey(""+each.charAt(0))) 
      { 
       //System.out.println("=========it is here"); 
       ArrayList<String> temp=dic.get(""+each.charAt(0)); 
       temp.add(each); 
       dic.put(""+each.charAt(0),temp); 
      } 
      else 
      { 
       ArrayList<String> temp=new ArrayList<String>(); 
       temp.add(each); 
       dic.put(""+each.charAt(0),temp); 
      } 
     } 
     Iterator it = dic.entrySet().iterator(); 
    while (it.hasNext()) { 
     Map.Entry pair = (Map.Entry)it.next(); 
     System.out.println("key: "+pair.getKey()); 
     for(String str:(ArrayList<String>)pair.getValue()) 
     { 
      System.out.print(str); 
     } 
    } 
     pos.push(new Position(0,0)); 
     while(!pos.isEmpty()) 
     { 
      Position position=pos.pop(); 
      System.out.println("position index: "+position.indexTest+" no: "+position.no); 
      if(dic.containsKey(""+test.charAt(position.indexTest))) 
      { 
       ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest)); 
       if(strings.size()>1&&position.no<strings.size()-1) 
        pos.push(new Position(position.indexTest,position.no+1)); 
       String str=strings.get(position.no); 
       if(position.indexTest+str.length()==test.length()) 
        return true; 
       pos.push(new Position(position.indexTest+str.length(),0)); 
      } 
     } 
     return false; 
    } 
    public static void main(String[] st) 
    { 
     String[] dic={"world","hello","super","hell"}; 
     System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman")); 
    } } 

मैं इसी तरह की समस्या नहीं किया है। यदि दिया गया स्ट्रिंग शब्दकोष शब्दों का संयोजन है तो यह समाधान सत्य या गलत देता है। अंतरिक्ष-पृथक स्ट्रिंग प्राप्त करने के लिए इसे आसानी से परिवर्तित किया जा सकता है। इसकी औसत जटिलता ओ (एन) है, जहां n: दिए गए स्ट्रिंग में शब्दकोष शब्द नहीं।

Answer 5

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

यहां प्रस्तुत समाधान को सबसे अधिक संभावित विभाजन निर्धारित करने के लिए वर्तनी सुधार और बिग्राम विश्लेषण शामिल करने के लिए बढ़ाया जा सकता है।

def memo(func): 
    ''' 
    Applies simple memoization to a function 
    ''' 
    cache = {} 
    def closure(*args): 
     if args in cache: 
      v = cache[args] 
     else: 
      v = func(*args) 
      cache[args] = v 
     return v 
    return closure 


def segment(text, words): 
    ''' 
    Return the first match that is the segmentation of 'text' into words 
    ''' 
    @memo 
    def _segment(text): 
     if text in words: return text 
     for i in xrange(1, len(text)): 
      prefix, suffix = text[:i], text[i:] 
      segmented_suffix = _segment(suffix) 
      if prefix in words and segmented_suffix: 
       return '%s %s' % (prefix, segmented_suffix) 
     return None 
    return _segment(text) 


def segment_all(text, words): 
    ''' 
    Return a full list of matches that are the segmentation of 'text' into words 
    ''' 
    @memo 
    def _segment(text): 
     matches = [] 
     if text in words: 
      matches.append(text) 
     for i in xrange(1, len(text)): 
      prefix, suffix = text[:i], text[i:] 
      segmented_suffix_matches = _segment(suffix) 
      if prefix in words and len(segmented_suffix_matches): 
       for match in segmented_suffix_matches: 
        matches.append('%s %s' % (prefix, match)) 
     return matches 
    return _segment(text) 


if __name__ == "__main__":  
    string = 'cargocultscience' 
    words = set('car cargo go cult science'.split()) 
    print segment(string, words) 
    # >>> car go cult science 
    print segment_all(string, words) 
    # >>> ['car go cult science', 'cargo cult science']