关于python实现trie树的信息

本文目录一览：

1、python中用字典写出树形数据结构并在控制台中打印树形数据结构
2、傻傻分不清吗？——Trie Tree，字典树、前缀树概述
3、怎么是用python 语言使用结巴分词呢
4、python字典怎么表现二叉树
5、Python字典的底层实现

python中用字典写出树形数据结构并在控制台中打印树形数据结构

#!/usr/bin/python3

# -*- coding: utf-8 -*-

def print_tree(tree):

buff = [‘ROOT/’]

_print_tree(tree, buff, ”, 0)

print(‘\n’.join(buff))

def _print_tree(tree, buff, prefix, level):

count = len(tree)

for k, v in tree.items():

count -= 1

if v:

buff.append(‘%s +- %s/’ % (prefix, k))

if count 0:

_print_tree(v, buff, prefix + ‘ | ‘, level + 1)

else:

_print_tree(v, buff, prefix + ‘ ‘, level + 1)

else:

buff.append(‘%s +- %s’ % (prefix, k))

def test():

tree = {

‘bin’: { ‘bash’: None, ‘cat’: None, ‘cp’: None, },

‘etc’: {

‘init.d’: { ‘apache2’:None, ‘slapd’:None, ‘sshd’:None, },

‘passwd’: None,

‘hosts’: None,

‘var’: {

‘log’: {

‘apache2’: { ‘accesslog’:None, ‘errorlog’: None, },

}

print_tree(tree)

if __name__ == ‘__main__’:

test()

输出结果：

ROOT/

+- etc/

| +- passwd

| +- init.d/

| | +- apache2

| | +- sshd

| | +- slapd

| +- hosts

+- bin/

| +- cp

| +- bash

| +- cat

+- var/

+- log/

+- apache2/

+- errorlog

+- accesslog

傻傻分不清吗？——Trie Tree，字典树、前缀树概述

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。

从上图可以归纳出Trie树的基本性质：

实际场景中，每个中间节点，会设置「一个标记」，用于标识当前节点是否构成一个单词（关键词）。

字典树，作为数据结构，有什么用？本质是：查询效率，或者说「时间复杂度」。

Trie树：

优点：

缺点：

具体的应用场景：

怎么是用python 语言使用结巴分词呢

Python代码

#encoding=utf-8

import jieba

seg_list = jieba.cut(“我来到北京清华大学”,cut_all=True)

print “Full Mode:”, “/ “.join(seg_list) #全模式

seg_list = jieba.cut(“我来到北京清华大学”,cut_all=False)

print “Default Mode:”, “/ “.join(seg_list) #默认模式

seg_list = jieba.cut(“他来到了网易杭研大厦”)

print “, “.join(seg_list)

输出：

Full Mode: 我/ 来/ 来到/ 到/ 北/ 北京/ 京/ 清/ 清华/ 清华大学/ 华/ 华大/ 大/ 大学/ 学

Default Mode: 我/ 来到/ 北京/ 清华大学

他, 来到, 了, 网易, 杭研, 大厦 (此处，“杭研”并没有在词典中，但是也被Viterbi算法识别出来了)

python字典怎么表现二叉树

用python构造一个n层的完全二叉树的代码如下： typedef struct {int weight;int parent, lchild, rchild; } HTNode ,*HuffmanTree; // 动态分配数组存储huffman树算法设计void createHuffmantree(){ ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode.

Python字典的底层实现

字典是一种可变、无序容器数据结构。元素以键值对存在，键值唯一。它的特点搜索速度很快：数据量增加10000倍，搜索时间增加不到2倍；当数据量很大的时候，字典的搜索速度要比列表快成百上千倍。

在Python中，字典是通过散列表（哈希表）实现的。字典也叫哈希数组或关联数组，所以其本质是数组（如下图），每个 bucket 有两部分：一个是键对象的引用，一个是值对象的引用。所有 bucket 结构和大小一致，我们可以通过偏移量来读取指定 bucket。

定义一个字典 dic = {}，假设其哈希数组长度为8。

Python会根据哈希数组的拥挤程度对其扩容。“扩容”指的是:创造更大的数组，这时候会对已经存在的键值对重新进行哈希取余运算保存到其它位置；一般接近 2/3 时，数组就会扩容。扩容后，偏移量的数字个数增加，如数组长度扩容到16时，可以用最右边4位数字作为偏移量。

计算键对象 name 的哈希值，然后比较哈希数组对应索引内的bucket是否为空，为空返回 None ，否则计算这个bucket的键对象的哈希值，然后与 name 哈希值比较，相等则返回值对象，否则继续左移计算哈希值。

注意：

1.键必须为可哈希的，如数字、元组、字符串；自定义对象需要满足支持hash、支持通过 __eq__() 方法检测相等性、若 a == b 为真，则 hash(a) == hash(b) 也为真。

2.字典的内存开销很大，以空间换时间。

3.键查询速度很快，列表查询是按顺序一个个遍历，字典则是一步到位。

4.往字典里面添加新键可能导致扩容，导致哈希数组中键的次序变化。因此，不要在遍历字典的同时进行字典的修改。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/196001.html