Mumbai University > Computer Engineering > Sem 4 > Analysis of Algorithm

Marks: 5 M

Year: Dec 2014

1. In computer science, a tries is also called digital tree and sometimes radix tree or prefix tree.
2. Tries is a tree based data structure for storing strings in order to support fast pattern matching.
3. Tries are used for information retrieval.
4. Tries is used to store the character in each node not the key.
5. Path from root to node is associated with key.
6. Tries uses character of a key to guide the search process.
7. All the descendants of the node have a common prefix of the string associated with that node.

Types:

I. Standard Tries:

The standard tries for a set of strings S is an ordered tree such that:

• Each node but the root is labeled with a character.
• The children of a node are alphabetically ordered
• The paths from the external nodes to the root yield the strings of S.
• Example: Standard tries for the set of strings S ={ bear, bell, bid, bull, buy, sell, stock, stop} is shown in figure 14.

II. Compressed Tries:

• Tries with nodes of degree at least 2.
• Obtained from standard tries by compressing chains of redundant nodes.

III. Suffix Tries:

• A suffix trie is a compressed trie for all the suffixes of a text.
• The suffix trie for a text X of size n from an alphabet of size d.
• Suffix tries stores all the n(n−1)/2 suffixes of X in O(n) space.
• Suffix tries supports arbitrary pattern matching and prefixes matching queries in O(dm) time, where m is the length of the pattern.
• Suffix tries can be constructed in O(dn) time
• Applications:
• Word matching.

• Prefix matching.

• Example: Minimize example is shown in figure 16.