python：快速使用通配符的字典单词查找*

Question

给定一段文本，这段文本被分成一个个单词，我想在一个字典中查找这些单词，这个字典也是从一个文本文件中读取并用split('\n')分开的。

与其一个个检查每个单词是否在字典里（这样做非常慢），我需要根据通配符来选择元素*（' * '是在末尾，也就是说不需要复杂的排列组合）。比如，解决方案应该选择所有以'dep'开头的字典元素，而不需要遍历整个字典列表。

在这种情况下，性能非常重要。我考虑过使用B树……但是

1. 在Python中，哪个包和数据类型最适合快速实现。
2. 请提供代码示例。

Answer 1

你需要一个字典树（trie）。可以使用PyTrie这个包。

Answer 2

使用一种叫做 dawg 的数据结构，它在节省空间方面比Trie更有效。虽然有一些Python的实现，但如果你刚开始，可以先看看 这里。