Autocomplete algorithm research

Source: https://futurice.com/blog/data-structures-for-fast-autocomplete

A prefix tree is able to exploit “shared” prefixes in order to store the words more efficiently. For instance, the words are stored along paths rather than in individual nodes, which eliminates the need of storing “repeat” letters throughout the tree. (A word containing the letter “t” would not need to have that “t” repeated in every child node using this model).

Deterministic finite automata is a data structure that allows for further efficiency optimization by having as few nodes as possible. In this case, the end of words all share the suffix “ED” so relinking the other paths back to the same ending will negate the need for having “ED” as individual paths for each child.

A method that is used to sort through word lists to display the most commonly used words is by assigning each node/word an integer weight that quantifies its popularity and provides a number which can be used to determine its actual prevalence compared to other words.

Note that using a DFA data structure is made more complicated when paired with this implementation because the ends of certain word paths may be shared by multiple words. In this case, one would need to use a finite state transducer, which determines the numerical weight based on path instead of associating it with a particular leaf node.

Another idea is to have two separate tries: one that maintains a static, global library, and another personalized trie that is created for each individual user based on their vocabulary needs and habits. For instance, they could add new words to this trie and the words that are used frequently by them could be added as well. With this method, one could search the much smaller trie with faster speed and more efficiency.