🚣🏾 🗨️ 🍥 pymorphy2 🗡️ 👩🏾‍🏭 🤹

2009 में वापस, पर्मॉर्फ़ के बारे में " बज़िंग बटक्स .. " के बारे में हब पर एक लेख पहले से ही था - पायथन में रूसी भाषा के लिए एक रूपात्मक विश्लेषक (एक उल्लंघन जो शब्दों को संक्रमित कर सकता है, भाषण, मामले, आदि के बारे में जानकारी संवाद कर सकता है)।

2012 में, मैंने धीरे-धीरे pymorphy2 ( github , bitbucket ) करना शुरू किया - मुझे लगता है कि इस लाइब्रेरी को यहां पेश करने का समय आ गया है: pymorphy2 pymorphy की तुलना में सैकड़ों गुना तेजी से काम कर सकता है (बिना / C ++ एक्सटेंशन का उपयोग किए) और अभी भी कम मेमोरी की आवश्यकता है; बेहतर शब्दकोश, बेहतर पार्सिंग गुणवत्ता, पत्र ई के लिए बेहतर समर्थन, आसान स्थापना और अधिक "ईमानदार" एपीआई हैं। नकारात्मक से - सभी pymorphy फीचर्स अब pymorphy2 में लागू नहीं किए गए हैं।

यह आलेख इस बारे में है कि pymorphy2 कैसे बनाया गया था (कभी-कभी उबाऊ तकनीकी विवरण के साथ), और ऐसा करने में मैंने कितना बकवास किया; यदि आप सब कुछ आज़माना चाहते हैं, तो आप दस्तावेज़ पढ़ सकते हैं।

Pymorphy के साथ क्या समस्याएं थीं:

बल्कि धीमी गति (डिफ़ॉल्ट रूप से स्थापित होने पर कुछ सौ शब्द / सेकंड);
aot.ru से शब्दकोशों पर निर्भरता, जो स्पष्ट नहीं है कि कैसे फिर से भरना / तय करना है;
एपीआई के साथ कुछ समस्याएं - उदाहरण के लिए, झुकाव के लिए एपीआई के अनुसार, ऐसा लग सकता है कि पुस्तकालय खुद विश्लेषण की अस्पष्टता को हटा देता है, हालांकि यह ऐसा नहीं है;
पत्र all विधि द्वारा समर्थित था "हर जगह ई के साथ सभी जगह";
बल्कि जटिल स्थापना - आपको शब्दकोश, कुछ अलग प्रारूप आदि डाउनलोड करने की आवश्यकता है। (यहां तक कि जापानी में किसी ने वीडियो सबक की एक श्रृंखला बनाई);
पायथन 3.x केवल बिटबकेट के साथ संस्करण में समर्थित था, जिसे कभी जारी नहीं किया गया था;
शिशु को राजी करना असंभव है: क्रिया को शिशु के रूप में रखा जा सकता है, लेकिन इसके विपरीत - अब नहीं;
हाइफ़न किए गए शब्द हमेशा सही ढंग से झुके नहीं होते हैं;
कुआँ, आदि।

इससे पहले कि मुझे पाइमॉर्फी होती, मैंने पायथन में कभी नहीं लिखा, न ही मैंने प्राकृतिक भाषा प्रसंस्करण के साथ काम किया (पाइमोर्फी दोनों को समझने का एक तरीका था) - यह बिल्कुल स्पष्ट है कि बहुत कुछ बेहतर किया जा सकता है।

लेकिन pymorphy1 का बहुत कुछ सही किया गया था। उदाहरण के लिए, रूसी में स्थापना और विशेष निर्भरता के बिना स्थापना (सबसे महत्वपूर्ण बात, एक संकलक की आवश्यकता के बिना); परीक्षणों के साथ कम या ज्यादा सामान्य विकास प्रक्रिया; विश्लेषण और भविष्यवाणी की गुणवत्ता काफी उच्च थी। Django के साथ एकीकरण भी एक अच्छा "विपणन" कदम था - हालांकि, इसके साथ कुछ वैचारिक समस्याएं थीं (आप विश्लेषण की अस्पष्टता को हल किए बिना सीधे टेम्पलेट में एक शब्द को सही ढंग से घोषित नहीं कर सकते हैं - और यह एपीआई में प्रदान नहीं किया गया था)।

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

लंबे समय तक मैं पिछड़ी अनुकूलता को तोड़ना नहीं चाहता था और मेरे पास जो कुछ भी है उसे विकसित करने की कोशिश की (हालांकि बरियार , उदाहरण के लिए, यहां तक कि एक कांटा भी था, जिसने पिछड़ी संगतता को तोड़ दिया, लेकिन तेजी से काम किया)। Pymorphy2 लिखने के लिए निर्णायक प्रोत्साहन OpenCorpora प्रोजेक्ट था - वहां के लोग, अन्य चीजों के अलावा (और "सब कुछ") बहुत हैं, aot.ru से शब्दकोश लिया, इसकी संरचना को पूरी तरह से बदल दिया और फिर से भरना और अन्य सुधार शुरू किए।

