在 Python 中有什么方法可以找到用户输入的混乱单词存在给定列表而没有排列代码以使其更快？

Question

假设我有 300k+ 项的独特列表：

mylist = ["door", "mango", "rose", "orange", "car", "knowledge", "flower", ...., 300k+ items]

userinput = input()

现在，如果用户输入 "knowledge" 的乱码。例如。 "dngwekleo"，程序应该检查 mylist 中的输入单词并打印 "knowledge" 作为输出。

我的代码在输入单词的长度为 7 之前工作正常，我使用排列代码进行输入，然后匹配排列 == mylist 中的每个单词。但是一旦输入单词的输入长度超过 8-10，它就会产生太多的排列，然后 python 需要太多时间（10 分钟、20 分钟、30 分钟）才能得到输出。

请帮助我解决这个问题，以便在 10-15 秒内更快地得到答案，尝试了 20 天。

Answer 1

您可以计算原始列表和输入中每个单词的字母。如果计数匹配，则一个词是另一个词的排列。

from collections import Counter
# Pre-calculate the dictionaries
counts = [Counter(word) for word in mylist]

userinput = input()
count = Counter(userinput)
if count in counts:
    # Found it!

对于大型列表，您可以通过为每个单词计算一组冻结的字母计数对来减少查找时间：

counts = {frozenset(Counter(word).items()) for word in mylist}
count = frozenset(Counter(userinput).items())
if count in counts: ...

Answer 2

为了快速启动，您可以通过创建一个查找来实现，其中键按字符排序并保留原始字符串的值。
例如：{deegklnow : knowledge}

my_list = ["door", "mango", "rose", "orange", "car", "knowledge", "flower"]

lookup = {"".join(sorted(x)): x for x in my_list}

print(lookup.get("".join(sorted("dngwekleo"))))
print(lookup.get("".join(sorted("eosr"))))
print(lookup.get("".join(sorted("rca"))))

knowledge
rose
car

Answer 3

编辑想了想，我觉得DYZ的回答可能会更快。

注意：我假设对输入词集进行一些预计算是可以接受的，只有在那之后的查找时间才是真正重要的。

扩展 DYZ 的想法：

计算每个字母出现的次数
使用该计数更新哈希值
对列表中的每个输入词执行此操作以获得键为：哈希，值：词（或词列表，例如 "cart" 和 "trac" 会导致相同的结果字符数）
然后对用户输入进行哈希处理并在字典中进行查找

哈希函数的示例实现：

import hashlib
import string

def get_char_count_hash(input_string):
    char_count_hash = hashlib.sha256()

    for char in string.ascii_lowercase:
        char_count = input_string.count(char)
        char_count_hash.update(str(char_count))

    return char_count_hash.hexdigest()

注意：您可以通过稍微优化哈希函数来减少预计算时间。

在 Python 中有什么方法可以找到用户输入的混乱单词存在给定列表而没有排列代码以使其更快？

Is there any way in Python where we can find jumbled word entered by user exists given list without permutations code to make it faster?

python

python-3.x

list

permutation

scramble