文档章节

Trie 的原理和实现 (python 实现)

ChenQi
 ChenQi
发布于 2012/06/05 15:56
字数 390
阅读 3606
收藏 2

原理:(from wiki)

In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings.

Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.

Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. (consider a dictionary)

Looking up keys is faster. Looking up a key of length m takes worst case O(m) time. BST takes O(m log n) time.

 

Tries facilitate longest-prefix matching, but hashing does not, as a consequence of the above.

 

1.       A common application of a trie is storing a dictionary, such as one found on a mobile telephone.

2.       Tries are also well suited for implementing approximate matching algorithms.

3.       Lexicographic sorting of a set of keys can be accomplished with a simple trie-based algorithm as follows. (e.g. radix sort using trie)

4.       A trie forms the fundamental data structure of Burstsort, currently (2007) the fastest known, memory/cache-based, string sorting algorithm.[6]

 

实现实例:

 

#!/usr/bin/python                                                                                                                                                      
print '================ A Trie Demo =============='

class Node:
    def __init__(self):
        self.value = None
        self.children = {}    # children is of type {char, Node}                                                                                                       

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, key):      # key is of type string                                                                                                                
        # key should be a low-case string, this must be checked here!                                                                                                  
        node = self.root
        for char in key:
            if char not in node.children:
                child = Node()
                node.children[char] = child
                node = child
            else:
                node = node.children[char]
        node.value = key

    def search(self, key):
        node = self.root
        for char in key:
            if char not in node.children:
                return None
            else:
                node = node.children[char]
        return node.value

    def display_node(self, node):
        if (node.value != None):
            print node.value
        for char in 'abcdefghijklmnopqrstuvwxyz':
            if char in node.children:
                self.display_node(node.children[char])
        return

    def display(self):
        self.display_node(self.root)

trie = Trie()
trie.insert('hello')
trie.insert('nice')
trie.insert('to')
trie.insert('meet')
trie.insert('you')
trie.display()
print
print trie.search('hello')
print trie.search('HELLO')
print

print '================= END ====================='

 

示例结果:

root@localhost :/home/James/mypro/Python# ./trie.py
================ A Trie Demo ==============
hello
meet
nice
to
you

hello
None

================= END =====================
root@localhost :/home/James/mypro/Python#

 

© 著作权归作者所有

ChenQi
粉丝 61
博文 191
码字总数 111579
作品 0
丰台
高级程序员
私信 提问
Python: Trie树实现字典排序

一般语言都提供了按字典排序的API,比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法,最容易想到的就是字符串搜索的方式,但这种方式实现起来很麻烦,性能也不太好。T...

陈亦
2014/02/18
0
4
python中文分词,使用结巴分词对python进行分词

在采集美女站时,需要对关键词进行分词,最终采用的是python的结巴分词方法. 中文分词是中文文本处理的一个基础性工作,结巴分词利用进行中文分词。其基本实现原理有三点: 基于Trie树结构实现...

yangjiyue0520
2017/11/04
0
0
用python实现新词发现程序——基于凝固度和自由度

python学习笔记整理于猿人学网站的python教程和python爬虫 互联网时代,信息产生的数量和传递的速度非常快,语言文字也不断变化更新,新词层出不穷。一个好的新词发现程序对做NLP(自然预言处...

呆木木人儿
03/04
0
0
LeetCode 208. Implement Trie (Prefix Tree) (实现Trie树)

原题 Implement a trie with , , and methods. Example: Note: You may assume that all inputs are consist of lowercase letters . All inputs are guaranteed to be non-empty strings. R......

dby_freedom
2018/12/03
0
0
分词,难在哪里?科普+解决方案!

题图:by Lucas Davies 一、前言 分词,我想是大多数大前端开发人员,都不会接触到的一个概念。这个不影响我们了解它,毕竟我们要多方向发展。今天就来简单介绍一些分词,我尽量用简介的语言...

承香墨影
2018/10/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java的线程同步和并发问题示例

并发问题 多线程是一个非常强大的工具,它使我们能够更好地利用系统的资源,但我们需要在读取和写入多个线程共享的数据时特别小心。 当多个线程尝试同时读取和写入共享数据时,会出现两种类型...

hiuh
55分钟前
1
0
Spring Boot 常用注解说明

实体类 @Entity (实体类注解) @Table(可指定表名) @Data(可缺省get/set) @Id (指定属性主键) @GeneratedValue(指定主键生成规则)

兜兜毛毛
今天
3
0
局域网能互相ping通,ubuntu虚拟机不能上外网

【问题】 桥接模式老是无法上网,查看本机IP发现被分配了一个私网地址,猜测应该是虚拟DHCP服务器没有打开,于是查看Ubuntu的网络配置: /etc/network/interfaces 发现没有dhcp配置的信息,只...

tahiti_aa
今天
2
0
以太坊助记词PHP开发包简介

以太坊助记词PHP开发包用来为PHP以太坊应用增加助记词和层级确定密钥支持能力。下载地址:以太坊助记词php开发包 。 1、开发包概述 以太坊助记词PHP开发包主要包括以下特性: 生成符合BIP39...

汇智网教程
昨天
2
0
系统监控-分布式调用链Skywalking

1. 为什么要使用分布式调用链技术? 随着公司业务的高速发展,公司服务之间的调用关系愈加复杂,如何理清并跟踪它们之间的调用关系就显的比较关键。线上每一个请求会经过多个业务系统,并产生...

秋日芒草
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部