优化单词生成器

Question

我正在尝试构建一个能够在拼字游戏中找到最佳单词的程序。在下面的代码中，我试图创建一个列表，其中包含给定一组 7 个字符的所有可能的单词。

import csv
import itertools

with open('dictionary.csv', newline='') as f:
    reader = csv.reader(f)
    data = list(reader)


def FindLegalWords(data):
    LegalWords = []
    for i in data:
        if len(i[0]) <= 15:
            LegalWords.append(i[0])
    return LegalWords


PossibleWords = []


def word_generator(chars, start_with, min_len, max_len):
    for i in range(min_len - 1, max_len):
        for s in itertools.product(chars, repeat=i):
            yield start_with + ''.join(s)


for word in word_generator('abcdefg', '', 2, 15):
    if word in FindLegalWords(data):
        PossibleWords.append(word)

我认为上述代码显然需要几天时间才能找到所有可能的单词。什么是解决问题的更好方法？就我个人而言，我想过让每个单词成为一个数字，然后使用 NumPy 来操作它们，因为我听说 NumPy 非常快。这会解决问题吗？或者这还不够？我很乐意回答有关我的代码的任何问题。

提前致谢

Answer 1

大约有 5_539 亿种可能性，使用字符串的代码通常非常慢（部分原因是 Unicode 和分配）。这是巨大的。生成大量数据来过滤其中的大部分数据效率不高。这个算法问题 无法使用像 Numpy 这样的优化库来解决。解决此问题的一种解决方案是直接生成仍然适合 FindLegalWords 的所有可能值的更小子集。我猜你可能不想生成像“bfddgfbgfgd”这样的词。因此，您可以通过连接 2 个可发音的单词部分来生成可发音的单词。虽然这样做有点棘手。更好的解决方案是 从现有词典中检索可能的单词 。你可以在网上找到这样的列表。还有一些可以从免费密码数据库中检索的可发音单词的字典。 AFAIK，像 John-the-Ripper 这样的工具可以生成这样的单词列表，您可以将其存储在文本文件中，然后从 Python 程序中读取它。请注意，由于列表可能很大，因此最好压缩文件并直接从压缩源中读取文件。

关于更新的一些说明：

因为 FindLegalWords(data) 是一个常量，您可以存储它，以免一遍又一遍地重新计算它。您甚至可以计算 set(FindLegalWords(data))，以便在结果中更快地搜索 word。尽管如此，可能性的数量是主要问题，所以它还不够。

PossibleWords 将包含 FindLegalWords(data) 中所有字符串的所有可能子集。因此，您可以直接从 data 生成它，而不是使用结合检查的蛮力方法。这应该快几个数量级是 data 很小。否则，主要问题将是 PossibleWords 太大，以至于您的 RAM 肯定不够大以容纳它...

优化单词生成器

Optimize Word Generator

python

optimization