attachment:trie.py von GaGa2En

   1 #!/usr/bin/env python
   2 """ (slightly modified) Trie data structure"""
   3 
   4 class TrieError(Exception):
   5     pass
   6 
   7 class Trie:
   8     """Trie data structure"""
   9 
  10     def __init__(self):
  11         self.children = None
  12         self.final = 0
  13 
  14     def add(self, str):
  15         """Adds string to the trie"""
  16         if len(str):
  17             key = str[0]
  18 	    if not self.children:
  19 	        self.children = {}
  20             if not key in self.children.keys():
  21                 self.children[key] = Trie()
  22             self.children[key].add(str[1:])
  23         else:
  24 	    self.final = 1
  25 
  26     def remove(self, str):
  27         """Remove str from trie"""
  28         if not str:
  29             self.final = 0
  30             return
  31 
  32         key = str[0]
  33         if self.children[key]:
  34             self.children[key].remove(str[1:])
  35         
  36 	    
  37     def has(self, str, n=0): # XXX this is a slight modfication from a std trie!
  38         """Checks if str[0:n] (may not be whole string) is in trie
  39 	
  40 	   returns 0 on no match
  41 	   returns n on a match of length n
  42 	"""
  43         if len(str):
  44             key = str[0]
  45             if self.children and key in self.children.keys():
  46                 return self.children[key].has(str[1:],n+1)
  47         return self.final*n
  48 
  49     def newhas(self, str, n=0):
  50         length = len(str)
  51         return self._has(str, n, length)
  52 
  53     def _has(self, str, n, length):
  54         if length:
  55             key = str[0]
  56             if self.children and key in self.children.keys():
  57                 return self.children[key]._has(str[1:],n+1,length-1)
  58         return self.final*n
  59 
  60 if __name__ == '__main__':
  61     t = Trie()
  62     for i in range(10000):
  63         t.add(str(i*i))
  64 	
  65     t.add("das ist ein test")
  66 
  67     print t.has("das ist ein test.trallalla")
  68     print t.has("9")
  69     print t.has("81 asdasd")
  70     print t.has("100 asdasda")
  71     print t.has("42")
  72 
  73     for i in range(100000):
  74         x=t.has(str(i))