तो, OpenCorpora से एक शब्दकोश का उपयोग करने के लिए विचार आया।

Pymorphy ने aot.ru से ऐसे शब्दकोशों का उपयोग किया, जिन्हें शायद ही कभी संसाधित किया गया था (उन्हें साइक्लाइट प्रारूप में अनुवादित किया गया था, लेकिन संक्षेप में संरचना समान थी)। अलग-अलग, शब्दों की "नींव", अलग से "उपसर्ग", अलग-अलग "अंत" संग्रहीत किए गए थे, और अलग-अलग - इन भागों से शब्दों के निर्माण के नियम। यह तरीका अच्छा था क्योंकि इसके आधार पर बहुत अधिक प्रयास और शोध के बिना "सप्ताहांत" के एक जोड़े में रूपात्मक विश्लेषक को लागू करना संभव था।

लेकिन यह सब - कई रैपरों के माध्यम से डेटा तक पहुंच और (विशेषकर) अजगर कोड के साथ भागों से शब्दों को इकट्ठा करना - काम की गति को नकारात्मक रूप से प्रभावित करता है; मैं किसी भी तरह से इस दृष्टिकोण के साथ किसी भी गति में सुधार नहीं कर सकता था, समाधान जटिल थे और वास्तव में मदद नहीं करते थे (ध्यान दें: विकल्प "जैसा भी हो सब कुछ फिर से लिखना, लेकिन सी ++ में काम करता है " जल्दी से काम करता है, लेकिन pororphy2 की तुलना में अधिक मेमोरी की आवश्यकता होती है) ।

संक्षेप में, pymorphy2 में मैं कुछ अन्य दृष्टिकोणों की कोशिश करना चाहता था, क्योंकि शब्दकोश नए हैं, और अभी भी बहुत सारे शब्दकोश फिर से लिखते हैं। उसी समय, मैं चाहता था कि pymorphy2 एक अजगर पुस्तकालय बना रहे, और न केवल C / C ++ कोड के ढेर के लिए एक आवरण - मैं चाहता था कि पार्स तर्क तर्क अजगर पर बने रहे। क्या करना है इसके लिए कई विकल्प थे।

स्वचालित मशीनें

दिमाग में आने वाला पहला विकल्प परिमित ऑटोमेटा के संदर्भ में समस्या का सुधार करना था। lightcaster ने यहां अच्छी तरह से दृष्टिकोण का वर्णन किया: habrahabr.ru/post/109736 । दृष्टिकोण सुंदर है, अर्थात् है।

मुझे यहाँ क्या उलझन है:

a) OpenFST C ++ लाइब्रेरी का उपयोग लेख में किया गया था (यह परिमित राज्य मशीनों को लागू करने का सबसे लोकप्रिय तरीका लगता है), लेकिन उपयोगकर्ताओं को इसे मैन्युअल रूप से स्थापित करने के लिए मजबूर करना एक विकल्प नहीं है;
ख) यहां तक कि सी ++ लाइब्रेरी का उपयोग करते हुए, परिणाम, लेख द्वारा निर्णय लेने, बल्कि मामूली थे (2 हजार शब्द / सेकंड बनाम 100+ हजार शब्द / सेकंड सिस्टम या लेमेटाइज़र के लिए); यह स्पष्ट है कि इस आंकड़े में काफी सुधार हो सकता है (और लाइटकास्टर कहता है कि यह कुछ भी अनुकूलित नहीं है) - लेकिन फिर भी;
ग) यह उन दृष्टिकोणों में से एक है जो (मेरी राय में) प्रवेश सीमा को बढ़ाता है - मुझे लगता है कि यह अधिक होने की संभावना है।

अंत में यह पता चला कि मुझे इसकी आवश्यकता होगी: कोड को ऑप्टिमाइज़ करने का तरीका पता करें और यह C ++ लाइब्रेरी के साथ भी धीरे-धीरे क्यों निकले; OpenFST के लिए एक सरल इंस्टॉलेशन रैपर लिखें (या किसी अन्य FST कार्यान्वयन का उपयोग करें - उदाहरण के लिए, अपना खुद का बनाएं) + Python में OpenFST (या सिर्फ FST कार्यान्वयन) के एक छोटे से हिस्से का कार्यान्वयन करें (ताकि एक संकलक के बिना पायरोमी का उपयोग किया जा सके), ठीक है, सभी एल्गोरिदम तैयार करें परिमित राज्य मशीनों के संदर्भ में।

