Tries
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
A "trie" is a data structure that converts "sentences" of symbols into a tree structure. In a trie all sequences ("n-grams") up to a certain length that appear in a "sentence" have as their parent "most" of that -gram, that is, all but the rightmost element of the original -gram. One also generally stores information on the number of times that a given -gram appears as the child of other -grams. Tries are useful for many purposes, including searching and finding "collocations", that is, -grams that appear more frequently than would occur randomly given their constituent parts.
[more]
Contributed by: Seth J. Chandler (March 2011)
Open content licensed under CC BY-NC-SA
Snapshots
Details
There is nothing particularly special about using a cellular automaton to generate the sentences or the use of a binary alphabet. The alphabet could be linguistic symbols or words and the stream of "text" could be words or true sentences.
Snapshot 1: where the sentences have lots of patterns that appear far more frequently than mere chance, the trie reflects this with fewer branches
Snapshot 2: a trie for rule 110
Snapshot 3: a trie for a cellular automaton with simple behavior
Permanent Citation