Wie finden Sie mögliche englische Wörter in langen zufälligen String?

Question

Ich mache ein künstlerisches Projekt, bei dem ich herausfinden möchte, ob aus einer langen Zeichenkette (~ 28.000) irgendwelche Informationen hervorgehen. Es ist ein bisschen wie das Problem, mit dem man ein Jumble löst. Hier ist ein Ausschnitt:

jfifddcceaqaqbrcbdrstcaqaqbrcrisaxohvaefqiygjqotdimwczyiuzajrizbysuyuiathrevwdjxbinwajfgvlxvdpdckszkcyrlliqxsdpunnvmedjjjqrczrrmaaaipuzekpyqflmmymedvovsudctceccgexwndlgwaqregpqqfhgoesrsridfgnlhdwdbbwfmrrsmplmvhtmhdygmhgrjflfcdlolxdjzerqxubwepueywcamgtoifajiimqvychktrtsbabydqnmhcmjhddynrqkoaxeobzbltsuenewvjbstcooziubjpbldrslhmneirqlnpzdsxhyqvfxjcezoumpevmuwxeufdrrwhsmfirkwxfadceflmcmuccqerchkcwvvcbsxyxdownifaqrabyawevahiuxnvfbskivjbtylwjvzrnuxairpunskavvohwfblurcbpbrhapnoahhcqqwtqvmrxaxbpbnxgjmqiprsemraacqhhgjrwnwgcwcrghwvxmqxcqfpcdsrgfmwqvqntizmnvizeklvnngzhcoqgubqtsllvppnedpgtvyqcaicrajbmliasiayqeitcqtexcrtzacpxnbydkbnjpuofyfwuznkf

Was ist die effizienteste Art, nach allen möglichen englischen Wörtern zu suchen, die in diese Zeichenfolge eingebettet sind (sowohl vorwärts als auch rückwärts)?

Was ist ein nützliches Wörterbuch, um die Teilstrings zu überprüfen? Gibt es eine gute Bibliothek, um so etwas zu tun? Ich habe gesucht und einige interessante TRIE-Lösungen gefunden; aber die meisten von ihnen beschäftigen sich mit der Situation, in der Sie die Wörter im Voraus kennen.

Answer 1

habe ich diese Lösung alle Worte vorwärts und rückwärts aus einem Korpus von 28.000 zufälligen Zeichen in einem Wörterbuch von 100.000 Worten in 0,5 Sekunden zu finden. Es läuft in O (n) Zeit. Es nimmt eine Datei namens "words.txt", die ein Wörterbuch ist, das Wörter durch irgendeine Art von Leerzeichen getrennt hat. Ich benutzte die Standard-Unix-Wortliste in /usr/share/dict/words, aber ich bin sicher, dass Sie viele Textdateiwörterbücher online finden können, wenn nicht diese.

from random import choice 
import string 

dictionary = set(open('words.txt','r').read().lower().split()) 
max_len = max(map(len, dictionary)) #longest word in the set of words 

text = ''.join([choice(string.ascii_lowercase) for i in xrange(28000)]) 
text += '-'+text[::-1] #append the reverse of the text to itself 

words_found = set() #set of words found, starts empty 
for i in xrange(len(text)): #for each possible starting position in the corpus 
    chunk = text[i:i+max_len+1] #chunk that is the size of the longest word 
    for j in xrange(1,len(chunk)+1): #loop to check each possible subchunk 
     word = chunk[:j] #subchunk 
     if word in dictionary: #constant time hash lookup if it's in dictionary 
      words_found.add(word) #add to set of words 

print words_found 

Answer 2

Hier ist eine Bisektion/binäre Suche, die nützlich sein sollte.

def isaprefix(frag, wordlist, first, last): 
    """ 
    Recursive binary search of wordlist for words that start with frag. 

    assumes wordlist is a sorted list 
    typically called with first = 0 and last = len(wordlist) 

    first,last -->> integer 
    returns bool 
    """ 

    # base case - down to two elements 
    if (last - first) < 2: 
     # return False unless frag is a prefix 
     # of either of the two remaining words 
     return wordlist[first].startswith(frag) or wordlist[last].startswith(frag) 

    #mid = (first + last)/2 
    midword = wordlist[(first + last)/2] 

    # go ahead and return if you find one 
    # a second base case? 
    if midword.startswith(frag): 
     return True 

    #print word, ' - ', wordlist[mid], ' - ', wordlist[mid][:len(word)], ' - ', isprefix 
    # start the tests 
    # python does just fine comparing strings 
    if frag < midword: 
     # set the limits to the lower half 
     # of the previous range searched and recurse 
     return isaprefix(frag, wordlist, first, mid-1) 

    # frag is > midword: set the limits to the upper half 
    # of the previous range searched and recurse 
    return isaprefix(frag, wordlist, mid+1, last) 

Answer 3

Sie schafft eine Sequenz aus dem gesamten Wörterbuch denken können und Ausrichten ihnen dann die Worte in der Folge mit smith Wasser Mann oder einen heuristischen lokalen Alignment-Algorithmus