कुछ साल पहले, lightcaster ने मुझे परिमित राज्य मशीनों पर pymorphy के कार्यान्वयन का एक और स्केच भेजा था (सी एक्सटेंशन के बिना पाइथनियम, मुझे इसमें कुछ भी समझ में नहीं आया था :) - परिणामस्वरूप स्केच ने लगभग 2 हज़ार शब्दों / सेकंड की गति से काम किया और लगभग 300 एमबी मेमोरी की आवश्यकता थी। यह सब, एक तरफ, बुरा नहीं है, लेकिन दूसरे पर, यह वैसे भी बहुत प्रेरणादायक नहीं था; यह स्पष्ट था कि यदि इस विधि द्वारा "माथे पर" हल किया जाता है, तो यह बहुत तेज़ी से काम नहीं करेगा, और आपको उस व्यक्ति की तुलना में बहुत बेहतर लिखना होगा जो विषय को समझता है। संक्षेप में, यह बहुत काम और एक अनुचित परिणाम (+ अन्य वास्तुशिल्प विचार, लेख के अंत के करीब) की तरह लग रहा था। शायद, यह गलत लग रहा था, कौन जानता है - मैंने इसे कोशिश नहीं की है, केवल बहाना है।

इस तरह (विशेष रूप से ऑटोमेटा के बारे में समस्या के रूप में समस्या पर विचार करने के लिए) मैं नहीं गया। हालांकि - यह कैसे कहना है, यह सब देखने के बिंदु पर निर्भर करता है :)

नकल प्रणाली

दूसरा विकल्प व्यवस्था पर प्रकाशन में वर्णित लगभग लागू करना था। मुझे नहीं पता कि क्या mystem अब समान एल्गोरिदम का उपयोग करता है, लेकिन लेख में वर्णित विधि काफी उचित है। वे mystem के बारे में बहुत सारी अच्छी चीजें लिखते हैं, इसलिए पहले मैंने pymorphy2 को लागू करने की कोशिश की जो प्रकाशन में वर्णित है।

विधि का सार (जैसा कि मैं इसे समझता हूं)

क) हमारे पास रूसी भाषा के सभी शब्दों की एक सूची है, और प्रत्येक शब्द के लिए "घोषणा मॉडल" ("प्रतिमान") का संकेत दिया गया है - कुछ प्रकार का टेम्पलेट जिसके द्वारा इस शब्द के अन्य रूपों का निर्माण किया जा सकता है। ठीक है, उदाहरण के लिए, कई संज्ञाओं के लिए, आप नाम के मामले के बहुवचन को प्राप्त करने के लिए पत्र "और" अंत में असाइन कर सकते हैं, और "हूँ" - नाममात्र। रूसी आकारिकी के अधिकांश अहसास इसी सिद्धांत पर बनाए गए हैं।

b) शब्दों के सभी उल्टे "अंत" के लिए एक उपसर्ग वृक्ष (trie) बनाया गया है। "समाप्ति" को लगभग aot.ru के समान ही लिया जाता है - दाईं ओर शब्द का हिस्सा, जो कि गिरावट के साथ बदलता है। उदाहरण के लिए, शब्द "हैम्स्टर" में, यह "अमी" हो सकता है - ट्राइ में "इमा" जोड़ें।

ग) एक उपसर्ग वृक्ष (त्रिक) शब्द के सभी उल्टे "नींव" के लिए बनाया गया है। उदाहरण के लिए, "हम्सटर" शब्द के लिए यह "कामोख" है। इसके अलावा, इस ढांचे के लिए घोषणा मॉडल (प्रतिमान) के संभावित सूचकांक (विभाजक के माध्यम से) "नींव" के अंत तक असाइन किए जाते हैं। उदाहरण के लिए, यदि "हम्सटर" को प्रतिमान A और B के अनुसार झुकाया जा सकता है, और विभाजक $ है, तो त्रिकोणीय में हम "kamokh $ A" और "kyamokh $ B" मान जोड़ देंगे। Mystem पर लेख में, मूल बातें के लिए एक पेड़ का उपयोग नहीं किया गया था, लेकिन कई (मेरी राय एक अनुकूलन उपाय के रूप में है) - लेकिन यह एल्गोरिथ्म को दृढ़ता से प्रभावित नहीं करता है, हम मानते हैं कि पेड़ यहां एक है।

घ) शब्द का वास्तविक विश्लेषण: हम अंत से शब्द का अनुसरण करते हैं, पहले त्रिक से सभी संभव "अंत" इकट्ठा करते हैं (उपसर्ग वृक्ष में, यह ऑपरेशन त्रि में शब्दों की संख्या के ओ (1) और लंबाई के ओ (एन) के लिए किया जाता है)। "हम्सटर" के लिए मान लीजिए कि हम पा सकते हैं कि ऐसे शब्द हैं जिनमें विभक्ति अंत "" (खाली), "और", "अमी" या "कामी" है। ये "अंत" "मूल बातें" के अनुरूप हैं: हैम्स्टर, हैम्स्टर, हम्सटर और हम्सटर।

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

