अक्षरों की एक लंबी स्ट्रीम में शब्दों को खोजें। ऑटो-टोकनइज़

Question

वर्णों की लंबी स्ट्रीम में आपको सही शब्द कैसे मिलेगा?

इनपुट:

"The revised report onthesyntactictheoriesofsequentialcontrolandstate" 

गूगल के आउटपुट:

"The revised report on syntactic theories sequential controlandstate" 

आपको क्या लगता है गूगल यह करता है (जो पर्याप्त समय है कि वे उत्पादन उत्पादन पर विचार करीब है)? आप सटीकता कैसे बढ़ाएंगे?

Answer 1

मैं इस तरह पुनरावर्ती एल्गोरिदम की कोशिश करेंगे:

• प्रत्येक स्थिति में एक स्थान डालने का प्रयास करें। यदि बायां हिस्सा एक शब्द है, तो सही भाग पर दोहराएं।
• सभी अंतिम आउटपुट में वैध शब्दों की संख्या/कुल शब्दों की संख्या की गणना करें। सबसे अच्छा अनुपात वाला एक आपके उत्तर की संभावना है।

उदाहरण के लिए, यह दे रही है "thesentenceisgood" चलाने होगा:

thesentenceisgood 
the sentenceisgood 
    sent enceisgood 
     enceisgood: OUT1: the sent enceisgood, 2/3 
    sentence isgood 
      is good 
       go od: OUT2: the sentence is go od, 4/5 
      is good: OUT3: the sentence is good, 4/4 
    sentenceisgood: OUT4: the sentenceisgood, 1/2 
these ntenceisgood 
     ntenceisgood: OUT5: these ntenceisgood, 1/2 

तो तुम जवाब के रूप में OUT3 चुनेंगे।

Answer 2

वर्तनी सुधार एल्गोरिदम की जांच करें। Google - http://www.norvig.com/spell-correct.html में उपयोग किए गए एल्गोरिदम पर एक आलेख का एक लिंक यहां दिया गया है। यहां आपको a scientific paper on this topic from google मिलेगा।

Answer 3

यहां मैथमैटिका में एक कोड है जिसे मैंने हाल ही में कोड गोल्फ के लिए विकसित करना शुरू किया था।
यह एक न्यूनतम मिलान, गैर लालची, रिकर्सिव एल्गोरिदम है। इसका मतलब है कि वाक्य "कलम तलवार से अधिक mighter है" (रिक्तियों के बिना) देता है :)

findAll[s_] := 
    Module[{a = s, b = "", c, sy = "="}, 
    While[ 
    StringLength[a] != 0, 
    j = ""; 
    While[(c = findFirst[a]) == {} && StringLength[a] != 0, 
    j = j <> StringTake[a, 1]; 
    sy = "~"; 
    a = StringDrop[a, 1]; 
    ]; 
    b = b <> " " <> j ; 
    If[c != {}, 
    b = b <> " " <> c[[1]]; 
    a = StringDrop[a, StringLength[c[[1]]]]; 
    ]; 
    ]; 
    Return[{StringTrim[StringReplace[b, " " -> " "]], sy}]; 
] 

findFirst[s_] := 
    If[s != "" && (c = DictionaryLookup[s]) == {}, 
    findFirst[StringDrop[s, -1]], Return[c]]; 

नमूना इनपुट

ss = {"twodreamstop", 
     "onebackstop", 
     "butterfingers", 
     "dependentrelationship", 
     "payperiodmatchcode", 
     "labordistributioncodedesc", 
     "benefitcalcrulecodedesc", 
     "psaddresstype", 
     "ageconrolnoticeperiod", 
     "month05", 
     "as_benefits", 
     "fname"} 

