字符串模式匹配算法系列（三）：Trie树

 1 #!/usr/bin/env python
 2 #-*- coding: utf-8 -*-
 3 import sys
 4 import pdb
 5 
 6 reload(sys)
 7 sys.setdefaultencoding(‘utf-8‘)
 8 
 9 class TrieNode(object):
10     """Trie节点
11 
12     Attributes:
13         value: 本节点的值（非None即作为结束判断条件）
14         successor: 后继节点
15     """
16     def __init__(self,value=None):
17         self.value = value
18         self.successor = {}
19 
20     def set_successor(self,key,value=None):
21         if key not in self.successor:
22             self.successor[key] = TrieNode(value)
23         elif value is not None:
24             self.successor[key].value = value
25         return self.successor[key]
26 
27     def get_successor(self,key):
28         if key not in self.successor:
29             return None
30         return self.successor[key]
31 
32 
33 class Trie(object):
34     """Trie树
35     """
36     def __init__(self):
37         # 生成root节点
38         self.root = TrieNode()
39 
40     def insert(self,word):
41         """插入操作
42         """
43         word_len = len(word)
44         curr = self.root
45 
46         for i,c in enumerate(word):
47             value = True if i + 1 == word_len else None
48             curr = curr.set_successor(c,value)
49 
50     def search(self,word):
51         word_len = len(word)
52         curr = self.root
53         ret = False
54 
55         for i,c in enumerate(word):
56             curr = curr.get_successor(c)
57             if curr is None:
58                 break
59             if i + 1 == word_len and curr.value is True:
60                 ret = True
61                 break
62         return ret
63 
64     def startsWith(self,prefix):
65         curr = self.root
66         ret = True
67 
68         for c in prefix:
69             curr = curr.get_successor(c)
70             if curr is None:
71                 ret = False
72                 break
73         return ret
74 
75 
76 def main():
77     trie = Trie()
78 
79     trie.insert("app")
80     trie.insert("apple")
81     trie.insert("beer")
82     trie.insert("add")
83     trie.insert("jam")
84     trie.insert("rental")
85     print trie.search("apps")
86     print trie.search("app")
87 
88 
89 if __name__ == ‘__main__‘:
90     main()