च) यदि आपको कुछ भी नहीं मिला, तो इसका मतलब है कि सबसे कम आधार वाला कोई शब्द नहीं है - आप एक लंबे आधार पर जा सकते हैं; आप इसी तरह के मूल सिद्धांतों की भी जांच कर सकते हैं (कागज से मुझे समझ में नहीं आया कि वास्तव में क्या किया जा रहा है, लेकिन यह वह बिंदु नहीं है - उदाहरण के लिए, आप अगली लंबी नींव की कोशिश कर सकते हैं; सभी संभावित मूल सिद्धांतों का परीक्षण हो जाने के बाद, समान शब्द पहले से ही काम करना शुरू कर सकते हैं) ।

पेपर में विभिन्न अनुमानों का भी वर्णन किया गया है जो शब्दकोश के आकार को कम कर सकते हैं और अप्रत्याशित भविष्यवाणियों को हटा सकते हैं।

मैं कुछ गलत समझ सकता था या गलत समझ सकता था; यदि यह व्यवसाय के लिए आवश्यक है, तो मूल लेख को पढ़ना बेहतर है, निश्चित रूप से।

Trie

विधि उपसर्ग पेड़ (ट्राई) का उपयोग करती है - विधि को लागू करने के लिए, आपको पायथन के लिए एक त्रि कार्यान्वयन की आवश्यकता है। मैं अजगर के कार्यान्वयन का उपयोग नहीं करना चाहता था (मैं मेमोरी से गति और लोलुपता के लिए डरता था), और मैंने, आश्चर्यजनक रूप से, ट्राइ के कुछ अच्छे सी / सी ++ कार्यान्वयन के लिए किसी भी तैयार किए गए अजगर रैपर को नहीं पाया।

डेटा संरचनाओं के अपने C / C ++ कार्यान्वयन को लिखना दुर्लभ है: C / C ++ में पहले से ही बहुत सारी चीजें हैं, और कई पुस्तकालय अत्याधुनिक एल्गोरिदम को लागू करते हैं। क्यों? तो एक आदमी एक चालाक डेटा संरचना के साथ आया था, एक वैज्ञानिक पत्रिका में इसके बारे में एक लेख लिखा था। ताकि परिणाम दोहराया जा सके, लेखक अक्सर कार्यान्वयन को पूरा करता है, और सबसे अधिक बार - यह सी या सी ++ में होता है। यदि वह इसे अपलोड नहीं करता है, तो कोई अन्य व्यक्ति पेपर पढ़ता है और कार्यान्वयन लिखता है - सी / सी ++ में भी (ठीक है, कभी-कभी वे जावा में ऐसी चीजें लिखते हैं)।

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

इस दृष्टिकोण के 2 बड़े पैमाने हैं:

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

सबसे पहले मुझे लिबडाट्री लाइब्रेरी पसंद आई , मैंने यहां इसके लिए रैपर के बारे में लिखा : habrahabr.ru/post/9797963 । लाइब्रेरी में कुछ चीजें तय की जानी थीं (यह आमतौर पर इस तरह से निकलती है - मैंने सी में एक कार्यशील कार्यान्वयन लिखा था, लाइब्रेरी के लेखक ने सब कुछ फेंक दिया और एक ही चीज़ के लिए अधिक मुहावरेदार सी कोड लिखा - और क्या यह सही है, क्योंकि सी कोड वास्तव में उसके लिए बेहतर था :); नतीजतन, हमें पूरी तरह से उपयोगी आवरण मिला।

डेट्री और "सब कुछ सिस्टम से चोरी!" दृष्टिकोण के साथ, यह 20-60 हजार शब्द / सेकंड निकला (एक भविष्यवक्ता के साथ और एक अजगर बांधने की न्यूनतम के साथ; ऐसा क्यों फैलता है - मुझे पहले से ही याद नहीं है, मौसम, शायद), और इसने लगभग 30 एमबी मेमोरी पर कब्जा कर लिया।

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

इसके अलावा, एक तरफ 30 एमबी अच्छा है, और दूसरी तरफ aot.ru कम है (हम लिखते हैं कि 9 एमबी, फिर 19 एमबी - हम मानते हैं कि 9, मेरे हाथों की जांच नहीं हुई)। मेमोरी की खपत महत्वपूर्ण है क्योंकि pymorphy का उपयोग एक तोप से गौरैयों को गोली मारने के लिए किया जाता है (किसी साइट पर शब्दों का तनाव), और इसके लिए इसे हर वेब प्रक्रिया में लोड करने की आवश्यकता होती है। ठीक है, या यदि आप डाउनलोड नहीं करते हैं (इस तथ्य के कारण कि स्मृति एक दया है), तो एक अलग सेवा के साथ एक बगीचे की बाड़ लगाना (कुछ zeromq पर, या http के माध्यम से संचार करना) - जिसे आप भी नहीं चाहते हैं।

डेटरी कार्यान्वयन बिंदुओं पर "भोला" नहीं है, एक डेटरी को नियमित उपसर्ग पेड़ की तुलना में 2 गुना कम मेमोरी की आवश्यकता होती है (इसलिए 30Mb अभी भी अच्छा है)।

