जांच कर रहा है कि किसी स्ट्रिंग में अंग्रेजी वाक्य

Question

अभी तक, मैंने पूरी बात के माध्यम से एक शब्दकोश और फिर से लेने का फैसला किया है। हर बार जब मैं एक नई लाइन देखता हूं, तो मैं उस नई लाइन से अगली न्यूलाइन तक एक स्ट्रिंग बना देता हूं, फिर मैं स्ट्रिंग करता हूं। यह देखने के लिए कि वह अंग्रेजी शब्द कहीं है या नहीं। यह बहुत लंबा समय लगता है, प्रत्येक शब्द सत्यापित करने के लिए लगभग 1/2-1/4 एक सेकंड लेता है।

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

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

तार मैं इस तरह दिखेगा जाँच कर रहा हूँ:

"hithisisastringthatmustbechecked" 

लेकिन उनमें से ज्यादातर पूरा कचरा, बस अनियमित अक्षर शामिल था।

मैं अक्षरों की असंभव रचनाओं की जांच नहीं कर सकता, क्योंकि उस स्ट्रिंग को 'टीएम' के कारण 'थर्म' के बीच बाहर फेंक दिया जाएगा।

Answer 1

आप Knuth–Morris–Pratt (KMP) algorithm पर नियोजित करके खोज को तेज कर सकते हैं।

प्रत्येक शब्दकोष शब्द, और build a search table for it के माध्यम से जाएं। आपको केवल एक बार ऐसा करने की ज़रूरत है। अब अलग-अलग शब्दों की आपकी खोज तेज गति से आगे बढ़ेगी, क्योंकि "झूठी शुरूआत" समाप्त हो जाएगी।

Answer 2

इसे जल्दी करने के लिए बहुत सारी रणनीतियां हैं।

आइडिया 1

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

तो सरणी इस तरह दिखता है:।

a - substr[0] = "astringthatmustbechecked" 
b - substr[1] = "bechecked" 
c - substr[2] = "checked" 
d - substr[3] = "d" 
e - substr[4] = "echecked" 
f - substr[5] = null // since there is no 'f' in it 
... and so forth 

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

आइडिया 2

शब्दकोश में सबसे लंबे शब्द को ध्यान में रखते हुए उस विचार पर विस्तार करें और उस दूरी से अधिक लंबे समय तक चलने वाले सरणी में उन तारों से अक्षरों से छुटकारा पाएं।

तो तुम सरणी में इस है:

a - substr[0] = "astri" 

हैं:

a - substr[0] = "astringthatmustbechecked" 

लेकिन अगर सूची में सबसे लंबा शब्द 5 पत्र है, रखने के लिए कोई जरूरत नहीं है किसी भी अधिक से अधिक पत्र कई बार आपको अधिक पत्र रखना है। इसलिए इसे पूरी स्ट्रिंग रखना है क्योंकि "ई" 5 अक्षर से कम दिखाता रहता है।

e - substr[4] = "echecked" 

तारों को नियंत्रित करते समय आप किसी भी विशेष पत्र से शुरू होने वाले सबसे लंबे शब्दों का उपयोग करके इस पर विस्तार कर सकते हैं।

आइडिया 3

यह 1 और 2 इसका एक विचार है कि आप के बजाय इस्तेमाल कर सकते हैं के साथ कोई संबंध नहीं है।

आप शब्दकोश को एक लिंक की गई डेटा संरचना में संग्रहीत नियमित अभिव्यक्ति में बदल सकते हैं। नियमित अभिव्यक्ति भी लिखना संभव है और फिर इसे लागू करना संभव है।

मान लें इन शब्दकोश में शब्द हैं:

arun 
bob 
bill 
billy 
body 
jose 

बिल्ड जुड़ा हुआ संरचना इस तरह की। (इसका एक द्विआधारी पेड़, वास्तव में, इस तरह से कि मैं इसे कैसे उपयोग करने के लिए की व्याख्या कर सकते में प्रतिनिधित्व किया।)

