Interesting stuff.  The article is quite verbose -- here is the Cliff Notes versions:<p>The trie is a well-known data structure for storing string sets or string-keyed maps (<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Trie" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Trie</a>).  You can compress a trie by using a DAG&#x2F;FSM instead of a tree -- this lets you share states for suffixes, whereas trees only let you share states for prefixes.  But for large sets minimizing a DAG is too expensive to perform on the whole trie.  If you insert the keys in-order, you can minimize the DAG on-the-fly much more cheaply.<p>If you have a map instead of a set, the DAG is called a FST (finite state tranducer) instead of a finite state acceptor.  In this case every edge has some value that you accumulate into the final result.  For example, if the map values are integers, each edge can be an integer that is added to the final result.  It takes a bit more cleverness in the algorithm to share prefix&#x2F;suffix states while maintaining the tranducer invariants.