Reducing The Size Of A Trie Of All English Words

I am implementing an autocomplete feature using a Trie. Using the words list in this link, I am inserting every word into my Trie. I want to reduce the memory used by the Trie with

Solution 1:

If your trie is static, meaning that you do not need to insert words in it every now and then, but that you can build it "all at once", then the structure you need is a DAFSA, which stands for Directed Acyclic Finite State Automaton. In the case your trie is dynamic, meaning you will need to insert new words in it, the DAFSA is still the answer, but the algorithms are much harder.

This is basically a compressed version of a trie, it has the same access speed, but a much lower space requirement in the general case.

Algorithms to convert a trie into a DAFSA (sometimes called DAWG for Directed Acyclic Word Graph) are not as simple as the ones that simply build a trie, but they're understandable. You should find everything you need here.