a -> r -> u -> n -> * 
| 
b -> i -> l -> l -> * 
| |    | 
| o -> b -> * y -> * 
|   | 
|   d -> y -> * 
| 
j -> o -> s -> e -> * 

तीर एक पत्र एक अन्य पत्र का पालन किया है कि इंगित करते हैं। तो "आर" को "ए" के बाद होना चाहिए या यह मेल नहीं खा सकता है।

नीचे जाने वाली रेखाएं एक विकल्प को दर्शाती हैं। आपके पास "ए या बी या जे" संभावित अक्षर हैं और फिर "बी" के बाद "i या o" संभावित अक्षर हैं।

नियमित अभिव्यक्ति इस प्रकार दिखती है:/(अरुण) | (बी (बीमार (वाई +)) | (ओ (बी | डीई))) | (जोस)/(हालांकि मैंने एक पैर फिसल दिया हो सकता है)। यह इसे रेगेक्स के रूप में बनाने का सारांश देता है।

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

यह बहुत काम है लेकिन कभी-कभी आसान हो सकता है।

साइड नोट मैंने कुछ कार्यक्रमों को एक प्रोग्राम लिखकर बनाया है जो कोड लिखता है जो बाइनरी पेड़ डेटा संरचना को देखने वाले कोड रखने के बजाय सीधे एल्गोरिदम चलाता है।

लंबवत बार विकल्पों के प्रत्येक सेट के बारे में सोचें switch एक विशेष वर्ण स्तंभ के खिलाफ कथन और प्रत्येक तीर घोंसले में बदल रहा है। यदि केवल एक विकल्प है, तो आपको पूर्ण switch कथन की आवश्यकता नहीं है, केवल if।

यह कुछ तेज़ चरित्र मिलान था और वास्तव में कुछ कारणों से काम करता था जो आज मुझे बढ़ाता है।

Answer 3

कैसे एक Bloom Filter के बारे में?

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

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

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

Answer 4

सिद्धांत रूप में, मुझे लगता है कि आप एक मार्कोव मॉडल को प्रशिक्षित करने और उपयोग करें कि अगर एक स्ट्रिंग शायद एक वाक्य या शायद कचरा है तय करने के लिए सक्षम होना चाहिए। शब्दों को पहचानने के लिए ऐसा करने के बारे में एक और सवाल है, वाक्य नहीं: How do I determine if a random string sounds like English?

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

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

alicewasbeginningtogetverytiredofsittingbyhersisteronthebankandofhavingnothingtodoonceortwiceshehadpeepedintothebookhersisterwasreadingbutithadnopicturesorconversationsinitandwhatistheuseofabookthoughtalicewithoutpicturesorconversation

यह अजीब लगता है, लेकिन जहाँ तक एक मार्कोव मॉडल के रूप में संबंधित, शास्त्रीय कार्यान्वयन से यह एक मामूली अंतर है।

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

Answer 5

इस कोड How to split text without spaces into list of words? से संशोधित किया गया था:

from math import log 

words = open("english125k.txt").read().split() 
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words)) 
maxword = max(len(x) for x in words) 

def infer_spaces(s): 
    """Uses dynamic programming to infer the location of spaces in a string 
    without spaces.""" 

    # Find the best match for the i first characters, assuming cost has 
    # been built for the i-1 first characters. 
    # Returns a pair (match_cost, match_length). 
    def best_match(i): 
     candidates = enumerate(reversed(cost[max(0, i-maxword):i])) 
     return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates) 

    # Build the cost array. 
    cost = [0] 
    for i in range(1,len(s)+1): 
     c,k = best_match(i) 
     cost.append(c) 

    # Backtrack to recover the minimal-cost string. 
    costsum = 0 
    i = len(s) 
    while i>0: 
     c,k = best_match(i) 
     assert c == cost[i] 
     costsum += c 
     i -= k 

    return costsum 

the same dictionary of that answer का उपयोग करते हुए और अपने स्ट्रिंग आउटपुट

>>> infer_spaces("hithisisastringthatmustbechecked") 
294.99768817854056 

परीक्षण

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