मार्कोव चेन टेक्स्ट जनरेशन

Question

हमें केवल मेरे डेटा संरचना वर्ग में एक नई परियोजना सौंपा गया था - मार्कोव चेन के साथ पाठ उत्पन्न करना।

अवलोकन

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

यह बिल्ली है और दो कुत्ते हैं।

Initial seed: "Th" 
Possible next letters -- i, e, e 
Therefore, probability of choosing i is 1/3, e is 2/3. 

Now, say we choose i. We add "i" to the output string. Then our seed becomes 
hi and the process continues. 

मेरे समाधान

मैं 3 वर्गों, नोड, ConcreteTrie, और ड्राइवर

बेशक

है, ConcreteTrie वर्ग पारंपरिक अर्थों की एक Trie नहीं है। यह ऐसे काम करता है:

कश्मीर = 2 के साथ वाक्य को देखते हुए:

यह बिल्ली है और वहाँ दो कुत्ते हैं।

मैं नोड्स थ, हाय, है, ... + ..., जीएस, एस उत्पन्न करता हूं। इनमें से प्रत्येक नोड में बच्चे हैं जो उनके अनुसरण वाले पत्र हैं। उदाहरण के लिए, नोड थ में बच्चों और मैं बच्चे होंगे। मैं उन नोड्स में से प्रत्येक में मायने रखता हूं ताकि मैं बाद में अगले पत्र को चुनने के लिए संभावनाएं उत्पन्न कर सकूं।

मेरा प्रश्न:

सबसे पहले, क्या इस परियोजना को पूरा करने लिए सबसे कारगर तरीका है? मेरा समाधान बहुत तेज़ प्रतीत होता है, लेकिन मैं वास्तव में अपने प्रोफेसर के मोजे बंद करना चाहता हूं। (मेरी आखिरी परियोजना पर संपादन दूरी की समस्या का एक बदलाव, मैंने ए *, एक जेनेटिक एल्गोरिदम, एक बीएफएस, और सिम्युलेटेड एनीलिंग किया - और मुझे पता है कि समस्या एनपी-हार्ड है)

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

Answer 1

कक्षा (आपका दूसरा प्रश्न) में जो भी शामिल है, उसके साथ इस असाइनमेंट की प्रासंगिकता पर। 'डेटा संरचनाओं का विचार' वर्ग सीएस में अक्सर सामना की जाने वाली कई संरचनाओं में छात्रों को बेनकाब करना है: सूचियों, ढेर, कतार, हैंश, विभिन्न प्रकार के पेड़, बड़े पैमाने पर ग्राफ, विभिन्न पंथों और लोभ आदि के matrices, आदि और उनके सामान्य कार्यान्वयन, उनकी ताकत और कमजोरियों और आम तौर पर उनके आवेदन के विभिन्न क्षेत्रों में कुछ अंतर्दृष्टि प्रदान करने के लिए।
चूंकि इनमें से किसी भी गेम/पहेली/समस्या को इन संरचनाओं के कुछ सेट में मैप किया जा सकता है, ऐसे विषयों की कोई कमी नहीं है जिन पर व्याख्यान और असाइनमेंट आधार हैं। आपकी कक्षा दिलचस्प प्रतीत होती है क्योंकि इन संरचनाओं पर कुछ ध्यान केंद्रित करते समय, आपको वास्तविक अनुप्रयोगों को खोजने का मौका भी दिया जाता है।
उदाहरण के लिए एक पतली छिपी हुई फैशन में "बिल्ली और दो कुत्ते" चीज भाषाविदों पर लागू सांख्यिकीय मॉडल का परिचय है।आपकी जिज्ञासा और प्रेरणा ने आपको मार्कोव मॉडल के साथ संबंध बनाने के लिए प्रेरित किया और यह एक अच्छी बात है, क्योंकि संभावना है कि आप स्नातकोत्तर से कुछ और बार "मार्कोव" से मिलेंगे ;-) और निश्चित रूप से सीएस या संबंधित डोमेन में पेशेवर जीवन में। तो, हाँ! यह लग सकता है कि आपके आस-पास कई आवेदन आदि butterflying रहे हैं, लेकिन इतने लंबे समय के रूप में आप क्या संरचनाओं और एल्गोरिदम विशेष परिस्थितियों में चयन करने के लिए का एहसास दिलाने में, आप अपना समय बर्बाद कर नहीं कर रहे हैं!

