如何在长随机字符串中找到可能的英语单词？

Question

我正在做一个艺术项目,我想看看是否有任何信息来自一长串字符(~28,000).这有点像解决混杂问题时面临的问题.这是一个片段:

jfifddcceaqaqbrcbdrstcaqaqbrcrisaxohvaefqiygjqotdimwczyiuzajrizbysuyuiathrevwdjxbinwajfgvlxvdpdckszkcyrlliqxsdpunnvmedjjjqrczrrmaaaipuzekpyqflmmymedvovsudctceccgexwndlgwaqregpqqfhgoesrsridfgnlhdwdbbwfmrrsmplmvhtmhdygmhgrjflfcdlolxdjzerqxubwepueywcamgtoifajiimqvychktrtsbabydqnmhcmjhddynrqkoaxeobzbltsuenewvjbstcooziubjpbldrslhmneirqlnpzdsxhyqvfxjcezoumpevmuwxeufdrrwhsmfirkwxfadceflmcmuccqerchkcwvvcbsxyxdownifaqrabyawevahiuxnvfbskivjbtylwjvzrnuxairpunskavvohwfblurcbpbrhapnoahhcqqwtqvmrxaxbpbnxgjmqiprsemraacqhhgjrwnwgcwcrghwvxmqxcqfpcdsrgfmwqvqntizmnvizeklvnngzhcoqgubqtsllvppnedpgtvyqcaicrajbmliasiayqeitcqtexcrtzacpxnbydkbnjpuofyfwuznkf

在这个字符串中搜索嵌入(向前和向后)所有可能的英语单词的最有效方法是什么？

什么是有用的字典来检查子字符串？做这种事情有没有一个好的图书馆？我四处搜寻,发现了一些有趣的TRIE解决方案; 但是他们中的大多数都在处理你事先知道一组单词的情况.

Answer 1

我使用这个解决方案,在一个包含100,000字的字典中,在.5秒内,从28,000个随机字符的语料库中找到所有单词前后.它在O(n)时间内运行.它需要一个名为"words.txt"的文件,这是一个字典,其中的单词由某种空格分隔.我使用了默认的unix wordlist,/usr/share/dict/words但我相信你可以在网上找到大量的文本文件词典,如果不是那样的话.

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