इसके अलावा, किसी तरह यह एल्गोरिदम के दृष्टिकोण से, जटिल हो गया; यह स्पष्ट था कि यदि आप आगे (भविष्यवक्ता, उत्तराधिकार) को समाप्त करते हैं, तो सब कुछ बहुत धीमा और अधिक जटिल हो जाएगा। गड़बड़।

मारिसा-trie

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

जब मैंने मारिसा-ट्राई का परीक्षण करना शुरू किया, तो मेरे माथे पर मेरी नज़र सबसे पहले चढ़ गई। देखें:

यदि आप अजगर शब्दकोश में सभी 3 मिलियन रूसी शब्दों को लेते हैं और लोड करते हैं, तो यह लगभग 600 एमबी रैम (सूची में - लगभग 300 एमबी) ले जाएगा;
यदि आप एक डेटा को एक डेट्री में लोड करते हैं, तो यह 70 एमबी रैम लेगा - जो पहले से ही बहुत अच्छा है;
और यदि आप उसी डेटा को MARISA-Trie पर अपलोड करते हैं, तो यह 10 गुना कम - 7 एमबी मेमोरी लेगा।

वह कैसे है? तथ्य यह है कि MARISA-Trie वास्तव में Trie नहीं है :) यह क्या है - मैंने इसे सामान्य तरीके से समझ नहीं पाया; स्रोत में "मांस" वाले फ़ोल्डर को ग्रिमोयर कहा जाता है; एल्गोरिथ्म का वर्णन विशेष रूप से जापानी में है।

जाहिर है, मारिसा-ट्राई पेट्रीसिया-ट्राई ( विकी ) का एक "सफल" कार्यान्वयन है, जिसमें न केवल प्रत्येक नोड के लिए पाठ्य सूचना का मिलान किया जा सकता है, बल्कि अगले स्तर का मारिसा-ट्राई भी हो सकता है। "सकुंट" का अर्थ है कि पेड़ की संरचना एक बिटमैप के साथ एन्कोडेड है, जो इसे बहुत कम मेमोरी खर्च करने की अनुमति देता है। खैर, एक दिलचस्प विशेषता है: मारिसा ट्राय भी तुरंत एक "सही हैश" के रूप में कार्य करता है। प्रत्येक कुंजी को 0 से len (trie) -1 तक की एक अद्वितीय संख्या दी गई है, और 0 से len (trie) -1 तक की प्रत्येक संख्या एक एकल कुंजी से मेल खाती है; आप कुंजी को संख्या द्वारा या कुंजी द्वारा संख्या से प्राप्त कर सकते हैं।

गति में - डेटारी 10 बार मारिसा-ट्राई से तेज है।

वापस झांकने के लिए। मारिसा-ट्राई के साथ डेट्री के एक सरल प्रतिस्थापन के बाद, यह पता चला कि पूरे खेत में 5 एमबी मेमोरी है, और 2-5 हजार शब्दों / सेकंड (बिना पूर्वसूचक के) की गति से काम करता है।

एक तरफ - 5Mb शांत है (हालांकि अब तक एक भविष्यवक्ता के बिना)। लेकिन दूसरी ओर - 2-5 हजार शब्द / सेकंड - धीरे-धीरे 20-60 हजार शब्दों / सेकंड के बाद, + मैं वास्तव में मारिसा-ट्राइ से कसकर बंधना नहीं चाहता, क्योंकि यह pymorphy2 को स्थापित करने के लिए एक संकलक आवश्यकता की ओर ले जाएगा। मैं पूरी तरह से समझ गया था कि डेट्री कैसे काम करती है, और एक अजगर-संगत कार्यान्वयन लिखना एक समस्या नहीं होगी, लेकिन मरीसा-ट्राई ... मारिसा-ट्राई के मामले में, पोर्ट करना संभव होगा, लेकिन इसके लिए अधिक प्रयास की आवश्यकता होगी, और सबसे अधिक संभावना यह काम करेगी - यह सवाल शायद "स्थगित" होगा, और pymorphy2 को स्थापित करने के लिए एक कंपाइलर की आवश्यकता होगी।

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

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

इस बिंदु पर, मैंने "कॉपी सिस्टम" के विचार से निपटना बंद कर दिया; डेटामरी और मरीसा-ट्राई के साथ अधूरे विकल्प शुरुआती pymorphy2 कमिट में उपलब्ध हैं।

