文档章节

trie树【简化的】1

大大美女女
 大大美女女
发布于 2013/10/10 17:44
字数 516
阅读 67
收藏 2
点赞 0
评论 0

Trie

又称单词查找树,Trie,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较。

Trie树最典型直观的应用:


热词提示中的应用

 

现在以只包含小写英文字母的英文单词的trie树做下说明:

        

Trie树的结构:

例如只有四个字符串:

abc  d  da  dda

则结构为:


 

 

Trie树的时空复杂度:

 

查找和插入的时间复杂度均为o(n), n为字符个数,假设只有26个小写英文字母, n26,如果为2000个汉字,n2000

 

 

Trie树的空间复杂度:

空间复杂度较高,是一个典型的空间换时间的结构,假设每个词平均长度为5,则空间复杂度为n^5

 

 上代码:此代码只处理包含26个小写英文字符情况:

#ifndef _TRIE_H_
#define _TRIE_H_


#include <string.h>
#include <iostream>

using namespace std;

const int kMaxBranchSize = 26;

struct TrieNode {
  bool is_word;
  TrieNode* next[kMaxBranchSize];
  TrieNode() : is_word(false) {
    for (int i = 0; i < kMaxBranchSize; i++) {
      next[i] = NULL;
    }
  }
};



class Trie {
  public:
    Trie() {
      root_ = new TrieNode();
    }

    ~Trie() {
      DeleteTrie(root_);
    }
  public:
    void DeleteTrie(TrieNode* root) {
      for (int i = 0; i < kMaxBranchSize; i++) {
        if (root->next[i] != NULL) {
          DeleteTrie(root->next[i]);
        }
      }
      if (root != NULL) {
        delete root;
        root = NULL;
      }
    }

    int Insert(const char* word) {
      if (NULL == word) {
        return -1;
      }
      TrieNode* now_node = root_;
      if (now_node == NULL) {
        return -2;
      }
      while (*word) {
        if (now_node->next[*word-'a'] == NULL) {
          TrieNode* tmp = new TrieNode();
          now_node->next[*word-'a'] = tmp;
        }
        now_node = now_node->next[*word-'a'];
        word++;
      }
      now_node->is_word = true;
      return 0;
    }

    int Search(const char* word) {
      if (NULL == word) {
        return -1;
      }
      TrieNode* node = root_;
      if (node == NULL) {
        return -2;
      }
      while (*word&&node != NULL) {
        node = node->next[*word - 'a'];
        word++;
      }

      if (node != NULL && node->is_word) {
        return 1;
      }

      return 0;

    }

  private:
    Trie(const Trie&);
    Trie& operator= (const Trie&);
  private:
    TrieNode* root_;

};


#endif

有趣有爱有价值:http://www.qihu100.com

 

#include "trie.h"

int main(int argc, char* argv[]) {
  Trie t;
  t.Insert("a");         
  t.Insert("ab");
  char * c = "abc";
  t.Insert(c);
  t.Insert("cba");
  if (t.Search("cba")) {
    cout<< "hehe" << endl; 
  }
  if (t.Search("cbad")) {
    cout<< "haha" << endl; 
  }
}

© 著作权归作者所有

共有 人打赏支持
大大美女女
粉丝 18
博文 60
码字总数 24479
作品 0
昌平
程序员
树结构—Trie树

很有段时间没写此系列了,今天我们来说Trie树,Trie树的名字有很多,比如字典树,前缀树等等。 一:概念 下面我们有and,as,at,cn,com这些关键词,那么如何构建trie树呢? 从上面的图中,我们...

亚特兰缇斯 ⋅ 2015/09/08 ⋅ 0

Trie 树实现与应用

Trie树 基本概念  Trie树又称字典树,它是用来查询字符串的一种数据结构。它每一个节点都有26个子节点,所以是26叉树。优点查询字符串的时候速度快,缺点浪费大量空间。  当一个字符串长为...

sdoyuxuan ⋅ 01/24 ⋅ 0

JavaScript: 实现简单的中文分词

中文分词在大数据横行的今天是越来越有用武之地了。它不仅被广泛用于专业的中文搜索引擎中,而且在关键词屏蔽、黑白名单以及文本相似度等方面也能大显身手。中文分词最简单也最常用的方式是基...

陈亦 ⋅ 2014/02/21 ⋅ 2

“1000万字符串,去掉重复”的一些思考和java实现

题目:1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现? 大数据的字符串处理我一般想到了trie树和hashmap,jdk里有hashmap的实现,所以想先...

努力的C ⋅ 2017/10/10 ⋅ 0

Python: Trie树实现字典排序

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

陈亦 ⋅ 2014/02/18 ⋅ 4

非法词判断

一个大文件,里面存储了一批非法词,每行一个词。 需求是,我随便给你一句话,能快速的判断出这句话是否包含了非法词,具体哪些非法词? 第一个关注点->算法 //////////////////////////////...

