पाठ विभाजन एल्गोरिथ्म

नमस्ते

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

इस लेख को इस्तेमाल किए गए प्रत्येक एल्गोरिदम के फायदे और नुकसान के विश्लेषण के साथ समस्या को हल करने का एक निश्चित कालक्रम माना जा सकता है। इसलिए, यदि आप इस विषय में रुचि रखते हैं, तो मैं एक बिल्ली के लिए पूछता हूं।

यह ध्यान देने योग्य है कि रिक्त स्थान के बिना बड़े पाठ को तोड़ने का कार्य बहुत आम है। यह जर्मन के "लंबे शब्दों" में शब्दों की परिभाषा है, जो, संक्षेप में, कई का संयोजन है ( geschwindigkeitsbegrenzung - गति सीमा ), चीनी लेखन में शब्दों की परिभाषा, जो शायद ही कभी एक स्थान का उपयोग करते हैं ( 人 人 心爱 words 宠物 - शहर के निवासियों का एक पसंदीदा पालतू ) इतने पर। यदि चीनी के साथ दूसरे मामले में, सरलतम एल्गोरिथ्म प्रति शब्द एक वर्ण मानता है और काफी स्वीकार्य काम करता है, तो जर्मन के साथ सब कुछ बहुत अधिक जटिल है।

एल्गोरिथम 1. न्यूनतम मिलान

हम लाइन के माध्यम से जाते हैं और पहले शब्द से मेल खाते हैं। हम इस शब्द को सहेजते हैं और बाकी पंक्ति के लिए प्रक्रिया दोहराते हैं। यदि अंतिम पंक्ति में एक भी शब्द मेल नहीं खाता है, तो हम मानते हैं कि विभाजन नहीं मिला है।
एल्गोरिथ्म बहुत तेज़ है (बस हमें जो चाहिए), लेकिन बहुत बेवकूफ।

उदाहरण: niceday => अच्छा दिन ।
लेकिन, निकवर्गर विभाजन के लिए नहीं मिलेगा, क्योंकि पाया शब्द अच्छा होने के बाद, एल्गोरिथ्म हमें निर्धारित करेगा, फिर लेख ए , फिर और शब्द आर हमारे शब्दकोश में नहीं है।
हम्म। मैच को रोकने के बजाय, पहले शब्द के बजाय, जो अधिकतम लंबाई के साथ लेता है?

एल्गोरिथम 2. अधिकतम मिलान या लालची

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

उदाहरण: अच्छा मौसम => अच्छा मौसम
लेकिन, वर्करास के लिए, विभाजन फिर से नहीं मिलेगा। पहला शब्द जो हमारे एल्गोरिथ्म से मेल खाएगा, काम कर रहा होगा, काम नहीं , और जो घास शब्द में पहले अक्षर को भी अवशोषित करेगा।
शायद आपको दोनों एल्गोरिदम को किसी तरह से संयोजित करने की आवश्यकता है? लेकिन, फिर स्ट्रिंग के बारे में क्या niceweatherwhenworkingrass ? सामान्य तौर पर, वे ब्रूट बल के लिए आए थे।

एल्गोरिथम 3. ब्रूटफोर्स

हम एक नियमित पुनरावर्ती फ़ंक्शन द्वारा स्ट्रिंग को शब्दों में विभाजित करने के सभी संभव संस्करण उत्पन्न करते हैं। ऐसे विकल्प 2 ^ (N-1) होंगे, जहां N स्ट्रिंग का आकार है। इसके बाद, हम उन विकल्पों को खोजते हैं, जिनमें डिक्शनरी से सबस्ट्रिंग शामिल नहीं थे। और परिणामस्वरूप विकल्प सही होगा। एल्गोरिथ्म की मुख्य समस्या गति है।
इसे रोको! और सब कुछ क्यों उत्पन्न होता है, और फिर इसे फ़िल्टर करें यदि आप तुरंत अपनी आवश्यकता के अनुसार उत्पन्न कर सकते हैं।

एल्गोरिथम 4. चतुर जानवर

हम अपने पुनरावर्ती कार्य को संशोधित करते हैं ताकि पुनरावर्ती कॉल तब होता है जब हमने पहले ही शब्दकोश से एक शब्द का मिलान किया हो। इस मामले में, वांछित विभाजन तुरंत उत्पन्न होता है। एल्गोरिथ्म बहुत तेज है, वांछित परिणाम देता है, और सामान्य तौर पर मैंने सोचा था कि समस्या हल हो गई थी।
दुर्भाग्य से, मैंने अस्पष्टता की दृष्टि खो दी है। तथ्य यह है कि लाइन विभाजन अद्वितीय नहीं है और ऐसे समय होते हैं जब दर्जनों समकक्ष विभाजन होते हैं।

उदाहरण: expertsexchange => ( विशेषज्ञ लिंग परिवर्तन , विशेषज्ञ विनिमय )

एक नया सबटैब सामने आया है: "सही" विभाजन कैसे चुनें?
मैं पहले विकल्पों के माध्यम से चला गया, यादृच्छिक, अंतिम, एक जिसमें अधिक शब्द हैं, एक जिसमें कम शब्द हैं और परिणाम थे, इसे हल्के ढंग से रखने के लिए, बहुत नहीं। कुछ प्रकार के स्मार्ट एल्गोरिथ्म की आवश्यकता थी। मैं समझ सकता हूं
बौना पत्ताकार सबसे अधिक संभावना है "बौनों से एक बौना अयस्क चुराता है" और "एक बौना अयस्क या एक कोर चोरी नहीं करता है", जिसका अर्थ है कि मशीन को समझना चाहिए। यहां मशीन लर्निंग एल्गोरिदम बचाव में आए।

एल्गोरिथ्म 5. स्पष्टता के साथ चतुर जानवर (संकल्प मॉडल)

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

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

एल्गोरिथ्म 6. स्पष्टता के साथ चतुर जानवर (संकल्प मॉडल)

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

निष्कर्ष

एल्गोरिदम अच्छे परिणाम दिखाता है। कमजोर बिंदु शब्दकोश है। चूंकि ट्विटर पर डेटा ज्यादातर अनौपचारिक है, लोगों के नाम, भौगोलिक नाम आदि, शब्दकोश कई उपयुक्त उम्मीदवारों को समाप्त करता है। इसलिए, एल्गोरिथ्म के विकास की दिशाओं में से एक शब्दकोश की अस्वीकृति है। इसके बजाय, आप शब्द का उपयोग ट्रेनेट से कर सकते हैं। दूसरा कमजोर बिंदु ट्रेन सेट है। चूंकि सब कुछ एमएल एल्गोरिदम में इस पर निर्भर करता है, इसलिए आपके पास यथासंभव प्रासंगिक डेटा होना चाहिए। यहां, एक विकल्प के रूप में, आप उसी ट्विटर से प्राप्त डेटा से ट्रेन-सेट का उपयोग कर सकते हैं।

संदर्भ

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