मुझे यह संदेह है कि सिस्टम का उपयोग करता है (अच्छी तरह से, प्रकाशन के अनुसार, मुझे पता नहीं चल सकता है कि अब वहाँ क्या उपयोग किया जाता है) शब्दों के कुछ हिस्सों के साथ कई ट्राइ करते हैं, क्योंकि वे भविष्यवाणियों के लिए एल्गोरिदम का वर्णन अधिक आसानी से करना संभव बनाते हैं, लेकिन बस इसके लिए स्मृति में सभी शब्दों को पूर्ण रूप से संग्रहीत नहीं करना है मेरे परीक्षणों के अनुसार, एक नियमित तिकड़ी के साथ यह (शब्द + डेटा उनके प्रतिमानों के बारे में होगा) 300-400 की मेगाबाइट्स, डेटारी के साथ - 200 की मेगाबाइट्स, लेकिन MARISA-Trie के साथ सब कुछ 20 की मेगाबाइट फिट कर सकती है। कुछ "नियमित" का प्रयोग करें। जैसा कि mystem के पेपर में यह एक अच्छी ट्रिक है, लेकिन इस तरह, जैसा कि मुझे लगता है (मैं गलत हो सकता हूं, "मैं चाहता हूं कि मेरा सिस्टम" अंत तक दृष्टिकोण काम नहीं करता) मौलिक रूप से "सभी शब्दों को रखने के मुकाबले अधिक धीमी गति से काम करता है"।

वापस भविष्य के लिए

अपने आप में, मैरिसा-ट्राई सभी शब्दों को स्मृति में रखने के लिए फिट नहीं था: यह त्वरित नहीं था - जो इस तथ्य से गति में संभावित लाभ को ऑफसेट करता है कि शब्दों को टुकड़ों में इकट्ठा करने की आवश्यकता नहीं होगी, + एपीआई में "कदम से कदम" की संभावना नहीं थी मनमाने तरीके से पेड़ के चारों ओर घूमने के लिए, जो आवश्यक था - मुझे पहले से ही याद नहीं है - क्या, शायद - पत्र के सही समर्थन के लिए in। तब एक अस्पष्ट स्मरण आया कि anot.ru में किसी भी तरह किसी भी समय सभी शब्दों को याद किया जाता है।

इसलिए, मैंने aot.ru से रूपात्मक विश्लेषक के विवरण को फिर से पढ़ना शुरू किया , और विशेष रूप से, पैरा "बाइनरी शब्दकोश प्रतिनिधि"। वह लौट आया, इसलिए बोलने के लिए, जहां यह सब शुरू हुआ।

Aot.ru पर लेख में सब कुछ "स्वचालित" कहा जाता है।

एक "एलियनेबल" डेटा संरचना के साथ संस्करण (जिसका उपयोग किसी और चीज़ के लिए किया जा सकता है - अच्छी तरह से, एक डैट्री या मरीसा-ट्राई की तरह) मुझे एक डिक्शनरी के साथ एक विशेष ऑटोमोबाटन की तुलना में बहुत अधिक (और पसंद है)। एक विशेष आटोमैटन को pymorphy2 में "दफन" किया जाएगा - वहां से कुछ भी पुन: उपयोग नहीं किया जा सकता है, यह केवल पाइमॉर्फी के ढांचे के भीतर डीबग किया जा सकता है, और पेम्फ की संरचना के भीतर जटिलता ठीक से जमा होगी। मैंने आमतौर पर उस पैराग्राफ को अपनी आंखों के माध्यम से चलाया, सोचा "हम्म हम्म, बुरा" और यह अलग तरीके से करने का एक तरीका है।

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

यह सच है कि वे कहते हैं कि "कंप्यूटर विज्ञान में केवल दो कठिन समस्याएं हैं: कैश अमान्य और नामकरण की चीजें।" मुझे "कैश अमान्य" के बारे में पता नहीं है, लेकिन मुझे लगा कि "नामकरण चीजें" यहां पूरी तरह से हैं।

आप ऐसे क्षणों में एक पूर्ण बेवकूफ लगते हैं; सब कुछ सरल था, सब कुछ मेरी शुरुआत से पहले मेरी आँखों के सामने था, और मुझे इस बारे में कई बार (मशीनों के बारे में और DAAG के बारे में) बताया गया है।

तो, नई योजना यह थी: पीटा ट्रैक पर

C / C ++ में DAWG कार्यान्वयन खोजें;
डेटापी और मरीसा-ट्राई के समान एपीआई के साथ इसके लिए एक आवरण बनाएं;
DAWG में सभी शब्द लिखें (तुरंत उनके व्याकरणिक रूपों के बारे में जानकारी के साथ)
बोनस - स्थापना को सरल बनाने के लिए DAWGs पढ़ने के लिए विशेष रूप से अजगर पुस्तकालय बनाएं।

इस मामले में शब्दावली शब्दों का रूपात्मक विश्लेषण केवल DAWG से शब्द के बारे में जानकारी प्राप्त करने के लिए नीचे आता है; सरलतम मामले में (यह मानते हुए कि किसी शब्द में केवल 1 पार्सिंग हो सकता है, और यह कि केवल व्याकरणिक जानकारी की आवश्यकता है) यह कोड की एक पंक्ति हो सकती है।

