Trie

3 Key excerpts on "Trie"

• 

  eBook - PDF

  Analytic Pattern Matching

  From DNA to Twitter

  • Philippe Jacquet, Wojciech Szpankowski(Authors)
  • 2015(Publication Date)
  • Cambridge University Press

    (Publisher)

  Tries are prototype data structures useful for many indexing and reTrieval purposes. We described their construction in detail in Chapter 6, so here we only 156 Chapter 7. Digital Trees briefly review some facts. Tries were first proposed by de la Briandais (1959) for information processing. Fredkin (1960) suggested the current name, part of the word reTrie val. Tries are trees whose nodes are vectors of characters or digits; they are a natural choice of data structure when the input records involve the notion of alphabets or digits. Given a sequence of n words over the alphabet A = {a 1 ,...,a |A| }, |A|≥ 2, we construct a Trie as follows. If n = 0 then the Trie is empty. If n = 1 then a single external node holding the word is allocated. If n ≥ 1 then the Trie consists of a root (i.e., internal) node directing words to |A| subtrees according to the first symbol of each word, and words directed to the same subtree are themselves Tries. The internal nodes in Tries are branching nodes, used merely to direct records to each subTrie; the record strings are all stored in external nodes, which are leaves of such Tries. In Figure 6.1 a binary Trie built over five records is shown. Digital search trees were discussed in Section 6.4. In a digital search tree (DST) record strings are directly stored in nodes. For a binary alphabet A = {0, 1}, the root contains the first string (or an empty string) and the next string occupies the right or the left child of the root depending on whether its first symbol is 0 or 1. The remaining strings are stored in nodes which are directly attached to already existing nodes in the tree. The search for an available node follows the prefix structure of a new string. Sometimes external nodes are added to such constructed trees, as was shown in Figure 6.8. These external nodes are positions where the next inserted string may end up.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  A Textbook of Data Structures and Algorithms, Volume 2

  Mastering Nonlinear Data Structures

  • G. A. Vijayalakshmi Pai(Author)
  • 2022(Publication Date)
  • Wiley-ISTE

    (Publisher)

  Search trees in general favor keys which are of fixed size, since this leads to efficient storage management. However, in the case of applications which are reTrieval-based and which call for keys of varying length, Tries provide better options. Search trees indulge in multi-way branching based on the whole key and hence searching is done based on key comparisons. In contrast, though Tries are also multi-way branched trees, searching is based only on a portion of a key and not on the whole, before it is completely reTrieved or stored.

  Tries are also called lexicographic search trees. The name Trie (pronounced “try”) originated from the word “reTrieval”.

  11.4.1. Definition and representation

  A Trie of order m may be empty. If non-empty, then it consists of an ordered sequence of exactly m Tries of order m. The branching at any level of the Trie is determined only by a portion and not by the whole key.

  Alphabetical keys require a Trie of order 27 (26 letters of the alphabet + a blank (“ ”)) for their storage and reTrieval. Each branch of the Trie partitions the keys into groups beginning with the specific alphabet.

  Thus, Tries have two categories of node structures, that is, branch node and information node. A branch node is merely a collection of LINK fields, each pointing either to a branch node or to an information node. An information node holds the key that is to be stored in the Trie. For example, in the case of alphabetical keys, each branch node has 27 LINK fields, one for each of the 26 alphabet characters and one for a blank (“ ”). The keys are stored in the information nodes. To access an information node containing a key, we need to move down a branch node or a series of branch nodes following the appropriate branch based on the alphabetical characters composing the key. All LINK fields that neither point to a branch node nor to an information node are represented using null pointers. To avoid clutter, null pointers have not been represented using any special notations.

  Figure 11.18.

  An example Trie

  Figure 11.18 illustrates an example Trie for alphabetical keys. The Trie stores the keys CAR, CARRIAGE, CARAVAN, BIKE, BUS, TRAIN, BICYCLE and AEROPLANE. The information nodes wholly store the keys. To access these information nodes, we follow a path beginning from a branch node moving down each level depending on the characters forming the key, until the appropriate information node holding the key is reached. Thus the depth of an information node in a Trie depends on the similarity of its first few characters (prefix

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Advanced Algorithms and Data Structures

  • Marcello La Rocca(Author)
  • 2021(Publication Date)
  • Manning

    (Publisher)

  Tries were originally developed as a compact, efficient way to search strings in files; the idea behind this data structure is, as we saw in the previous section, providing a way to reduce redundancy by storing common prefixes of strings just once.

  This couldn’t be achieved using a plain binary search tree, or with just a binary tree, so a paradigm shift was needed: de la Briandais then used n -ary trees, where edges are marked with all the characters in an alphabet, and nodes just connect paths.

  Nodes also have a small but crucial function: they store a tiny bit of information stating if the path from root to current node corresponds to a key stored in the Trie.

  Let’s take a look at figure 6.2 before moving to a more formal description. It shows the structure of a typical Trie, containing the words “a” , “an” , “at”, and “I” .

  Figure 6.2 The structure of a Trie. Words are encoded in the tree using edges, each edge corresponds to a single character, and each node n is associated with a single word, the one obtained by joining the characters associated with the edges in the path from the root to n . The root node corresponds to the empty string (because no edge is traversed), the leftmost leaf corresponds to “aa” , and so on. Not all the paths make meaningful words, and not all the nodes store the word associated with them. Only filled, black nodes (called “key nodes”) mark words stored in the Trie, while hollow nodes, aka “intermediate nodes,” correspond to prefixes of words stored in the Trie. Notice that all leaves should be key nodes.

  If you feel that figure 6.2 is a bit confusing, you are right. In their classic implementation, a Trie’s nodes have one edge for each possible character in the alphabet used: some of these edges point to other nodes, but most of them (especially in the lower levels of the tree) are null references.9

  Sign up to read

  Learn more about book