tree占用太多内存

Question

我正试图从一个名为web2.txt的文件中获取所有由字母'crbtfopkgevyqdzsh'组成的单词。下面发布的单元格后面是一段代码，它不正确地将整个运行返回到一个完整的单词，例如，对于单词，它将返回s,sh,商店战略卫生行动中心,震惊,,shocke,

所以我试了一个trie(知道双关语)。

web2.txt大小为2.5 MB，包含2,493,838个不同长度的单词。下面单元格里的树弄坏了我的Google Colab笔记本。我甚至升级到Google Colab Pro，然后又升级到Google Colab Pro+，试图适应代码块，但它仍然太多了。除了尝试得到相同的结果之外，还有什么更有效的想法吗?

# Find the words3 word list here:  svnweb.freebsd.org/base/head/share/dict/web2?view=co
trie = {}
with open('/content/web2.txt') as words3:

for word in words3:
cur = trie
for l in word:
cur  = cur.setdefault(l, {})
cur['word'] = True # defined if this node indicates a complete word

def findWords(word, trie = trie, cur = '', words3 = []):
for i, letter in enumerate(word):
if letter in trie:
if 'word' in trie[letter]:
words3.append(cur)
findWords(word, trie[letter], cur+letter, words3 )    
# first example: findWords(word[:i] + word[i+1:], trie[letter], cur+letter, word_list )
return [word for word in words3 if word in words3]
words3 = findWords("crbtfopkgevyqdzsh")

我使用python3

Answer 1

一个trie是多余的。大约有20万个单词，所以你可以对所有单词进行一次遍历，看看是否可以使用基本字符串中的字母组成单词。

这是collections.Counter的一个很好的用例，它为我们提供了一种获取任意字符串中字母的频率(即"counter ")的干净方法:

from collections import Counter
base_counter = Counter("crbtfopkgevyqdzsh")
with open("data.txt") as input_file:
for line in input_file:
line = line.rstrip()
line_counter = Counter(line.lower())
# Can use <= instead if on Python 3.10
if line_counter & base_counter == line_counter:
print(line)