Computer Algorithms II Lecture Notes

18 December 2007 • Tries

Outline

• Motivation

• Trie properties.

• Trie data structures.

• Trie implementations.

• Extension and details.

A Problem

• Store many (10⁵s or 10⁶s) long (1000s of characters) strings in a dictionary.

  • Ordered access may be required.

  • Subset access (prefix matching, for example).

  • More searches than insertions and deletions.

Solutions

• Ordered arrays.

  • Low overhead, O(log n) searches, other operations O(n).

• Binary Search trees.

  • Some overhead, O(log n) operations, subset and ordered access tricky.

• Hash tables.

  • Intermediate overhead, O(1) operations, subset and ordered access not possible.

• Can we do better" And in what sense?

Analysis

• Consider storing lots of Social Security Numbers (SSNs).

  • A nine-digit number: 123-45-6789.

• There's a billion SSNs.

  • But any one of them starts with a digit ‘0’ through ‘9’.

Digit Indexing

• Partition SSNs by first digit and index the partitions by digit.

  

• SSNs in a partition all have the same first digit.

  • Pull the same trick on the second digit.

  • And so on.

So What?

• D-digit numbers can be found (or not) with O(d) work.

  • Independent of the number of numbers stored.

• But n d-digit radix-r numbers use O(rdn) space.

N-ary Trees

• This data structure is an ordered r-way (or r-ary) tree.

• But it's not a search tree.

  • Interior nodes don't store a key, just a digit from the key.

Tries

• A digit-indexed r-ary tree is a trie.

  • Pronounced “try,” derived from “information retrieval”.

  • Interior trie nodes are called branch nodes.

  • Leaf trie nodes are called information (or data) nodes.

Trie Search

• Searching trie node n at level (i):

  • N is a data node: compare the data to the key.

  • N is a branch node:

    • If n.children[key[i]] is nil, fail.

    • Otherwise recurse on n.children[key[i]].

Find'

(node, node, int) 
find'(parent, root, key, dno)

  if root = nil
    return (parent, root, dno)

  if root isa data-node
    return (parent, 
            root.data = key ? root : nil, 
            dno)

  return find'(root, 
               root.children[key[dno]], 
               key, 
               dno + 1)

Find

• find() is easy using find'():

  bool find(root, key)
  
    (_, root, _) = 
      find'(nil, root, key, 0)
  
    return root = nil
  

Trie Insertion

• Look for the key.

  • If found, done.

  • Otherwise, insert the new key as a child.

Insert

insert(root, key)

  (parent, root, dno) = 
    find'(nil, root, key, 0)

  if root = nil
    parent.children[key[dno]] = 
      new data-node(key)

Trie Deletion

• Look for the key.

  • If not found, done.

  • If found, nil the child's entry in the parent.

  • If the parent's empty, recurse to the grandparent and repeat.

Delete

delete(root, key)

  (parent, root, dno) =
    find'(nil, root, key, 0)

  if root ≠ nil
    while root.parent ≠ nil
      parent = root.parent
      free root
      parent.children[key[--dno]] = nil
      if parent.child_count() ≠ 0, break
      root = parent

Other Operations

• Ordered traversals:

  • As with binary trees, use an *-order traversal, or threading.

• Range finding:

  • As with binary trees, search for the range endpoints and do an ordered traversal between them.

  • Special case: prefix matching.

    • Search for the prefix, take all ancestor data nodes.

Some Refinements

• Tries as described can be improved in a few ways.

  • Allow variable-length keys.

  • Use less space, without using too much time.

Variable-Length Keys

• With variable lenght keys, a shorter key may be a prefix of a longer key.

  123-45-6789
  1234

• Prefix keys require that branch nodes also be data nodes.

Explicit Ends

• Add a new end digit to the key's digit set.

• Add the end digit to each key before accessing the trie.

  123-45-6789$
  1234$

  • Explicitly ended shorter keys can't be prefixes.

• Explicitly-ended tries are (r + 1)-ary trees.

Branch-Data Nodes

• Let branch nodes also represent data nodes.

  • Add a key field to branch nodes.

• Key searches ending at branch nodes check the key field.

  (node, node, int) 
  find'(parent, root, key, dno)
  
    if root = nil
      return (parent, root, dno)
  
    if root isa data-node
      return (parent, 
              root.data = key ? root : nil, 
              dno)
  
    if root.key = key
      return (parent, root, dno)
  
    return find'(root, 
                 root.children[key[dno]], 
                 key, 
                 dno + 1)

Some Refinements

• Tries as described can be improved in a few ways.

  • Allow variable-length keys.

  • Use less space, without using too much time.

Space Efficient Branch Nodes

• Large-radix branch nodes tend to be space inefficient.

  • At higher levels, many of the entries may be nil.

  • However, digit search is constant time.

• All the usual space-saving tricks can be brought to bear on the child array.

  • At possible access-time costs.

Child Linked Lists

• Sparse child arrays can be represented by a singly-linked list.

  

• This saves space if the array's empty space is greater than the total link-node overhead.

• This costs access time, O(r) in the worst case.

  • Sparse linked-list access is quasi-constant.

Child BSTs

• For branch nodes with lots of children, folding the child linked list into a binary search tree will reduce access time.

  • At a cost of increasing space overhead.

• This makes sense for branch nodes with lots of children and lots of empty space.

  • That is, for keys with large-radix digits.

Explicit Child Links

• Roughly speaking, there are more unused child links in a trie than there are used links.

  • Higher-level branch nodes have fewer children than do lower-level branch nodes.

  • There are exponentially more higher-level branch nodes than there are lower-level branch nodes.

• Explicitly represent child links and don't represent empty links at all.

  (branch-node ref, key digit, child-node ref)

  • This is similar to the singly linked list representation.

Child Link Hashing

• Child-link triples are stored in a hash table.

  • The (branch-node ref, key digit) pair is the key for a triple.

• The triple and hash-table space overhead is spread over all empty links in the trie.

• Node access is constant time for a reasonable hash-table implementation.

  • Deleting unneeded branch nodes is expensive (O(r)).

No-Information Nodes

• Notice anything?

  

• Branch nodes with only one child provide no useful information.

  • All keys in the associated partition have the same digit.

• One-child branch nodes can be removed from the trie to save some space.

• A compressed trie has no one-child branch nodes.

Compressed Tries

• Key-digit indices are no longer related to level in compressed tries.

• Each branch node has to maintain the index explicitly.

  

• Trie operators are more complicated for compressed tries.

Binary Tries

• A binary trie is a trie with radix-2 keys, that is: binary numbers.

  

• Not surprisingly, binary tries compress well.

  

References

• Tries by Sartaj Sahni, Chapter 28 in Handbook of Data Structures and Algorithms, edited by Dinesh Metha and Sartaj Sahni, Chapman & Hall/CRC, 2005.

• Digital Searching, Section 6.3 in The Art of Computer Programming, Vol. 3: Sorting and Searching by Donald Knuth, Addison-Wesley, 1973.