小矩阵 ⋅ 2015/11/24 ⋅ 0

给一个字符串S和一个字符串数组T(T中的字符串要比S短许多),设计一个算法, 在字符串S中查找T中的字符串

给一个字符串S和一个字符串数组T(T中的字符串要比S短许多),设计一个算法, 在字符串S中查找T中的字符串。 解答 字符串的多模式匹配问题。 我们把S称为目标串,T中的字符串称为模式串。设目标...

一贱书生 ⋅ 2016/11/28 ⋅ 0

Google 面试题 | 字典里面的最长单词

专栏 | 九章算法 网址 | http://www.jiuzhang.com 三角形分割线 给定一个字符串列表words,找到words最长的word,使得这个word可用words中的其他word一次一个字符地构建。如果有多个可选答案...

⋅ 02/10 ⋅ 0

包含偏移的AC多模匹配

【背景】在网络设备中会用到DPI技术对数据包的负载做检测,从而挖掘网络流量中的信息,DPI技术会用到多模式匹配,现有多模匹配的算法和实现只是专注于多模式匹配,都不会关注模式串的偏移信息...

laijump ⋅ 2013/06/22 ⋅ 0

Internet路由之路由表查找算法概述-哈希/LC-Trie树/256-way-mtrie树

说明:本文没有源码分析的内容,然而我认为能理解本质比能看懂源码更有用,因为理解了本质之后,你也许就不用再看源码了,你甚至都可以写源码了。这就是Linux内核和Cisco的网站中包含大量文档...

晨曦之光 ⋅ 2012/04/10 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

浅谈springboot Web模式下的线程安全问题

我们在@RestController下,一般都是@AutoWired一些Service,由于这些Service都是单例,所以并不存在线程安全问题。 由于Controller本身是单例模式 (非线程安全的), 这意味着每个request过来,...

算法之名 ⋅ 今天 ⋅ 0

知乎Java数据结构

作者:匿名用户 链接:https://www.zhihu.com/question/35947829/answer/66113038 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 感觉知乎上嘲讽题主简...

颖伙虫 ⋅ 今天 ⋅ 0

Confluence 6 恢复一个站点有关使用站点导出为备份的说明

推荐使用生产备份策略。我们推荐你针对你的生产环境中使用的 Confluence 参考 Production Backup Strategy 页面中的内容进行备份和恢复(这个需要你备份你的数据库和 home 目录)。XML 导出备...

honeymose ⋅ 今天 ⋅ 0

JavaScript零基础入门——(九)JavaScript的函数

JavaScript零基础入门——(九)JavaScript的函数 欢迎回到我们的JavaScript零基础入门,上一节课我们了解了有关JS中数组的相关知识点,不知道大家有没有自己去敲一敲,消化一下?这一节课,...

JandenMa ⋅ 今天 ⋅ 0

火狐浏览器各版本下载及插件httprequest

各版本下载地址:http://ftp.mozilla.org/pub/mozilla.org//firefox/releases/ httprequest插件截至57版本可用

xiaoge2016 ⋅ 今天 ⋅ 0

Docker系列教程28-实战:使用Docker Compose运行ELK

原文:http://www.itmuch.com/docker/28-docker-compose-in-action-elk/,转载请说明出处。 ElasticSearch【存储】 Logtash【日志聚合器】 Kibana【界面】 答案: version: '2'services: ...

周立_ITMuch ⋅ 今天 ⋅ 0

使用快嘉sdkg极速搭建接口模拟系统

在具体项目研发过程中,一旦前后端双方约定好接口,前端和app同事就会希望后台同事可以尽快提供可供对接的接口方便调试,而对后台同事来说定好接口还仅是个开始、设计流程,实现业务逻辑,编...

fastjrun ⋅ 今天 ⋅ 0

PXE/KickStart 无人值守安装

导言 作为中小公司的运维,经常会遇到一些机械式的重复工作,例如:有时公司同时上线几十甚至上百台服务器,而且需要我们在短时间内完成系统安装。 常规的办法有什么? 光盘安装系统 ===> 一...

kangvcar ⋅ 昨天 ⋅ 0

使用Puppeteer撸一个爬虫

Puppeteer是什么 puppeteer是谷歌chrome团队官方开发的一个无界面(Headless)chrome工具。Chrome Headless将成为web应用自动化测试的行业标杆。所以我们很有必要来了解一下它。所谓的无头浏...

小草先森 ⋅ 昨天 ⋅ 0

Java Done Right

* 表示难度较大或理论性较强。 ** 表示难度更大或理论性更强。 【Java语言本身】 基础语法,面向对象,顺序编程,并发编程,网络编程,泛型,注解,lambda(Java8),module(Java9),var(...

风华神使 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部