I am looking for a pure Python implementation of a Trie data structure that would not use nested data structures. Most implementations typically all use a Node that contains a dict of children Nodes nesting dict as deep as needed. This type of deeply nested structure very quickly hits Python recursion limit when you try to pickle it.

There are a many excellent Trie implementations in C/C++ using multiple arrays to store the Trie rather than nested structures, but I could not find one in pure Python.

Note that as a side note I need to associate a value with each "key" sequence added to the Trie and that in my case I need to store only sequence of integers rather than strings. And as a final bonus what I am looking for is to build an AhoCorasick automaton on top of the Trie.

License-wise, this needs to be open source and compatible with a BSD-license so it can be integrated in https://github.com/WojciechMula/pyahocorasick/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.