You can store a Trie or a DAFSA in a single chunk of memory and still have blazingly fast lookups - see double-array tries. The disadvantage is that inserting/r

You can store a Trie or a DAFSA in a single chunk of memory and still have blazingly fast lookups - see double-array tries. The disadvantage is that inserting/removing values is more costly, but DAFSA doesn't support it anyways. https://code.google.com/p/dawgdic/ https://code.google.com/p/dawgdic/ library works this way; I'm not sure, but it seems https://github.com/chalup/dawggenerator https://github.com/chalup/dawggenerator also works this way. For mutable tries there are HAT-Tries which are designed to be cache-friendly; see e.g. an implementation at https://github.com/dcjones/hat-trie https://github.com/dcjones/hat-trie and a Python wrapper at https://github.com/kmike/hat-trie https://github.com/kmike/hat-trie.