nodetrie 1.0.6

nodetrie

trie数据结构库。

安装

pip install nodetrie

动机、设计目标

nodetrie是本机c库的python扩展。

这是因为缺少可行的python替代方案。虽然存在其他的TIE库实现，但它们受到严重的限制，例如

• 只读结构，无插入
• 大型树的高内存使用率
• 缺少搜索，特别是文件掩码或通配符式搜索
• 慢速插入

现有的PyPI实现落入这些大类，包括^ {A3}（只读）和^ {A4}（慢插入，对于大的树使用非常高的内存）。

nodetrie的c库旨在尽可能减少内存使用，并且仍然允许搜索任意长度的树。

每个节点都有一个与其关联的名称作为其数据，以及子节点列表和子节点数。

功能和设计说明

• nodetrie是一个n元树，意味着任何一个节点都可以有任意数量的子节点
• 节点子数组在插入时根据需要按每个节点动态调整大小。没有固定的最小或最大大小< /LI>
• 节点名可以是任意长度，允许使用可用内存
• 来自Node.name的节点名在python 2/3中始终是unicode
• 插入时可以使用任何python字符串类型
• 节点名在插入时从unicode隐式解码，如果需要，使用nodetrie.ENCODING（utf-8）可以重写的默认编码
• 每次调用Node.children时，都会从底层c指针创建新的pythonNode对象。创建这些对象的python解释器有开销。取而代之的是，保留和重复使用儿童参考资料是安全的，而且性能更好，请参见下面的示例

限制

• 未实现删除
• C库实现为儿童使用指针数组，以减少搜索空间的复杂性和名称的字符指针，以允许任意的名称长度。这可能会导致内存碎片
• Nodepython中的对象是只读的。不可能重写现有的^ {tT3}$对象的名称，也不能修改其属性
。
• 不应使用允许使用空字符（如ucs-2）的字符编码

示例用法

fromnodetrieimportNode# This is the root of the tree, keep a reference to it.# Deleting or letting the root node go out of scope will de-allocate# the entire treenode=Node()# Insert a linked tree so that a->b->c->d where -> means 'has child node'node.insert_split_path(['a','b','c','d'])node.children[0].name=='a'# Sub-trees can be referred to by child nodesa_node=node.children[0]a_node.name=='a'a_node.children[0].name=='b'a_node.is_leaf()==False# Insertions create only new nodes# Insert linked tree so that a->b->c->ddnode.insert_split_path(['a','b','c','dd'])# Only one 'a' nodenode.children_size==1# Existing references to nodes will have correct children# after insertion without recreating the node object.# Here, a_node is an existing object prior to more nodes# being added to its sub-tree. After insertion, a's sub-tree contains newly# inserted nodes as expected# 'c' node is first child of 'b' which is first child of 'a'# 'c' node has two children, 'd' and 'dd'c_node=a_node.children[0].children[0]c_node.children_size==2c_node.is_leaf()==False# 'd' and 'dd' are both leaf nodesleaf_nodes=[cforcinc_node.childrenifc.is_leaf()]len(leaf_nodes)==2

from__future__importprint_functionfromnodetrieimportNodenode=Node()forpathsin[['a','b','c1','d1'],['a','b','c1','d2'],['a','b','c2','d1'],['a','b','c2','d2']]:node.insert_split_path(paths)forpath,_nodeinnode.search(node,['a','b','*','*'],[]):print(path,_node)

[u'a',u'b',u'c1',u'd1']Node:'d1'[u'a',u'b',u'c1',u'd2']Node:'d2'[u'a',u'b',u'c2',u'd1']Node:'d1'[u'a',u'b',u'c2',u'd2']Node:'d2'

formatchinnode.query('a.b.*.*'):print(match)formatchinnode.query('a|b|*|*',separator='|'):print(match)

(u'a.b.c1.d1',Node:'d1')(u'a.b.c1.d2',Node:'d2')(u'a.b.c2.d1',Node:'d1')(u'a.b.c2.d2',Node:'d2')(u'a|b|c1|d1',Node:'d1')(u'a|b|c1|d2',Node:'d2')(u'a|b|c2|d1',Node:'d1')(u'a|b|c2|d2',Node:'d2')