"फजी रेगुलर एक्सप्रेशंस" के साथ पार्स एड्रेस

सारांश: लाइब्रेरी के बारे में मैंने प्राकृतिक भाषा के भावों के एक शब्दकोश के साथ तुलना के लिए लिखा था - विशेष रूप से, शहर के पते।

दादाजी के गाँव में

भौगोलिक अर्थ में - पता लिखने के कितने तरीके हैं?

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

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

एक उदाहरण अधिक जटिल है:
दूसरा हॉर्स-आर्मी स्ट्रीट - यहां कवि की आत्मा को घूमने के लिए जगह है। संख्या को "2" या केवल "2" के रूप में व्यक्त किया जा सकता है, या इसे "सेकंड" या "सेकंड" कहे जाने वाले शब्दों में भी लिखा जा सकता है - लगभग 50% उत्तरदाताओं में "घोड़ा" और "सेना" के बीच एक हाइफ़न होगा। ढेर करने के लिए, यह पता चला है कि "घोड़ा-सेना" किसी को लंबा लग रहा था और "2 कोनोर्म" तक कम हो गया था। सेंट। "

अन्य दिलचस्प उदाहरण "सेंट" नामों से जुड़े हैं। नाविक ज़ेलेज़्न्यक ”(या बस“ ज़्लीज़्न्यक ”?),“ प्र। मोरीसा टोर्ज़ा ”(या“ मारिसा टेरेसा ”?) और साथ ही पूरी तरह से महाकाव्य मामले“ उल। दूसरी छमाही की तीसरी पंक्ति "," रैब्तसकोए के गांव की सड़क "," सेंट। इज़ोरा नदी का बायाँ हिस्सा - "कृपया मुझे माफ़ कर दें अगर मैं खुद को स्मृति से सही ढंग से लिखने का प्रबंधन नहीं करता।

वैसे यह व्यवसाय के लिए खुशी की बात है

अब कल्पना कीजिए। कि आप एक ऐसा अनुप्रयोग विकसित कर रहे हैं, जो अन्य बातों के अलावा, "कंघी" (यानी एक एकीकृत रूप में ले जाना चाहिए) यह सब भूगोल है। मैं 2011 में इस पर आया था - कार्यक्रम को प्रिंट होने से पहले पते वाले विज्ञापनों को संसाधित करना था।

व्यवसाय के दृष्टिकोण से, "कॉम्बिंग" की आवश्यकता कई कारणों से प्रासंगिक थी - एक ही (लेकिन अलग-अलग लिखे गए) पते के साथ कई विज्ञापन जारी करने के लिए नहीं - या ब्लैक लिस्टेड पते वाले विज्ञापन जारी करने के लिए नहीं जिनके लिए आपको जुर्माना (उदाहरण के लिए, ऑब्जेक्ट) मिल सकता है अचल संपत्ति जिसके संबंध में न्यायिक जाँच हो, आदि)

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

इससे पहले कि यह कार्य मेरे हाथों में पड़ता, उसी उद्देश्य के लिए पुराने एप्लिकेशन ने एक विशेष व्यक्ति की सेवाओं का उपयोग किया - ऑपरेटर - जिसने कई घंटों के लिए खुद को लगभग 30,000 लाइनों के माध्यम से पारित किया और अपने विवेक पर उन्हें सही किया। यह कई कारणों से बहुत सुविधाजनक नहीं था। इसमें यह भी शामिल है कि ऑपरेटर को एक अजीब आदत थी - वह 90% सड़कों पर भेजें जो उसने कोलपिनो को नहीं जानता था। नतीजतन, जब मैंने सहेजे गए शब्दकोश फ़ाइलों की जाँच की, तो मुझे कोलपिनो जिले में अन्य सभी क्षेत्रों की तुलना में अधिक सड़कें मिलीं।

... और प्रोग्रामर भी खुश

अनुप्रयोग के पिछले संस्करण ने ऑपरेटर की सेवाओं का उपयोग क्यों किया?

यह अनुमान लगाना आसान है कि पतों के सॉफ्टवेयर हैंडलिंग के लिए कुछ अस्पष्ट चाल की आवश्यकता होती है। मालिकों और सहकर्मियों से मैंने जो दिलचस्प प्रस्ताव सुने, उनमें ये थे:

