如何在Python中创建TRIE

Question

如何在Python中创建TRIE我是Python的新手并且正在努力学习和进步。我对TRIE和DAWG很感兴趣，我一直在阅读它，但我不明白输出TRIE或DAWG文件应该是什么样的。TRIE应该是嵌套字典的对象吗？每个字母被分成字母等等？如果有100k或500k条目，那么在这样的字典上查找是否会很快？如何实现由多个单词组成的字块 - 或用空格分隔？如何将单词的前缀或后缀链接到结构中的另一个部分？[对于DAWG]我想了解最佳输出结构，以便弄清楚如何创建和使用它。我也很感激DAWG和TRIE的输出应该是什么。我不希望看到彼此相关的气泡的图形表示，我在阅读时看到它们很多。一旦将一组单词转换为TRIE或DAWG，我想知道输出对象。谢谢。

Answer 1

以下是实现Trie的python包列表：

• marisa-trie - 基于C ++的实现。

• python-trie - 一个简单的纯python实现。

• PyTrie - 一个更高级的纯python实现。

• pygtrie - Google的纯python实现。

• datrie - 基于libdatrie的双数组trie实现。