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

Question

我正在做一个艺术项目，我想看看是否有任何信息从一长串字符(~28,000)中出现。这有点像解决 Jumble 时所面临的问题。这是一个片段:

jfifddcceaqaqbrcbdrstcaqaqbrcrisaxohvaefqiygjqotdimwczyiuzajrizbysuyuiathrevwdjxbinwajfgvlxvdpdckszkcyrlliqxsdpunnvmedjjjqrczrrmaaaipuzekpyqflmmymedvovsudctceccgexwndlgwaqregpqqfhgoesrsridfgnlhdwdbbwfmrrsmplmvhtmhdygmhgrjflfcdlolxdjzerqxubwepueywcamgtoifajiimqvychktrtsbabydqnmhcmjhddynrqkoaxeobzbltsuenewvjbstcooziubjpbldrslhmneirqlnpzdsxhyqvfxjcezoumpevmuwxeufdrrwhsmfirkwxfadceflmcmuccqerchkcwvvcbsxyxdownifaqrabyawevahiuxnvfbskivjbtylwjvzrnuxairpunskavvohwfblurcbpbrhapnoahhcqqwtqvmrxaxbpbnxgjmqiprsemraacqhhgjrwnwgcwcrghwvxmqxcqfpcdsrgfmwqvqntizmnvizeklvnngzhcoqgubqtsllvppnedpgtvyqcaicrajbmliasiayqeitcqtexcrtzacpxnbydkbnjpuofyfwuznkf

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

检查子字符串的有用字典是什么？有做这种事情的好图书馆吗？我四处搜索，发现了一些有趣的 TRIE 解决方案；但是他们中的大多数都是在处理你提前知道单词集的情况。

Answer 1

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

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