文档章节

trie树【简化的】1

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

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
196
0
Trie 树实现与应用

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

sdoyuxuan
01/24
0
0
可持久化 trie 的简单入门

可持久化 $trie$ ....又是一个表里不一的东西..... 可持久化 $trie$ 的介绍: 和主席树类似的,其实可持久化就是体现在前缀信息的维护上(搞不懂这怎么就叫做可持久化了...) $trie$ (字典树...

Judge_Cheung
08/18
0
0
JavaScript: 实现简单的中文分词

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

陈亦
2014/02/21
0
2
非法词判断

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

小矩阵
2015/11/24
27
0

没有更多内容

加载失败,请刷新页面

加载更多

Hadoop - 企业级大数据管理平台CDH(小技巧一)

附上: 喵了个咪的博客:w-blog.cn cloudera官网: https://www.cloudera.com/ 官方文档地址: https://www.cloudera.com/documentation/enterprise/latest.html 一 , 磁盘扩容磁盘迁移 对于磁盘...

喵了_个咪
32分钟前
1
0
手动安装android的sdk

手动安装android的sdk 用eclipse+sdk的方式开发app,使用android sdk manager无法下载新的sdk,可以手动下载安装。 查找sdk的地址 浏览器访问https://dl-ssl.google.com/android/repository/...

kyle960
32分钟前
1
0
call方法的模拟实现

call方法的模拟实现 初步思考 const person = { name:"小明" } function sayName() { console.log(this.name) } sayName.call(person) //result: 小明 上面的代码有两...

lsner
36分钟前
1
0
apache 报错 AH01089: search for temporary

程序上传文件一直失败。经过测试使用apache反向代理会失败,但是直接访问服务器则可以上传。 经过分析apache的错误日志发现如下提示: apache 报错 AH01089: search for temporary director...

硕硕和果果
41分钟前
2
0
java源码Integer.bitCount算法解析,分析原理

看了一道leetcode上面的题 461 ,Hamming Distance 计算两个整数有多少不同的位。其实很简单,取两个整数异或的值,然后计算出里面二进制有多少个1就行了。代码如下: public int hammi...

117
44分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部