Python：使用通配符快速查找词典单词*

Question

给定一个文本，它被分成单词列表，我想查找字典中每个单词，该字典也是从文本文件中读取并使用 split('\n') 分隔的。

与其检查每个单词是否包含在字典中（这非常缓慢），我需要根据通配符 '*'（位于末尾，即不需要 permuterm 解决方案）选择一组元素。例如，解决方案应选择以“dep”开头的所有字典元素，而无需遍历整个字典列表。

在这种情况下，性能至关重要。我想到了 B 树...但是：

1. 什么是Python中用于快速实现的最佳软件包和数据类型？
2. 请提供代码示例。

- Lorenz Lo Sauer

---

看起来你需要一些trie包。 - Voo

通配符一定会更慢。字典使用哈希表 (访问时间为常数时间)。 - JBernardo

@JBernardo：不，这只是意味着元素必须以“星号”之前的任何内容开头。 - Lorenz Lo Sauer

这就是为什么你会失去常数时间搜索的原因。也就是说，它会变得更慢。 - JBernardo

Answer 1

你需要一个trie。使用PyTrie包。

- Petr Viktorin

Answer 2

使用一个DAWG，在空间浪费方面比Trie更有效率。有一些Python实现，但是首先可以看一下这里。

- hymloth

---

从网站上："...如果你不在意内存或速度[sic!]，只需存储你的单词"... 这样会更快吗？ - Lorenz Lo Sauer

这个dawg肯定更快。网站上的引用是反讽的。“只需将您的单词存储在SQL数据库中，或在云中启动100台机器。我不介意。给你更多的能量！” - hymloth