एक लेमैमाइज़र बनाना: स्पीड ऑप्टिमाइज़ेशन

Question

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

उदाहरण (नोट: हालांकि उदाहरण अंग्रेजी में दिया जाता है मैं अंग्रेजी के लिए एक lemmatizer निर्माण नहीं कर रहा हूँ): के लिए

शब्द: मना

lemmaform: forbidd

प्रत्यय: ing

लेम्मा: ना करे

मेरे समाधान:

मैं (नेस्टेड) ​​dicts के लिए डेटा परिवर्तित कर दिया है:

suffixdict : {suffix1:[type1,type2, ... , type(n)], suffix2:[type1,type2, ... , 
type(n)]}  
lemmaformdict : {lemmaform:{type1:lemma}} 

1) सभी संभव प्रत्यय और शब्द प्रकार है कि वे से जुड़े होते हैं का पता लगाएं। यदि सबसे लंबा संभव प्रत्यय 3 वर्ण लंबा है, तो प्रोग्राम प्रत्यय में कुंजी के लिए 'ing', 'ng', 'n' से मिलान करने का प्रयास करता है। यदि कुंजी मौजूद है तो यह एक मान (वर्ड टाइप का एक सेट) देता है।

2) प्रत्येक मिलान प्रत्यय के लिए निर्देश से lemmaform खोज। यदि लेम्माफॉर्म मौजूद है तो यह शब्दप्रवाह देता है।

3) अंत में, प्रोग्राम चरण 1 में उत्पादित शब्दकोषों को छेड़छाड़ करने का प्रयास करता है) और यदि चौराहे है तो यह शब्द की नींबू लौटाता है।

मेरा प्रश्न: क्या गति की परिप्रेक्ष्य से मेरी समस्या का बेहतर समाधान हो सकता है? (शब्दकोश में लगातार शब्दों और लेमास रखने के विकल्प को रद्द करना) बहुत अधिक सहायता प्राप्त करने में सहायता करें।

Answer 1

यह परिमित राज्य ट्रांसड्यूसर के लिए एक अद्भुत अनुप्रयोग होगा। क्यूं कर? क्योंकि वे आपको स्ट्रिंग रीराइटिंग को कुशलता से करने की अनुमति देते हैं (इनपुट के आकार के लिए रैखिक समय में)। पर विचार करें निम्नलिखित रों [आइए] mple ट्रांसड्यूसर:

यह इनपुट के रूप में एक स्ट्रिंग और चेक लेता प्रारंभिक अवस्था से एक रास्ता वहां मौजूद (यहाँ, 0) एक अंतिम अवस्था (10, 12 के लिए और क्या 17, क्रमशः) इनपुट वर्णों के अनुक्रम दिया। यदि यह अंतिम स्थिति तक पहुंचता है, तो यह उपयुक्त आउटपुट उत्पन्न करता है, उदाहरण के लिए (मना कर दिया, आईएनजी) अगर इनपुट "मना कर रहा था"।

मुझे नहीं पता कि आपके पास परिमित राज्य ऑटोमाटा पर कोई पृष्ठभूमि है या नहीं। यदि नहीं, तो उन्हें आज़माएं - यह प्रयास के लायक होगा। :) Tries एक विशेष प्रकार का परिमित राज्य automaton (उपरोक्त नमूना ट्रांसड्यूसर एक त्रिभुज है), इसलिए वे एक अच्छी शुरुआत हो सकती हैं।

Answer 2

गैर-निर्धारितीtrie automaton पहचानने वाले प्रत्यय के पूर्ण सेट को कवर करने पर विचार करें, लेकिन पीछे की ओर शब्द का विश्लेषण करें। गैर-निर्धारक होने का मतलब है कि मशीन एक साथ कई राज्यों में हो सकती है, और पूरी तरह से मशीन एक स्वीकार्य स्थिति में है यदि इनमें से कोई भी राज्य स्वीकार कर रहा है।

प्रारंभिक स्थिति स्वीकार्य स्थिति होगी, इसलिए यह कोई प्रत्यय नहीं पहचान सकता (जैसा कि अंग्रेजी be में)। प्रारंभिक स्थिति से, संक्रमण (), ('e', 'z', 'i'), ('e', 'd', 'a') और ('e', 'v', 'o') उदाहरण के लिए सभी स्वीकार्य राज्यों पर पहुंचेंगे, और आपको एनएफए का उपयोग करते समय विवादित 'e' एस के बारे में चिंता करने की आवश्यकता नहीं है।

प्रारंभिक स्थिति से प्रत्येक शब्द के "अक्षर" पीछे की ओर खिलाए जाते हैं। प्रत्येक बार जब मशीन स्वीकार्य स्थिति में उतरती है, तो शब्द का शेष भाग आपके lemmaformdict में देखा जाता है और सभी परिणाम रखे जाते हैं। फिर प्रसंस्करण तब तक जारी रहता है जब तक कि मशीन की स्थिति शून्य न हो (न केवल स्वीकार न हो)।

उस बिंदु पर लेम्मा के कुल विकल्प इस तरह से संकेत दिए गए शब्द की संभावित व्याख्याओं को संदर्भित करते हैं (और यह हमेशा एक छोटी संख्या होनी चाहिए)।

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