一个简单的解决方案是将单词存储在字典中（因为您必须将它们存储在某些数据结构中），其关键是字符分布；例如，Counter("hello") = {h: 1, e: 1, l: 2, o: 1}。查询字典会给你字谜。

对于存储不可变键（字符分布），可以使用元组列表，进行排序，或者您可以使用字母长度的向量（26）。因此，您可以在准备阶段进行速度-空间权衡；查找是常数时间，不计算计算查询词的字符分布所花费的时间。如果您采用后者，固定宽度的路线，您可以通过散列密钥进行另一个权衡，因为您知道输入的基数（唯一词的数量）。

这很好玩！这是 Emre 的想法在 Python 中的实现。我尽量避免循环以使代码更快。

首先，一些导入和常量。

from collections import Counter
import urllib.request

ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
LEN_ALPHABET = len(ALPHABET)

1. 下载完整的英文单词列表。（我避免将其称为“字典”以避免与同名的 Python 类型混淆）。我在这里找到了一个。删除所有包含非字母字符的单词（包括连字符......可能不是最佳的）。

response = urllib.request.urlopen('http://www-personal.umich.edu/~jlawler/wordlist')
words = str(response.read()).replace('\\r', '').split('\\n')
words = {w for w in words if set(w).issubset(set(ALPHABET))}

2. 创建哈希函数。 将给定单词映射到长度为的元组LEN_ALPHABET。第一项是 的字符数a，第二项是 的字符数，b依此类推。例如，单词 'agaze' 被散列到元组(2, 0, 0, 0, 1, 0, 1, 0, ...0, 0, 1)中。

char_to_int = {c: i for i, c in enumerate(ALPHABET)}

def hasher(w):
    w = [char_to_int[c] for c in w]
    count = Counter(w)
    return tuple(count[i] for i in range(LEN_ALPHABET))

3. 创建散列词词典。字典将每个元组映射到一组相应的单词。

h_words = {}
for w in words:
    h_words.setdefault(hasher(w), set()).add(w)

4. 查找字谜。最后，一个包装函数使查找更方便。

def get_anagrams(w):
    return h_words.setdefault(hasher(w), set())

一个小测试：

print(get_anagrams('olleh'))

这将{'hello'}根据需要返回。

哦，一定要执行这个：

print('The largest set of anagrams in the English language is:', max(h_words.values(), key=len))

@Emre 的回应和 @elias-strehle 的实现是正确的。我使用从这条推文中借来的优雅（恕我直言）散列函数进行了类似的实现

该类将每个单词散列为其所有字母的乘积，其中每个字母都映射到一个素数。素数的乘积只有在使用完全相同的数字时才会发生碰撞。

它非常快（根据要求），每秒大约 200k 字谜查找（在我的机器上）

有关完整示例，请参见此处

class Anagrammer:

    alphabet = {"a":2,"b":3,"c":5,"d":7,"e":11,"f":13,"g":17,"h":19,"i":23,"j":29,"k":31,"l":37,"m":41,"n":43,"o":47,"p":53,"q":59,"r":61,"s":67,"t":71,"u":73,"v":79,"w":83,"x":89,"y":97,"z":101}

    def __init__(self, corpus):
        self.index = {}
        self.createIndex(corpus)

    def createAnagramIndexNumber(self, word):
        index = 1
        for x in list(word):
            index *= self.alphabet[x]
        return index

    def createIndex(self, corpus):
        for word in corpus:
            self.index.setdefault(self.createAnagramIndexNumber(word),set())
            self.index[self.createAnagramIndexNumber(word)].add(word);

    def getAnagrams(self, word):
        return self.index[self.createAnagramIndex(word)]

我认为，根本没有外部软件包很难找到解决方案。在内部，您可以创建一个索引，可用于高效搜索，但我不记得任何具有非唯一索引搜索的“纯 Python/R”数据结构。字典不适合，因为所有字谜都有相同的键，这对于 dict 是不可能的。在 Python 和 R 中都没有原生的二叉树搜索实现。

这是我会使用的可能解决方案的草图。让我们创建十进制哈希来确定字母，一个单词由（Python）组成：

def word2hash(word):
    alphabet = list(map(chr, range(ord('a'), ord('z')+1)))
    hashed_word = {k: 0 for k in alphabet}
    for letter in set(word.lower()):
        hashed_word[letter] = 1
    hashed_word = sorted(hashed_word.items(), key=lambda x: alphabet.index(x[0]))
    hashed_word = ''.join([str(x[1]) for x in hashed_word])
    return int(hashed_word, 2)

此函数将根据字母生成十进制哈希。此哈希可用于高效的二叉树搜索 (BTS)。但碰撞是它没有考虑双字母。例如，'hello' 和 'ooohell' 的输出都是相同的：2377728。无论如何，过滤掉字典的大部分内容既快速又健壮。基于此索引，有几种实现高效搜索的选项：

• SQL 数据库：开箱即用支持非唯一索引，但您需要一个 SQL 接口库（python-mysqldb / RMySQL /etc）。对我来说，这是最好的选择。只需将带有预先计算的十进制索引的字典放入数据库中，然后尽可能多地查询它；
• 任何带有 BTS 的 Python/R 包：（例如data.tree）；
• 无需外部依赖即可自行实现 BTS。

对于第二步，让我们使用更精确的元组哈希。它不像前一个那么简单，但它的输入要小得多：

def word2letterset(word):
    alphabet = list(map(chr, range(ord('a'), ord('z')+1)))
    letterset = {}
    for letter in list(word):
        try:
            letterset[letter] += 1
        except KeyError:
            letterset[letter] = 1
    return tuple(letterset.items())

这一步可以用“蛮力”在纯 Python/R 中完全实现：计算输入“单词”的元组哈希，并将其与上一步中找到的所有单词的计算哈希进行比较。