5 months, 2 weeks

Trie of all Suffixes


A trie, pronounced “try” and also called digital tree or prefix tree, is a special data structure used to store strings that can be visualized like a graph. Comes from the word retrieval. It consists of nodes and edges. Each node consists of at max 26 children and edges connect each parent node to its children.

For a trie data structure, we need to store extra data such as character link pointers and complete node flags. Therefore, the trie requires more memory to store the string data. However, if there are many common prefixes, the memory requirement becomes smaller as we can share the prefix nodes.

Although the hash table has a relatively faster lookup speed, it only supports the exact match of the whole string. The trie solution is more flexible to support more applications, such as auto-complete. Also, we can easily print all the words in the dictionary in alphabetic order with a trie.

Therefore, if we want a full-text lookup application, the hash table is better as it has a faster lookup speed. However, if we want to return all the words that match a prefix, the trie is our solution.

Tries: implementation

class TrieMap(object):                          
  """Trie implementation of a map. Associating keys (strings or other sequence type) with values.
Values can be any type. """                    
    def __init__(self,    kvs):                                                          
     self.root = {}                                                                            
         for (k,v) in kvs:                                                                    

    def add(self,k,v):                                                                       
    """    Add a key-value    pair """                                                 
        cur = self.root                                                                       
        for c in k:             # for each character in    the string                   
            if    c not in cur:                                                                
                cur[c]    = {}       # if not there, make new edge on character c
            cur    = cur[c]                                                                    
        cur['value'] = v            # at the end of the path, add    the value
     def query(self, k):                                                        
     """ Given    key, return associated value or    None """
         cur = self.root                                                          
         for c    in k:                                                                
             if    c not in cur:                                                    
                 return None                                                    
         return    cur.get('value')                                          

The complexity of creating a trie is O(W*L), where W is the number of words, and L is an average length of the word: you need to perform L lookups on the average for each of the W words in the set.


1. Auto Complete (Web Browser, Email,Search Engines( More advanced Levenshtein Algorithm),Source Code Editors,Database Query Tools,Word processors, Command Line interpreters)
2. Spell Checkers
3. Longest Prefix Matching
4. Browser History
5. Bioinformatics
6. Internet routing (Luleå algorithm)
("Compressed variants of tries, such as databases for managing Forwarding Information Base (FIB), are used in storing IP address prefixes within routers and bridges for prefix-based lookup to resolve mask-based operations in IP routing.")
7. Full-text search

Suffix Trie

Suffix trie is a space-efficient data structure to store a string that allows many kinds of queries to be answered quickly.By building Trie of all suffixes, we can find any substring in linear time. Every suffix is ending with string terminating symbol. From each node if there is any path, it moves forward, otherwise returns that pattern is not found.

For this algorithm, the time complexity is O(m+k), where the m is the length of string and k is the frequency of the pattern in the text.

Building a Trie of Suffixes                                                    
1) Generate all suffixes of given text.                                        
2) Consider all suffixes as individual words and build a trie.                          

Suffix Trie: implementation

class SuffixTrie(object):                                                                             
    def __init__(self, t):                                                                                
      """ Make suffix trie from t"""                                                                
         t += '$'         # special terminator symbol                                          
         self.root = {}                                                                                      
         for i in xrange(len(t)):                # for each suffix                             
             cur = self.root                                                                               
             for c in t[i:]:    # for each character in    i'th suffix                         
                 if c not in cur:                                                                         
                      cur[c] = {}  # add outgoing edge if necessary                 
                 cur = cur[c]                                                                          

    def followPath(self, s):                                                                      
    """  Follow path given by characters of s.Return node at end of path, or None if we  fall off."""
        cur = self.root                                                                                                                        
    for c in s:                                                                                                                                 
            if    c not in cur:                                                                                                               
        return None                                                                                                                        
            cur    = cur[c]                                                                                                                 
        return cur                                                                                                                            

    def hasSubstring(self, s):                                                                                                  
    """ Return    true iff s appears as a    substring of t"""                                                   
        return self.followPath(s) is not None                                                                        

    def hasSuffix(self,    s):                                                                                                
        """Return true    iff s is a suffix of t"""                                                                           
        node = self.followPath(s)                                                                                             

        return    node is not None and '$' in node