• ANTLR की जरूरत है - मुझे यह समझाना पड़ा कि यह मशीन भाषाओं के लिए है और सिर्फ अत्यधिक स्वतंत्रता, मजाकिया स्वभाव आदि की अनुमति नहीं देता है;
• yuzay regexps - "Tsvetochnaya Street" नाम के शीर्ष में सभी प्रकार के टाइपो के लिए regexp लिखने के प्रस्ताव ने इस उद्यम के लेखक को इसकी सभी विफलता दिखाई;
• तंत्रिका नेटवर्क - इस तरह के एक उज्ज्वल विचार के लेखक दुर्भाग्य से, यह स्पष्ट नहीं कर सकते हैं कि तंत्रिका नेटवर्क का उपयोग कैसे प्रस्तावित है। मेरे अनुमान में, यदि आप इनपुट के साथ इनपुट लाइन के आउटपुट और हर चरित्र (या हर बिट) के साथ शहर के सभी संभावित स्थानों के नाम बनाते हैं, तो यह विचार शायद सफल होगा - केवल प्रशिक्षण के लिए यह कुछ अकल्पनीय संख्या में विकल्प (अच्छी तरह से, समय) लेगा ।

प्रयोग और दृष्टिकोण

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

लेकिन "सेंट के बारे में क्या। पैलेस "और" पी एल। पैलेस ”- यहाँ“ y ”को“ p ”से बदलना एक टाइपो नहीं है, हालाँकि एल्गोरिथ्म के दृष्टिकोण से इसका वजन एक ही है जैसे कि आप“ पैलेस ”को“ डोर ”से बदल देते हैं।

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

इस विचार ने पहले से ही अधिक दिलचस्प काम किया। हालाँकि, संक्षिप्तीकरण, शब्दों की क्रमबद्धता, वैकल्पिक शब्दों की चूक (जैसा कि "अलेक्सांद्र मेट्रोसोव स्ट्रीट" में - "अलेक्जेंड्रा" अच्छी तरह से याद कर सकती है) - उसने अभी भी हल नहीं किया।

दो बार सोचने के बिना, मैंने इन नियमों का वर्णन करने के लिए एक "मेटा-भाषा" बनाने का काम किया। क्या हुआ, मैंने "लाइब्रेरी ऑफ़ पर्सिंग फ़ज़ी रेगुलर एक्सप्रेशंस फॉर जावा" कहा।

किसी दिए गए अभिव्यक्ति के साथ "सामंजस्य" कार्यक्षमता के अलावा, यह अभिव्यक्ति में किसी भी हिस्से को सीधे बदलने के लिए नियमों को वर्तनी में सक्षम करने के लिए सुविधाजनक होने के लिए निकला।

संक्षिप्त विवरण

भाषा का वाक्य-विन्यास कोष्ठक के लिए मेरे महान प्रेम को दर्शाता है। किसी भी अभिव्यक्ति और उपप्रकार को कोष्ठक में संलग्न किया गया है; अभिव्यक्ति का प्रकार उद्घाटन ब्रैकेट के बाद वर्ण द्वारा निर्धारित किया जाता है। पढ़ने में आसानी के लिए गोल, चौकोर और घुंघराले ब्रैकेट की अनुमति है - मुख्य बात यह है कि उद्घाटन और समापन ब्रैकेट जोड़े में मेल खाते हैं।

(= सड़क, फूल)

प्रतीक "=" का अर्थ है कि शब्द दिए गए क्रम में या विपरीत में मौजूद होना चाहिए - अर्थात यह अभिव्यक्ति "फ्लावर स्ट्रीट" या "फ्लावर स्ट्रीट" से मेल खाती है।

और हां, टाइपो की स्वीकार्य संख्या को थ्रेशोल्ड मान द्वारा सेट किया जाता है जब तुलना के लिए ऑब्जेक्ट बनाते हैं, तो डिफ़ॉल्ट रूप से यह 75% के लिए होता है, जो आपको "Tsvyatochnaya" और यहां तक ​​कि "उलिट्स सस्वितात्नाया" को छोड़ देगा।

