在文件中写的字典中查找一系列字母的最快/最佳方法

Question

我有一系列字母，不一定是单词。我还有一个包含大约6000个字的文件。我必须确定字母顺序的任何重新安排是否构成文件中的单词。

做到这一点的最快/最佳方法是什么？如果我不能将整个文件加载到内存中怎么办？如果我可以怎么办？

我想到了一个o(n^2(的解决方案。当然，匹配单个单词的效果不会像单词数一样多。但是无论如何，它可以称为o(n^2(，不是吗？从文件中读取每一行，并检查给定的序列和行的长度是否相等。如果是，请计算每个字符的出现并匹配它们。

matched_words = []
with open('words.txt') as file:
for line in file:
    if len(line.strip()) == len(letters) and 
      Counter(line.strip()) == Counter(letters):
        matched_words.append(line.strip())
return matched_words

这有效，但是有更好的解决方案吗？

Answer 1

对于文件中的每个单词，您可以检查sorted(query)==sorted(word)。复杂性是o(nklogk(，其中n是单词的数量，k是单词的长度。
如果您需要查找多个查询，则可以进行一些预算以使其更快。您可以对文件中的每个单词进行排序，然后将它们加载到内存中，并测试设置成员资格。如果您需要找到给定字符序列的重新排列的实际单词，请加载到dict {sorted_form：}并查找每个查询中。
您还可以预先计算一系列分类的表单并将字典单词存储在Trie节点中。给定一个大小k的查询单词，对o(klogk(单词进行排序，然后在o(k(中查找trie，以使o(k^2*logk(

Answer 2

您的尝试在正确的轨道上。我们可以通过消除额外的工作来清理此操作。

from collections import Counter
def gen_matches(target, filepath):
    target_count = Counter(target)
    target_len = len(target)
    with open(filepath) as file:
        for line in file:
            word = line.strip()
            if len(word) == target_len and Counter(word) == target_count:
                yield word

您可以看到这些是最小的变化。我们可以一次在目标上调用Counter()和len()，并分配line.strip((的输出，以节省一些额外的努力。

这避免将整个文件加载到内存中。也是O(n(，假设我们的常数因子K(平均单词的长度(比单词数小得多。从计算机科学意义上讲，这比比较sorted(word)和sorted(target)更快。但是，实际上，比较分类单词的速度可能更快，因为Python的sorted()实现确实非常快。

您可能想尝试这两种方法！：(