DAWG ( dawgdic ) के लिए एक अच्छा पुस्तकालय उसी सुसुम याता में मिला, जिसे marisa-trie द्वारा लिखा गया था; मैंने इसके लिए एक अजगर आवरण बनाया: github.com/kmike/DAWG और एक अजगर इस प्रारूप का "पाठक": github.com/kmike/DAWG-Python (जिसे स्थापित करने के लिए कंपाइलर की आवश्यकता नहीं है)।

संपूर्ण डिक्शनरी, एनोटेशन के बिना, DAWG में लगभग 3MB, और एनोटेशन के साथ लगभग 7MB (= प्रत्येक शब्द को पार्स करने की जानकारी के साथ) लिया। तुलना के लिए, यदि आप अजगर डेटा को "जैसा है" में लोड करते हैं, तो यह कई गीगाबाइट मेमोरी लेता है।

वह सब बना रहा जिसे pymorphy2 लिखना था :)

लेख किसी भी तरह अंतहीन है, लेकिन pymorphy2 को अब अंदर कैसे व्यवस्थित किया जाता है - इस बारे में अब तक लगभग कुछ भी नहीं हुआ है। पाठ को और अधिक नहीं बढ़ाने के लिए, कुछ भी नहीं होगा; कैसे pymorphy2 के अंदर व्यवस्था की जाती है सुंदर (निरर्थक?) प्रलेखन में विस्तृत है , यहां तक कि चित्रों के साथ भी। मैं अब भी ध्यान दूंगा कि pymorphy2 पायथन लेमेटाइज़र क्लोन नहीं है, वहां सब कुछ अलग तरह से व्यवस्थित किया गया है, लेकिन aot.ru की जानकारी , निश्चित रूप से, बहुत मदद करती है।

यहाँ दो अजीब बेंचमार्क हैं (लैपटॉप प्रोसेसर 1.8 Ghz, पायथन 3.3 के तहत DAWG का उपयोग करके और PyPy 1.9 के तहत DAWG-Python का उपयोग करके):

Memory usage: 13.8M dictionary, 25.4M total (load time 0.14s) py33 runtests: commands[1] benchmarking MorphAnalyzer(): morph.parse(w) 29950 words/sec morph.parse(w) 47474 words/sec (considering word frequencies) morph.word_is_known(w) 244816 words/sec [p.normal_form for p in morph.parse(w)] 27807 words/sec [p.normalized for p in morph.parse(w)] 18231 words/sec [p.lexeme for p in morph.parse(w)] 3421 words/sec [{'NOUN'} in p.tag for p in morph.parse(w)] 23862 words/sec [p.tag.POS == 'NOUN' for p in morph.parse(w)] 22157 words/sec morph.tag(w): 96342 words/sec (considering word frequencies) morph.tag(w): 46767 words/sec morph.tag(w): 46935 words/sec (umlauts removed from input) morph.tag(w): 36331 words/sec (str(tag) called) benchmarking MorphAnalyzer(result_type=None): morph.parse(w) 35088 words/sec morph.parse(w) 62431 words/sec (considering word frequencies)

 Memory usage: 40.5M dictionary, 84.8M total (load time 0.39s) pypy runtests: commands[1] benchmarking MorphAnalyzer(): morph.parse(w) 41360 words/sec morph.parse(w) 108858 words/sec (considering word frequencies) morph.word_is_known(w) 243742 words/sec [p.normal_form for p in morph.parse(w)] 51728 words/sec [p.normalized for p in morph.parse(w)] 37551 words/sec [p.lexeme for p in morph.parse(w)] 14612 words/sec [{'NOUN'} in p.tag for p in morph.parse(w)] 44878 words/sec [p.tag.POS == 'NOUN' for p in morph.parse(w)] 45129 words/sec morph.tag(w): 133086 words/sec (considering word frequencies) morph.tag(w): 60049 words/sec morph.tag(w): 62567 words/sec (umlauts removed from input) morph.tag(w): 52632 words/sec (str(tag) called) benchmarking MorphAnalyzer(result_type=None): morph.parse(w) 60777 words/sec morph.parse(w) 124226 words/sec (considering word frequencies)

मुझे पता है कि यहाँ (क) संख्या बहुत समान है, इस तथ्य के बावजूद कि "अंदर" क्रियाएं बहुत अलग हैं (सी ++ आवरण + दुभाषिया बनाम जेट संकलक), और (ख) कि PyPy तेज है।

