xml地图|网站地图|网站标签 [设为首页] [加入收藏]

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

时间:2020-01-04 21:40来源:计算机
支持中文的基于词为基本粒度的前缀树(prefix trie)实现,prefixtrie Trie 树,也叫字典树、前缀树。可用于”predictivetext”和”autocompletion”,亦可用于统计词频(边插入Trie树边更新或添

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

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 中的键是一串位元,可以用于表示整数或者内存地址。

参考资料:

  1 #!/usr/bin/python                                                                                                                                                      
  2 # -*- coding:utf-8 -*-
  3 # * trie, prefix tree
  4 # * author: [email protected]
  5 import sys 
  6 reload(sys)
  7 sys.setdefaultencoding("utf-8")
  8 
  9 class Node:
 10   def __init__(self):
 11     self.value = None
 12     self.children = {}
 13 
 14 class Trie:
 15   def __init__(self):
 16     self.root = Node()
 17 
 18   def insert(self, key, value = None, sep = ' '):  # key is a word sequence separated by 'sep'
 19     elements = key if isinstance(key, list) else 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 = value
 30 
 31   def search(self, key, default = None, sep = ' '):
 32     elements = key if isinstance(key, list) else 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 if isinstance(key, list) else 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 if isinstance(key, list) else 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 if isinstance(key, list) else key.split(sep)
 68     value = 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 = node.value
 75     return value if value else default
 76 
 77   def longest_prefix_item(self, key, sep = ' '):
 78     elements = key if isinstance(key, list) else key.split(sep)
 79     node = self.root
 80     value = 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 = 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 if isinstance(prefix, list) else prefix.split(sep)
101     node = self.root
102     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 results
110 
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 广场')  

运行结果如下:

1
4
None
None
1
2
soho
soho 尚都
3
90
('soho xe5xb0x9axe9x83xbd', 3)
============== keys =================
prefix "sm":  sm | sm 新生活 广场 | sm 城市广场 | sm 广场 | sm 购物 广场 | sm 国际 广场
============== items =================
prefix "sm":  [('sm', 1), ('sm xe6x96xb0xe7x94x9fxe6xb4xbb xe5xb9xbfxe5x9cxba', 5), ('sm xe5x9fx8exe5xb8x82xe5xb9xbfxe5x9cxba', 3), ('sm xe5xb9xbfxe5x9cxba', 4), ('sm xe8xb4xadxe7x89xa9 xe5xb9xbfxe5x9cxba', 6), ('sm xe5x9bxbdxe9x99x85 xe5xb9xbfxe5x9cxba', 2)]
================= delete =====================
None

  

 

trie)实现,prefixtrie Trie 树,也叫字典树、前缀树。可用于predictive text和autocompletion,亦可用...

编辑:计算机 本文来源:支持中文的基于词为基本粒度的前缀树(prefix trie)实现,prefixtrie

关键词: