Trie

The concept of a trie was introduced by A. Thue in 1912 as a means to represent a set of strings (see Knuth, 1998).

In its simplest form, a trie is a multiway branching tree where each edge is labelled with a character.

For example, the set of strings {ear, earl, east, easy, eye} is represented by the trie depicted in figure 1.

Searching in a trie starts at the root and proceeds by traversing the edge that matches the first character, then traversing the edge that matches the second character, and so forth.

The search key is a member of the represented set if the search stops in a node that is marked – marked nodes are drawn as filled circles in figure 1.

Tries can also be used to represent finite Maps [⇒ Map Dialect ]. In this case marked nodes additionally contain values associated with the strings. Interestingly, the move from sets to finite maps is not a mere variation of the scheme. As we shall see it is essential for the further development.

On a more abstract level, a trie itself can be seen as a composition of finite maps. Each collection of edges descending from the same node constitutes a finite map sending a character to a trie. With this interpretation in mind, it is relatively straightforward to devise an implementation of string-indexed tries. For concreteness, programs will be given in the functional programming language Haskell 98 (Peyton Jones and Hughes, 1999).

HINZE, Ralf, 2000. Generalizing generalized tries. Journal of Functional Programming. Online. July 2000. Vol. 10, no. 4, p. 327–351. [Accessed 6 September 2023]. DOI 10.1017/S0956796800003713. A trie is a search tree scheme that employs the structure of search keys to organize information. Tries were originally devised as a means to represent a collection of records indexed by strings over a fixed alphabet. Based on work by C. P. Wadsworth and others, R. H. Connelly and F. L. Morris generalized the concept to permit indexing by elements built according to an arbitrary signature. Here we go one step further, and define tries and operations on tries generically for arbitrary datatypes of first-order kind, including parameterized and nested datatypes. The derivation employs techniques recently developed in the context of polytypic programming and can be regarded as a comprehensive case study in this new programming paradigm. It is well known that for the implementation of generalized tries, nested datatypes and polymorphic recursion are needed. Implementing tries for first-order kinded datatypes places even greater demands on the type system: it requires rank-2 type signatures and second-order nested datatypes. Despite these requirements, the definition of tries is surprisingly simple, which is mostly due to the framework of polytypic programming.

⇒ Tries ⇒ Sequence ⇒ Digital Searching

KNUTH, Donald Ervin, 1997. The art of computer programming. v. 2. Seminumerical Algorithms. 3rd ed. Reading, Mass: Addison-Wesley. ISBN  0-201-89684-2, p. 687.

[…] if we encode each qi(x) by a Sequence of 0s and 1s according as qi(x) does or doesn’t divide t(x)(pd−1)/2 − 1 for the successive t’s tried, we obtain a random binary trie with r lieves (see Section 6.3).

Note: Section 6.3 is Digital Searching.