C ++ में DAWG का क्रियान्वयन (यदि आप इसका उपयोग अजगर से करते हैं, तो साइथन रैपर को ध्यान में रखते हुए) PyPy के तहत DAWG-Python की तुलना में कई गुना तेज है, और pymorphot2 (जो कि सबसे कम किया था) के शुरुआती संस्करण CPython के तहत तेज थे। समय के साथ, सुविधाएँ बड़ी हो गईं, कोड अधिक जटिल हो गया, pymorphy2 धीमा हो गया (पहले के संस्करण और 200 + हजार शब्द / सेकंड disassembled किया जा सकता है - हालांकि बहुत अच्छा नहीं और बहुत सुविधाजनक नहीं); तेजी से बुनियादी डेटा संरचना "आउटवे" बंद हो गया है - और PyPy pymorphy2 के तहत अब तेजी से काम करता है। दूसरी ओर, यह स्पष्ट है कि सीपीथॉन के लिए संस्करण को कैसे तेज किया जाए - साइथन में कुछ और फिर से लिखना (वैसे: मैं ऐसा करने की योजना नहीं है); PyPy के साथ यह इतना स्पष्ट नहीं है।

आप देख सकते हैं कि असली पाठ में 100 हजार शब्द / सेकंड पार्स करने से पायथन 3.3 (व्याकरण संबंधी जानकारी प्राप्त करना) और PyPy (पूर्ण पार्सिंग दोनों, प्रारंभिक रूप और सुविधाजनक एपीआई के साथ) प्राप्त किए जा सकते हैं। तुलना के लिए: "वास्तविक" mystem (लिखित, जाहिरा तौर पर, C ++ में) ने काम किया (शुरुआती चरणों में एक बार मेरे परीक्षणों के अनुसार) केवल डेढ़ से दो गुना तेज, और उसी मात्रा में स्मृति की आवश्यकता थी; इससे मैंने अपने लिए निष्कर्ष निकाला - शायद गलत तरीके से - कि तंत्र फिर भी कई त्रि के साथ एक दृष्टिकोण का उपयोग करता है; यदि शब्द अपनी संपूर्णता में संग्रहीत थे, तो C ++ कार्यान्वयन को और अधिक मजबूती से आना चाहिए, भले ही तंत्र और इसके अलावा कुछ और मुश्किल हो। अच्छी तरह से यह ऐसा है, फिर से असंतुलित बकबक के साथ।

यदि आप DAWG के या तो PyPy या C ++ कार्यान्वयन का उपयोग नहीं करते हैं, तो pymorphy2 अभी भी कई त्वरित गति से काम करेगा (अनुमानों से - एक दर्जन बार) pymorphy1 की तुलना में सभी त्वरण चालू होने के साथ - ठीक है, इसे पार्स करना बेहतर है।

मैं कैसे मदद कर सकता हूं

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

यह बहुत अच्छा होगा अगर किसी ने pymorphy1 से लापता सुविधाओं को पोर्ट करने में मदद की;
OpenCorpora से कोई भी मदद और pymorphy2 भी मदद;
ट्रैकर में कई खुले बग (कट्टर की अलग-अलग डिग्री) हैं;
pymorphy2 में अब एक बहुत ही आदिम टोकन बनाया गया है - आप एक बेहतर टोकनर का आविष्कार कर सकते हैं; वहां यह समझना अच्छा होगा कि pymorphy2.units.by_shape.py से कक्षाएं किस तरह से टोकन के साथ सहसंबंधित होती हैं;
सीएलआई में सुधार किया जा सकता है ताकि pymorphy2 का उपयोग पूर्ण कमांड लाइन उपयोगिता के रूप में किया जा सके;
आप pymorphy2 के लिए और अधिक भविष्यवाणियाँ लिखने का प्रयास कर सकते हैं (देखें कि pymorphy2.units में वर्तमान कैसे बनाए जाते हैं) - यदि आपको विस्तार के लिए इंटरफ़ेस अच्छा है, तो आपको यह समझने की ज़रूरत है कि इंटरफ़ेस विस्तार के लिए अच्छा है (+ विश्लेषण में सुधार करना और मानक वितरण में कुछ नया जोड़ना संभव है);
ठीक है, आप बस pymorphy2 का उपयोग शुरू कर सकते हैं।

बड़ी संख्या में लोगों ने भाग लिया pymorphy के विकास में, जिनमें से कई ने वास्तव में गंभीर योगदान दिया, और इस सब से बहुत दूर pymorphy2 में स्थानांतरित कर दिया गया; मैं नहीं चाहूंगा कि काम गायब हो जाए (मुझे लगता है कि यह गायब नहीं होगा)। इसकी मदद के बिना, मुझे कभी भी प्योरमोफी का समर्थन करने की प्रेरणा नहीं मिलेगी, या सब कुछ pymorphy2 के रूप में फिर से लिखने की प्रेरणा होगी।

और pymorphy2 में कई लोगों ने पहले से ही एक गंभीर योगदान दिया है, वैसे :)

संदर्भ

स्रोत कोड: github , bitbucket
प्रलेखन: pymorphy2.rtfd.org
बग ट्रैकर: github.com/kmike/pymorphy2/issues
चर्चा / समर्थन: गूगल-समूह
पायथन के लिए डेटा संरचनाएं जो इस प्रक्रिया के दौरान उत्पन्न हुईं: DAWG , DAWG-Python , marisa -trie , datrie , hat-trie

pymorphy2