trie 字典树

• storing strings in order to support fast pattern matching and prefix matching.
  

  Standard Tries

• A standard trie is an ordered tree T: define S be a set of s strings from alphabet Σ such that no string in S is a prefix of another string.
  • Each node of T , except the root, is labeled with a character of Σ.
  • The children of an internal node of T have distinct labels.
  • T has s leaves, each associated with a string of S
• A standard trie storing a collection S of s strings of total length n from an alphabet Σ:
  • The height of T is equal to the length of the longest string in S.

  • Every internal node of T has at most

    Σ

    children.

  • T has s leaves.
  • The number of nodes of T is at most n + 1
• There is a potential space inefficiency in the standard trie that has prompted the development of the compressed trie

Compressed Tries

• Let T be a standard trie. We say that an internal node v of T is redundant if v has one child and is not the root.
• Advantange over a standard trie: the number of nodes is proportional to the number of strings rather than their total
• A compressed trie storing a collection S of s strings from an alphabet of size d has the following properties:
  • Every internal node has at leaset two children and most d children
  • has s leaves nodes
  • number of nodes is O(s)
    

    Suffix Tries

• the strings in the collection S are all the suffixes of a string X
• The compact representation of a suffix trie T for a string X of length n uses O(n) space.
• efficiently perform pattern-matching queries on text X