關於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.往字典裡面添加新鍵可能導致擴容，導致哈希數組中鍵的次序變化。因此，不要在遍歷字典的同時進行字典的修改。