अब, काम
trie के लिए संभव दृष्टिकोण पर कुछ संकेत इस प्रकार की समस्या के लिए एक प्राकृतिक समर्थन की तरह लगता है। हो सकता है कि आप खुद से पूछ सकें कि यह दृष्टिकोण कैसे स्केल करेगा, अगर आपको इस छोटी वाक्य की बजाय पूरी किताब कहनी पड़ेगी। यह ज्यादातर रैखिक रूप से लगता है, हालांकि यह इस बात पर निर्भर करता है कि त्रिभुज में तीन हॉप (इस दूसरे क्रम के लिए मार्कोव चेन के लिए) प्रत्येक विकल्प कैसे है: जैसे विकल्पों में वृद्धि की संख्या बढ़ती है, पथ चुनना कम कुशल हो सकता है।
इंडेक्स के निर्माण के लिए एक संभावित वैकल्पिक भंडारण स्टोकैटिस्क मैट्रिक्स (वास्तव में आंकड़े एकत्र करने की प्रक्रिया के दौरान केवल 'सादा' अगर केवल मैट्रिक्स स्पैस होता है, तो अंत में स्टोकैस्टिक बन जाता है जब आप प्रत्येक पंक्ति को सामान्य करते हैं-कॉलम-निर्भर करता है आप इसे सेट अप करते हैं) एक (100%) तक की राशि तक। ऐसा मैट्रिक्स मोटे तौर पर 729 x 28 होगा, और एक ही ऑपरेशन में, दो-अक्षर टुपल और उसके संबंधित निम्न पत्र के अनुक्रमण को अनुक्रमित करने की अनुमति देगा। (मुझे "स्टार्ट" और "स्टॉप" संकेतों के विवरण के लिए 28 मिल गया है, विवरण ...)
इस अधिक कुशल अनुक्रमण की लागत अतिरिक्त स्थान का उपयोग है। अंतरिक्ष के लिहाज से trie बहुत ही कुशल, केवल प्रभावी रूप से अस्तित्व में पत्र तीन के संयोजन भंडारण, मैट्रिक्स हालांकि कुछ जगह (आप, अंत में यह बहुत कम आबादी वाले हो जाएगा में शर्त अनुक्रमण कि बहुत अधिक पाठ के बाद भी बरबाद करती है " कुत्ते/बिल्ली "वाक्य।)
यह आकार बनाम सीपीयू समझौता बहुत आम है, हालांकि कुछ एल्गोरिदम/संरचनाएं दोनों मायने में दूसरों की तुलना में बेहतर होती हैं ... इसके अलावा मैट्रिक्स दृष्टिकोण अच्छी तरह से स्केल नहीं करेगा, आकार-वार , अगर समस्या को पिछले तीन वर्णों से अक्षरों की पसंद के आधार पर बदल दिया गया था।
कोई भी कम नहीं, शायद वैकल्पिक कार्यान्वयन के रूप में मैट्रिक्स को देखें। यह इस वर्ग की भावना में बहुत अधिक है विभिन्न संरचनाओं को आजमाएं और देखें कि वे अन्य लोगों की तुलना में बेहतर क्यों हैं (किसी विशिष्ट कार्य के संदर्भ में)।
अक्षरों के जोड़ों (या तीन गुना) की संभावनाओं के आधार पर tag cloud बनाने के लिए आप एक छोटी सी यात्रा यात्रा कर सकते हैं: त्रिभुज और मैट्रिक्स दोनों के लिए आवश्यक सभी डेटा शामिल हैं; इसके सभी दिलचस्प गुणों के साथ मैट्रिक्स, इसके लिए अधिक उपयुक्त हो सकता है।
मज़े करो!

Answer 2

आप पात्रों के साथ दृष्टिकोण बाइग्राम का उपयोग कर, लेकिन आमतौर पर यह शब्द के लिए आवेदन किया है, क्योंकि उत्पादन और अधिक सार्थक अगर हम आपके मामले में के रूप में सिर्फ साधारण जनरेटर का उपयोग हो जाएगा)।

1) मेरे दृष्टिकोण से आप सही कर रहे हैं। लेकिन हो सकता है कि आपको अगले नोड के चयन को थोड़ा यादृच्छिक बनाना चाहिए? जैसे 5 उच्चतम से यादृच्छिक नोड का चयन करें। मेरा मतलब है कि यदि आप हमेशा उच्चतम संभावना वाले नोड का चयन करते हैं तो आपकी आउटपुट स्ट्रिंग बहुत समान होगी।

2) मैं अपने विश्वविद्यालय में बिल्कुल वैसा ही होमवर्क किया है। मुझे लगता है कि बिंदु छात्रों को पता चलता है कि मार्कोव चेन शक्तिशाली लेकिन जनरेटर के आवेदन डोमेन उत्पादन के व्यापक अध्ययन के बिना हास्यास्पद