(बराक, (हुसैन), ओबामा, (द्वितीय)

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

(^ (व्लादिमीर, लेनिन), (निकिता, ख्रुश्चेव), (कार्ल, मार्क्स)

प्रतीक "^" का अर्थ है सूचीबद्ध सूक्तियों में से एक का चयन - इस मामले में, अभिव्यक्ति की तुलना तीन सूचीबद्ध आंकड़ों में से किसी के साथ की जा सकती है, जबकि "व्लादिमीर मार्क्स" और "निकिता लेनिन" काम नहीं करेंगे।

अन्य अभिव्यक्तियाँ हैं - संख्याओं की श्रेणियों के साथ सामंजस्य स्थापित करने के लिए (यह उनकी तुलना में एक फजी लागू करने के लिए असुविधाजनक होगा), एक स्पष्ट regexp के साथ सामंजस्य स्थापित करने के लिए (अप्रत्याशित रूप से? लेकिन यह उपयोगी हो सकता है) - संक्षिप्ताक्षरों के साथ सामंजस्य की संभावना भी है ("" "प्रतीक" का उपयोग करके)। नाम समूहों को उनके साथ आगे की जाँच करने या उन्हें प्रतिस्थापन के रूप में उपयोग करने के लिए कैप्चर करें - यह सब मैंने प्रलेखन में वर्णित किया है।

प्रतिस्थापन कार्यक्षमता बड़े अभिव्यक्तियों के लिए प्रासंगिक हो जाती है, एक संक्षिप्त, प्रासंगिक उदाहरण देना मुश्किल है, लेकिन कोशिश करें:

[^ (((व्लाद *, व्लादिमीर, बी) | वोवा) ~ ए | डियर_ $ ए, (^ अल *, अलेक्जेंडर, साशा) | साशा) ~ बी | नस्टी_ $ बी] ~ सी। हैलो | $ C

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

निष्कर्ष

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

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

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

संदर्भ

जावा के लिए फजी रेग्जाप्स वास्तव में मेरी लाइब्रेरी है।

Javadocs - प्रलेखन और "फजी regexps" की भाषा का विस्तृत विवरण

TRE एक और regexp लाइब्रेरी है (C में) फजी तुलना की संभावना के साथ - मैंने इसका उपयोग करने के बारे में नहीं सोचा था, इसमें जावा संस्करण नहीं है और मुझे प्रतिस्थापन की आवश्यकता है; इसमें तुलनात्मक त्रुटियों का भी अलग-अलग मूल्यांकन किया जाता है, हालाँकि, यह अन्य कार्यों में उपयोगी हो सकती है।

डामेरो-लेवेन्शिन एक लोकप्रिय सरल फजी तुलना एल्गोरिथ्म है जो मैंने भावों में एकल शब्दों की तुलना करने के लिए आंतरिक रूप से उपयोग किया था।

वादा किया हुआ उदाहरण

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

 (^
     अब्खाज़िया, ऑस्ट्रेलिया, ऑस्ट्रिया, अजरबैजान, अल्बानिया, अल्जीरिया, एंगुइला,
     अंगोला, अंडोरा, अर्जेंटीना, आर्मेनिया, अरूबा, अफगानिस्तान, बहामास,
     बांग्लादेश, बारबाडोस, बहरीन, बेलीज, बेल्जियम, बेनिन, बरमूडा,
 // ...
     फिजी, फिलीपींस, फिनलैंड, फ्रांस, क्रोएशिया, चाड, मोंटेनेग्रो,
     चेक गणराज्य, चिली, स्विट्जरलैंड, स्वीडन, स्वालबार्ड, इक्वाडोर, इरिट्रिया, एस्टोनिया
     इथियोपिया, जमैका, जापान,
     [^ (कनेक्टेड *, स्टेट *, (? आमेर *)), अमेरिका, यूएसए, यूएसए] | यूनाइटेड स्टेट्स ऑफ अमेरिका,
 // ...
     [^ कोमोरोस, (कोमोर *, (@ आईएसलैंड)]]। कोमोरोस,
     [^ कांगो, ब्रेज़ाविल, (@ REPUB), कांगो]] | कांगो गणराज्य,
     [^ ज़ैरे, DRC, ({^ DR, (डेमोक्र * *, (@ REPUB))}, कांगो]] DR_Congo |
 // ...
     [^ बर्मा, म्यांमार] | म्यांमार,
     [(@ आईसलैंड), मेन] आइल ऑफ मैन,
     [नागोर्नो *, (? -?), कारा *, (@ REPUB)] | नागोर्नो-काराबाखो,
     [^ नीदरलैंड, नीदरलैंड] | नीदरलैंड्स |
 // ...
     [यू *, ओससेटिया] | South_Ossetia,
     [^ साउथ अफ्रीका, {(^ साउथ अफ्रीकन *, {साउथ *, (? -), अफ्र *}}, (@ REPUB)}] | साउथ अफ्रीकन रिपब्लिक,
     [यू *, सूडान] | South_Sudan
 )

 :: आईसलैंड (^ द्वीप *, {o, -, *} में)
 :: REPUB (^ पी, प्रतिनिधि, प्रतिनिधि * *)