प्रत्येक पंक्ति पर एकाधिक (15+) regexes के खिलाफ पाठ के एक शरीर को पार्स करने का सबसे अच्छा तरीका क्या है?

Question

मेरे पास टेक्स्ट का एक समूह है जिसे मुझे स्कैन करना है और प्रत्येक पंक्ति में कम से कम 2 और कभी-कभी जानकारी के चार भाग होते हैं। समस्या यह है कि प्रत्येक पंक्ति 15-20 अलग-अलग कार्रवाइयों में से 1 हो सकती है।

माणिक में वर्तमान कोड इस तरह कुछ हद तक दिखता है:

 
text.split("\n").each do |line| #around 20 times.. 

.............. 

     expressions['actions'].each do |pat, reg| #around 20 times 

................. 

यह स्पष्ट रूप से 'समस्या' है। मैंने सभी रेगेक्सन को एक साथ जोड़कर इसे तेज (सी ++ में 50% मार्जिन में) बनाने में कामयाब रहा, लेकिन यह अभी भी गति की आवश्यकता नहीं है - मुझे इन फ़ाइलों में से हजारों को तेजी से पार्स करने की आवश्यकता है!

अभी मैं उन्हें रेगेक्स के साथ मेल खाता हूं - हालांकि यह असहिष्णु रूप से धीमा है। मैंने रूबी के साथ शुरुआत की और सी ++ पर उम्मीद की कि मुझे गति वृद्धि मिलेगी और यह अभी नहीं हो रहा है।

मैंने पीईजी और व्याकरण आधारित पार्सिंग पर आकस्मिक रूप से पढ़ा है लेकिन इसे लागू करने में कुछ मुश्किल लग रहा है। क्या यह दिशा मुझे सिर चाहिए या क्या अलग-अलग मार्ग हैं?

मूल रूप से मैं पोकर हाथ इतिहास को पार्स कर रहा हूं और हाथ इतिहास की प्रत्येक पंक्ति में आमतौर पर जानकारी के 2-3 बिट होते हैं जिन्हें मुझे इकट्ठा करने की आवश्यकता होती है: खिलाड़ी कौन था, कितना पैसा या कार्रवाई किस कार्ड से जुड़ी हुई थी .. आदि ..

नमूना पाठ की जरूरत है कि पार्स किया जा सकता:

 
buriedtens posts $5 
The button is in seat #4 
*** HOLE CARDS *** 
Dealt to Mayhem 31337 [8s Ad] 
Sherwin7 folds 
OneMiKeee folds 
syhg99 calls $5 
buriedtens raises to $10 

मैं इस जानकारी प्रत्येक कार्य एक xml नोड में बदल गया है इकट्ठा करने के बाद।

अभी मेरा मेरा रूबी कार्यान्वयन मेरे सी ++ से बहुत तेज है लेकिन यह जांच है। मैं यहाँ सब कोड पोस्ट करने के लिए नहीं करना चाहते हैं, लेकिन अभी तक मेरे हाथ/दूसरा ऐसा दिखाई देगा:

बस क्योंकि मैं सी कोड में अच्छी तरह से 4-5 साल के

अद्यतन के लिए नहीं लिखा है

 
588 hands/second -- boost::spirit in c++ 
60 hands/second -- 1 very long and complicated regex in c++ (all the regexen put together) 
33 hands/second -- normal regex style in ruby 

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

संबंधित प्रश्न: Efficiently querying one string against multiple regexes.

Answer 1

मैं

• Boost Spirit या
• Antlr अगर व्याकरण जटिल है सुझाव है;
• Xpressive यदि यह थोड़ा आसान है,
• Tokenizer और हस्तनिर्मित कोड यदि यह मामूली है।

गुड लक

Answer 2

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

Answer 3

Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) देखें। आपके डेटा की मात्रा और आपके रेगेक्स कितना जटिल है, इस पर निर्भर करता है कि यह आपके स्वयं के पार्सिंग तर्क को लिखने के लिए तेज़ हो सकता है।

Answer 4

क्या नियमित अभिव्यक्ति मिलान कभी ओवरलैप करते हैं? यही है, जब दो या दो से अधिक रेगेक्स एक ही पंक्ति से मेल खाते हैं, तो क्या वे हमेशा लाइन के विभिन्न हिस्सों से मेल खाते हैं (कोई ओवरलैप नहीं)?

मैचों कभी नहीं होते हैं, तो आपकी खोज एक रेगुलर एक्सप्रेशन 15 regexes को जोड़ती है आप अब का उपयोग कर चलाएँ:

