algo.trie: trie collection class¶
Trie is a data structure for effective prefix search. It is used in Spylls to store prefixes and suffixes. For example, if we have suffixes “s”, “ions”, “ications”, they are stored (reversed) this way:
root +-s ... metadata for suffix "s" +-noi ... metadata for suffix "ions" +-taci ... metadata for suffix "ications"
So, for the word “complications”, we can receive all its possible suffixes (all three) in one pass through trie.
Important: Profiling shows that search through Trie of suffixes/prefixes is the center of Spylls performance, that’s why it is very primitive and fast implementation instead of some library like pygtrie. Probably, by choosing fast (C) implementation of trie, the whole spylls can be make much faster.