首页 > 代码库 > 支持中文的基于词为基本粒度的前缀树(prefix trie)实现

支持中文的基于词为基本粒度的前缀树(prefix trie)实现

Trie树,也叫字典树、前缀树。可用于”predictive text”和”autocompletion”,亦可用于统计词频(边插入Trie树边更新或添加词频)。

在计算机科学中,trie,又称前缀树字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 这个术语来自于 retrieval。根据词源学,trie 的发明者 Edward Fredkin 把它读作 英语发音:/?tri?/ "tree"。[1][2] 但是,其他作者把它读作 英语发音:/?tra?/ "try"。[1][2][3]

在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。

键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示 trie 的原理。

trie 中的键通常是字符串,但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie 中的键是一串位元,可以用于表示整数或者内存地址。

参考资料:http://zh.wikipedia.org/wiki/Trie

  1 #!/usr/bin/python                                                                                                                                                        2 # -*- coding:utf-8 -*-  3 # * trie, prefix tree  4 # * author: yangxudongsuda@gmail.com  5 import sys   6 reload(sys)  7 sys.setdefaultencoding("utf-8")  8   9 class Node: 10   def __init__(self): 11     self.value =http://www.mamicode.com/ None 12     self.children = {} 13  14 class Trie: 15   def __init__(self): 16     self.root = Node() 17  18   def insert(self, key, value = http://www.mamicode.com/None, sep =  ):  # key is a word sequence separated by ‘sep‘ 19     elements = key.split(sep) 20     node = self.root 21     for e in elements: 22       if not e: continue 23       if e not in node.children: 24         child = Node() 25         node.children[e] = child 26         node = child 27       else: 28         node = node.children[e] 29     node.value =http://www.mamicode.com/ value 30  31   def search(self, key, default = None, sep =  ): 32     elements = key.split(sep) 33     node = self.root 34     for e in elements: 35       if e not in node.children: 36         return default 37       node = node.children[e] 38     return node.value 39  40   def delete(self, key, sep =  ): 41     elements = key.split(sep) 42     self.__delete(elements) 43  44   def __delete(self, elements, node = None, i = 0): 45     node = node if node else self.root 46     e = elements[i] 47     if e in node.children: 48       child_node = node.children[e] 49       if len(elements) == (i+1): 50         return node.children.pop(e) if len(child_node.children)==0 else False 51       elif self.__delete(elements, child_node, i+1): 52         return node.children.pop(e) if (len(child_node.children)==0 and not child_node.value) else False 53     return False 54  55   def longest_prefix(self, key, sep =  ): 56     elements = key.split(sep) 57     results = [] 58     node = self.root 59     for e in elements: 60       if e not in node.children: 61         return sep.join(results) 62       results.append(e) 63       node = node.children[e]    64     return sep.join(results) 65  66   def longest_prefix_value(self, key, default = None, sep =  ): 67     elements = key.split(sep) 68     value =http://www.mamicode.com/ default 69     node = self.root 70     for e in elements: 71       if e not in node.children: 72         return value 73       node = node.children[e] 74       value =http://www.mamicode.com/ node.value 75     return value if value else default 76  77   def longest_prefix_item(self, key, sep =  ): 78     elements = key.split(sep) 79     node = self.root 80     value =http://www.mamicode.com/ node.value 81     results = [] 82     for e in elements: 83       if e not in node.children: 84         return (sep.join(results), value) 85       results.append(e) 86       node = node.children[e] 87       value =http://www.mamicode.com/ node.value 88     return (sep.join(results), value) 89  90   def __collect_items(self, node, path, results, sep): 91     if node.value: 92       results.append((sep.join(path), node.value)) 93     for k, v in node.children.iteritems():    94       path.append(k) 95       self.__collect_items(v, path, results, sep) 96       path.pop() 97     return results   98  99   def items(self, prefix, sep =  ):100     elements = prefix.split(sep)101     node = self.root102     for e in elements:103       if e not in node.children:104         return []105       node = node.children[e]106     results = []107     path = [prefix]108     self.__collect_items(node, path, results, sep)109     return results110 111   def keys(self, prefix, sep =  ):112     items = self.items(prefix, sep)113     return [key for key,value in items]114 115 if __name__ == __main__:116   trie = Trie()117   trie.insert(happy 站台, 1)118   trie.insert(happy 站台 美食 购物 广场, 2)119   trie.insert(sm, 1)         120   trie.insert(sm 国际 广场, 2)121   trie.insert(sm 城市广场, 3)122   trie.insert(sm 广场, 4)123   trie.insert(sm 新生活 广场, 5)124   trie.insert(sm 购物 广场, 6)125   trie.insert(soho 尚都, 3)126 127   print trie.search(sm)128   print trie.search(sm 广场)129   print trie.search(sm 新东方广场)130   print trie.search(神马)131   print trie.search(happy 站台)132   print trie.search(happy 站台 美食 购物 广场)133   print trie.longest_prefix(soho 广场)134   print trie.longest_prefix(soho 尚都 广场)135   print trie.longest_prefix_value(soho 尚都 广场)136   print trie.longest_prefix_value(xx 尚都 广场, 90)137   print trie.longest_prefix_item(soho 尚都 广场)138 139   print ============== keys =================140   print prefix "sm": ,  | .join(trie.keys(sm))141   print ============== items =================142   print prefix "sm": , trie.items(sm)143 144   print ================= delete =====================145   trie.delete(sm 广场)146   print trie.search(sm 广场)  

运行结果如下:

14NoneNone12sohosoho 尚都390(‘soho \xe5\xb0\x9a\xe9\x83\xbd‘, 3)============== keys =================prefix "sm":  sm | sm 新生活 广场 | sm 城市广场 | sm 广场 | sm 购物 广场 | sm 国际 广场============== items =================prefix "sm":  [(‘sm‘, 1), (‘sm \xe6\x96\xb0\xe7\x94\x9f\xe6\xb4\xbb \xe5\xb9\xbf\xe5\x9c\xba‘, 5), (‘sm \xe5\x9f\x8e\xe5\xb8\x82\xe5\xb9\xbf\xe5\x9c\xba‘, 3), (‘sm \xe5\xb9\xbf\xe5\x9c\xba‘, 4), (‘sm \xe8\xb4\xad\xe7\x89\xa9 \xe5\xb9\xbf\xe5\x9c\xba‘, 6), (‘sm \xe5\x9b\xbd\xe9\x99\x85 \xe5\xb9\xbf\xe5\x9c\xba‘, 2)]================= delete =====================None

  

 

支持中文的基于词为基本粒度的前缀树(prefix trie)实现