regex1|regex2|regex3|...|regex15 

उपयोग समूहों पर कब्जा करता है, तो आप यह निर्धारित करने के लिए 15 regexes के मिलान करने में सक्षम होना चाहिए ।

एक लंबे रेगेक्स के लिए एक बार आपके डेटा को खोजना 15 बार खोजने से तेज़ होगा। आपके द्वारा उपयोग किए जा रहे रेगेक्स इंजन और आपके नियमित अभिव्यक्ति की जटिलता पर कितनी तेज़ी से निर्भर करता है।

Answer 5

यदि आप पर्ल का उपयोग कर रहे थे, तो यह करने का एक तरीका यहां है।
perldoc perlfaq6

while (<>) { 
    chomp; 
    PARSER: { 
     m/ \G(\d+\b )/gcx && do { print "number: $1\n"; redo; }; 
     m/ \G(\w+  )/gcx && do { print "word: $1\n"; redo; }; 
     m/ \G(\s+  )/gcx && do { print "space: $1\n"; redo; }; 
     m/ \G([^\w\d]+)/gcx && do { print "other: $1\n"; redo; }; 
    } 
} 

से नकल प्रत्येक पंक्ति के लिए, PARSER पाश पहले एक शब्द सीमा के बाद अंक की एक श्रृंखला से मिलान करने की कोशिश करता है। यह मैच उस स्थान पर शुरू होना है जहां अंतिम मैच छोड़ा गया था (या पहले मैच में स्ट्रिंग की शुरुआत)। चूंकि c ध्वज का उपयोग करता है, यदि स्ट्रिंग उस नियमित अभिव्यक्ति से मेल नहीं खाती है, तो perl pos() रीसेट नहीं करता है और अगला मिलान एक अलग स्थिति को शुरू करने के लिए एक ही स्थिति में शुरू होता है।

Answer 6

पर्ल में एक साधारण परीक्षण का प्रयास करें। "अध्ययन" समारोह के बारे में पढ़ें। क्या मैं कोशिश कर सकते हैं है:

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

मैंने कोशिश नहीं की है, लेकिन यह दिलचस्प हो सकता है।

Answer 7

एक और विचार यदि आपके पास इसका उपयोग करने के लिए एक स्पिफी क्वाड या ऑक्ट कोर सर्वर है।

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

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

Answer 8

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

मुझे रूबी नहीं पता, लेकिन पर्ल में मैं थोड़ा स्विच स्टेटमेंट करता हूं, साथ ही महत्वपूर्ण भागों को $ 1, $ 2 आदि में प्राप्त करने के साथ ही .. मेरे अनुभव में, यह स्ट्रिंग बनाने से धीमा नहीं है तुलना और फिर अन्य माध्यमों के साथ लाइन विभाजित।

HAND_LINE: for ($Line) 
    { /^\*\*\* ([A-Z ]+)/ and do 
     { # parse the string that is captured in $1 
      last HAND_LINE; }; 
     /^Dealt to (.+) \[(.. ..)\]$/ and do 
     { # $1 contains the name, $2 contains the cards as string 
      last HAND_LINE; }; 
     /(.+) folds$/ and do 
     { # you get the drift 
      last HAND_LINE; }; }; 

मुझे नहीं लगता कि आप वास्तव में इसे तेज़ी से बना सकते हैं। चेक को उन पंक्तियों के लिए रखें जो सबसे पहले सबसे अधिक स्थिति में होते हैं (संभवतः गुना बयान) और जो केवल अंतिम रूप से कम होते हैं (नया हाथ, "*** NEXT PHASE ***")।

यदि आपको पता चलता है कि वास्तविक फ़ाइल पढ़ने एक बाधा है, तो आप शायद यह देख सकते हैं कि आप कौन सी मॉड्यूल का उपयोग बड़ी फ़ाइलों को हल करने के लिए कर सकते हैं; पर्ल के लिए, Tie::File दिमाग में आता है।

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

Answer 9

मैंने पीईजी और व्याकरण आधारित पार्सिंग पर आकस्मिक रूप से पढ़ा है लेकिन इसे लागू करने में कुछ मुश्किल लग रहा है। क्या यह दिशा मुझे सिर चाहिए या क्या अलग-अलग मार्ग हैं?

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

रूबी में Treetop है जो एक पार्सर जनरेटर है जो पीईजी का उपयोग करता है। मैंने हाल ही में एक लघु व्याकरण के साथ एक रेगेक्स भारी हाथ लिखित पार्सर को बदलने में काफी सुखद पाया।

Answer 10

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