यादृच्छिक स्ट्रिंग में अंग्रेजी शब्दों की गणना

Question

मान लीजिए कि मेरे पास यादृच्छिक रूप से जेनरेट की गई स्ट्रिंग s=t&^%JHGgfdteam*&HGEdfg है, उस स्ट्रिंग में अंग्रेज़ी शब्दों की संख्या को गिनने का सबसे अच्छा तरीका क्या है? (कुछ शब्दकोष फ़ाइल में परिभाषित अंग्रेजी शब्द)। स्पष्ट रूप से क्रूर बल एक अच्छा विचार नहीं है ... एक प्रत्यय-त्रि ई काम होगा? द्विआधारी खोज? ध्यान दें कि s के मामले में, दो शब्द हैं: "चाय" और "टीम"। कोई विचार? सम्मान

Answer 1

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

छद्म कोड में:

Trie dict = ... // load dictionary 
Dictionary occurences = {} 

for i in length(string): 
    j = i + 1 
    # think of partial as string.Substring(i, j); 
    while dict.hasChildren(partial): 
     j++ 
     if isWord(partial): 
      dict[partial]++ 

इस तरह से आप की गारंटी देंगे यह एक मैच याद नहीं करता है, जबकि अभी भी सभी संभावनाओं की तलाश में।

आप बदल रहा है क्या j करने के लिए या isWord() विधि में कम शब्दों का त्याग करके आरंभ नहीं हो जाता द्वारा मान्य शब्दों का न्यूनतम लंबाई सीमित कर सकते हैं (ताकि a एक "वैध" शब्द नहीं होगा)।

Answer 2

Aho-Corasick string matching algorithm इनपुट टेक्स्ट के आकार में समय रैखिक में शब्दकोश और मिलान पैटर्न के आकार में समय रैखिक में मिलान संरचना बनाता है + मिले मैचों की संख्या।