आउटपुट { "कलम तलवार से अधिक हो सकता है एर है}

twodreamstop    = two dreams top 
onebackstop    = one backstop 
butterfingers    = butterfingers 
dependentrelationship  = dependent relationship 
payperiodmatchcode  = pay period match code 
labordistributioncodedesc ~ labor distribution coded es c 
benefitcalcrulecodedesc ~ benefit c a lc rule coded es c 
psaddresstype    ~ p sad dress type 
ageconrolnoticeperiod  ~ age con rol notice period 
month05     ~ month 05 
as_benefits    ~ as _ benefits 
fname      ~ f name 

HTH

Answer 4

निम्नलिखित नियमों के साथ एक स्टोकेस्टिक नियमित व्याकरण (छुपा मार्कोव मॉडल के बराबर) का प्रयास करें:

for every word in a dictionary: 
stream -> word_i stream with probability p_w 
word_i -> letter_i1 ...letter_in` with probability q_w (this is the spelling of word_i) 
stream -> letter stream with prob p (for any letter) 
stream -> epsilon with prob 1 

संभावनाओं प्रशिक्षण सेट से प्राप्त किया जा सकता है, लेकिन निम्नलिखित चर्चा देखें। विटरबी एल्गोरिदम का उपयोग करके सबसे अधिक संभावित पार्स की गणना की जाती है, जिसमें छिपे हुए राज्यों की संख्या में चौकोर समय जटिलता है, इस मामले में आपकी शब्दावली, ताकि आप बड़ी शब्दावली के साथ गति के मुद्दों में भाग सकें। लेकिन क्या होगा यदि आप सभी p_w = 1, q_w = 1 p = .5 सेट करते हैं, जिसका अर्थ है, ये कृत्रिम भाषा मॉडल में संभावनाएं हैं जहां सभी शब्द समान रूप से संभावित हैं और सभी गैर-शब्द समान रूप से असंभव हैं। बेशक अगर आप इस सरलीकरण का उपयोग नहीं करते हैं तो आप बेहतर सेगमेंट कर सकते हैं, लेकिन एल्गोरिदम जटिलता काफी कम हो जाती है। यदि आप wikipedia entry में पुनरावृत्ति संबंध देखते हैं तो आप इस विशेष मामले के लिए इसे आजमा सकते हैं और सरल बना सकते हैं।स्थिति के लिए viterbi parse संभावना VP(k) = max_l(VP(k-l) * (1 if text[k-l:k] is a word else .5^l) को सरलीकृत किया जा सकता है आप एक शब्द की अधिकतम लंबाई के साथ एल को बाध्य कर सकते हैं और यह पता लगा सकते हैं कि एक एल अक्ष एक हैश खोज के साथ एक शब्द बनाते हैं। इसकी जटिलता शब्दावली आकार से स्वतंत्र है और O(<text length> <max l>) है। क्षमा करें यह सबूत नहीं है, सिर्फ एक स्केच है लेकिन आपको जाना चाहिए। एक अन्य संभावित अनुकूलन, यदि आप शब्दकोश का एक तिहाई बनाते हैं, तो आप जांच सकते हैं कि कोई सबस्ट्रिंग किसी भी सही शब्द का उपसर्ग है या नहीं। तो जब आप पाठ [k-l: k] से पूछते हैं और नकारात्मक जवाब प्राप्त करते हैं, तो आप पहले से ही जानते हैं कि यह किसी भी डी के लिए पाठ [के-एल: के + डी] के लिए भी सच है। इसका लाभ उठाने के लिए आपको रिकर्सन को महत्वपूर्ण रूप से पुनर्व्यवस्थित करना होगा, इसलिए मुझे यकीन नहीं है कि इसका पूरी तरह से शोषण किया जा सकता है (यह टिप्पणी देख सकता है)।

Answer 5

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

यह अनिवार्य रूप से एक प्रशिक्षण सेट के दौरान जा रहा है और एम.आई. शब्द जोड़े के मान जो आपको बताते हैं कि अल्बर्ट सिम्पसन अल्बर्ट आइंस्टीन की तुलना में कम संभावना है :)

आप इस विषय में अकादमिक पत्रों के लिए विज्ञान डायरेक्ट खोजने का प्रयास कर सकते हैं। म्युचुअल सूचना के आधार पर बुनियादी जानकारी के लिए देखें http://en.wikipedia.org/wiki/Mutual_information

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