javascript trie前缀树的示例

引子

Trie树(来自单词retrieval),又称前缀字,单词查找树,字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构。

它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

Trie树也有它的缺点, 假定我们只对字母与数字进行处理,那么每个节点至少有52+10个子节点。为了节省内存,我们可以用链表或数组。在JS中我们直接用数组,因为JS的数组是动态的,自带优化。

基本性质

  1. 根节点不包含字符,除根节点外的每一个子节点都包含一个字符
  2. 从根节点到某一节点。路径上经过的字符连接起来,就是该节点对应的字符串
  3. 每个节点的所有子节点包含的字符都不相同

程序实现

// by 司徒正美
class Trie {
 constructor() {
  this.root = new TrieNode();
 }
 isValid(str) {
  return /^[a-z1-9]+$/i.test(str);
 }
 insert(word) {
  // addWord
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    var node = cur.son[c];
    if (node == null) {
     var node = (cur.son[c] = new TrieNode());
     node.value = word.charAt(i);
     node.numPass = 1; //有N个字符串经过它
    } else {
     node.numPass++;
    }
    cur = node;
   }
   cur.isEnd = true; //樯记有字符串到此节点已经结束
   cur.numEnd++; //这个字符串重复次数

   return true;
  } else {
   return false;
  }
 }
 remove(word){
   if (this.isValid(word)) {
     var cur = this.root;
     var array = [], n = word.length
     for (var i = 0; i < n; i++) {
       var c = word.charCodeAt(i);
       c = this.getIndex(c)
       var node = cur.son[c];
       if(node){
         array.push(node)
         cur = node
       }else{
         return false
       }

     }
     if(array.length === n){
       array.forEach(function(){
         el.numPass--
       })
       cur.numEnd --
       if( cur.numEnd == 0){
         cur.isEnd = false
       }
     }
   }else{
     return false
   }
 }
 preTraversal(cb){//先序遍历
    function preTraversalImpl(root, str, cb){
      cb(root, str);
      for(let i = 0,n = root.son.length; i < n; i ++){
        let node = root.son[i];
        if(node){
          preTraversalImpl(node, str + node.value, cb);
        }
      }
    }
    preTraversalImpl(this.root, "", cb);
  }
 // 在字典树中查找是否存在某字符串为前缀开头的字符串(包括前缀字符串本身)
 isContainPrefix(word) {
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    if (cur.son[c]) {
     cur = cur.son[c];
    } else {
     return false;
    }
   }
   return true;
  } else {
   return false;
  }
 }
 isContainWord(str) {
  // 在字典树中查找是否存在某字符串(不为前缀)
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    if (cur.son[c]) {
     cur = cur.son[c];
    } else {
     return false;
    }
   }
   return cur.isEnd;
  } else {
   return false;
  }
 }
 countPrefix(word) {
  // 统计以指定字符串为前缀的字符串数量
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    if (cur.son[c]) {
     cur = cur.son[c];
    } else {
     return 0;
    }
   }
   return cur.numPass;
  } else {
   return 0;
  }
 }
 countWord(word) {
  // 统计某字符串出现的次数方法
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    if (cur.son[c]) {
     cur = cur.son[c];
    } else {
     return 0;
    }
   }
   return cur.numEnd;
  } else {
   return 0;
  }
 }
}

class TrieNode {
 constructor() {
  this.numPass = 0;//有多少个单词经过这节点
  this.numEnd = 0; //有多少个单词就此结束
  this.son = [];
  this.value = ""; //value为单个字符
  this.isEnd = false;
 }
}

我们重点看一下TrieNode与Trie的insert方法。 由于字典树是主要用在词频统计,因此它的节点属性比较多, 包含了numPass, numEnd但非常重要的属性。

insert方法是用于插入重词,在开始之前,我们必须判定单词是否合法,不能出现 特殊字符与空白。在插入时是打散了一个个字符放入每个节点中。每经过一个节点都要修改numPass。

优化

现在我们每个方法中,都有一个c=-48的操作,其实数字与大写字母与小写字母间其实还有其他字符的,这样会造成无谓的空间的浪费

// by 司徒正美
getIndex(c){
   if(c < 58){//48-57
     return c - 48
   }else if(c < 91){//65-90
     return c - 65 + 11
   }else {//> 97
     return c - 97 + 26+ 11
   }
 }

然后相关方法将c-= 48改成c = this.getIndex(c)即可

测试

var trie = new Trie();
  trie.insert("I");
  trie.insert("Love");
  trie.insert("China");
  trie.insert("China");
  trie.insert("China");
  trie.insert("China");
  trie.insert("China");
  trie.insert("xiaoliang");
  trie.insert("xiaoliang");
  trie.insert("man");
  trie.insert("handsome");
  trie.insert("love");
  trie.insert("Chinaha");
  trie.insert("her");
  trie.insert("know");
  var map = {}
  trie.preTraversal(function(node, str){
    if(node.isEnd){
     map[str] = node.numEnd
    }
  })
  for(var i in map){
    console.log(i+" 出现了"+ map[i]+" 次")
  }
  console.log("包含Chin(包括本身)前缀的单词及出现次数:");
  //console.log("China")
  var map = {}
  trie.preTraversal(function(node, str){
    if(str.indexOf("Chin") === 0 && node.isEnd){
      map[str] = node.numEnd
    }
   })
  for(var i in map){
    console.log(i+" 出现了"+ map[i]+" 次")
  }

Trie树和其它数据结构的比较

Trie树与二叉搜索树

二叉搜索树应该是我们最早接触的树结构了,我们知道,数据规模为n时,二叉搜索树插入、查找、删除操作的时间复杂度通常只有O(log n),最坏情况下整棵树所有的节点都只有一个子节点,退变成一个线性表,此时插入、查找、删除操作的时间复杂度是O(n)。

通常情况下,Trie树的高度n要远大于搜索字符串的长度m,故查找操作的时间复杂度通常为O(m),最坏情况下的时间复杂度才为O(n)。很容易看出,Trie树最坏情况下的查找也快过二叉搜索树。

文中Trie树都是拿字符串举例的,其实它本身对key的适宜性是有严格要求的,如果key是浮点数的话,就可能导致整个Trie树巨长无比,节点可读性也非常差,这种情况下是不适宜用Trie树来保存数据的;而二叉搜索树就不存在这个问题。

Trie树与Hash表

考虑一下Hash冲突的问题。Hash表通常我们说它的复杂度是O(1),其实严格说起来这是接近完美的Hash表的复杂度,另外还需要考虑到hash函数本身需要遍历搜索字符串,复杂度是O(m)。在不同键被映射到“同一个位置”(考虑closed hashing,这“同一个位置”可以由一个普通链表来取代)的时候,需要进行查找的复杂度取决于这“同一个位置”下节点的数目,因此,在最坏情况下,Hash表也是可以成为一张单向链表的。

Trie树可以比较方便地按照key的字母序来排序(整棵树先序遍历一次就好了),这跟绝大多数Hash表是不同的(Hash表一般对于不同的key来说是无序的)。

在较理想的情况下,Hash表可以以O(1)的速度迅速命中目标,如果这张表非常大,需要放到磁盘上的话,Hash表的查找访问在理想情况下只需要一次即可;但是Trie树访问磁盘的数目需要等于节点深度。

很多时候Trie树比Hash表需要更多的空间,我们考虑这种一个节点存放一个字符的情况的话,在保存一个字符串的时候,没有办法把它保存成一个单独的块。Trie树的节点压缩可以明显缓解这个问题,后面会讲到。

Trie树的改进

按位Trie树(Bitwise Trie)

原理上和普通Trie树差不多,只不过普通Trie树存储的最小单位是字符,但是Bitwise Trie存放的是位而已。位数据的存取由CPU指令一次直接实现,对于二进制数据,它理论上要比普通Trie树快。

节点压缩。

分支压缩:对于稳定的Trie树,基本上都是查找和读取操作,完全可以把一些分支进行压缩。例如,前图中最右侧分支的inn可以直接压缩成一个节点“inn”,而不需要作为一棵常规的子树存在。Radix树就是根据这个原理来解决Trie树过深问题的。

节点映射表:这种方式也是在Trie树的节点可能已经几乎完全确定的情况下采用的,针对Trie树中节点的每一个状态,如果状态总数重复很多的话,通过一个元素为数字的多维数组(比如Triple Array Trie)来表示,这样存储Trie树本身的空间开销会小一些,虽说引入了一张额外的映射表。

前缀树的应用

前缀树还是很好理解,它的应用也是非常广的。

(1)字符串的快速检索

字典树的查询时间复杂度是O(logL),L是字符串的长度。所以效率还是比较高的。字典树的效率比hash表高。

(2)字符串排序

从上图我们很容易看出单词是排序的,先遍历字母序在前面。减少了没必要的公共子串。

(3)最长公共前缀

inn和int的最长公共前缀是in,遍历字典树到字母n时,此时这些单词的公共前缀是in。

(4)自动匹配前缀显示后缀

我们使用辞典或者是搜索引擎的时候,输入appl,后面会自动显示一堆前缀是appl的东东吧。那么有可能是通过字典树实现的,前面也说了字典树可以找到公共前缀,我们只需要把剩余的后缀遍历显示出来即可。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

您可能感兴趣的文章:

  • JavaScript实现二叉树定义、遍历及查找的方法详解
  • JS实现二叉查找树的建立以及一些遍历方法实现
  • JavaScript数据结构之二叉树的查找算法示例
  • JavaScript数据结构之二叉查找树的定义与表示方法
(0)

相关推荐

  • JavaScript实现二叉树定义、遍历及查找的方法详解

    本文实例讲述了JavaScript实现二叉树定义.遍历及查找的方法.分享给大家供大家参考,具体如下: 二叉树(binary tree) 在写这篇文章之前说一下数据结构和算法这个系列,这个系列包含了很多东西,比如啥子排序,线性表,广义表,树,图这些大家都是知道的,但是这些东西我们学了之后工作中能用到的又有多少呢,据我所知绝大部分公司,一线码农,屌丝,程序猿是用不到这些东西,既然这样为啥子我还要强调这个系列呢,本人觉得算法和数据结构是程序的基本功,前提想脱离一线码农,普通程序猿行列,说得通俗一点就是

  • JS实现二叉查找树的建立以及一些遍历方法实现

    二叉查找树是由节点和边组成的. 我们可以定义一个节点类Node,里面存放节点的数据,及左右子节点,再定义一个用来显示数据的方法: //以下定义一个节点类 function Node(data,left,right){ // 节点的键值 this.data = data; // 左节点 this.left = left; // 右节点 this.right = left; // 显示该节点的键值 this.show = show; } // 实现show方法 function show(){ re

  • JavaScript数据结构之二叉查找树的定义与表示方法

    本文实例讲述了JavaScript数据结构之二叉查找树的定义与表示方法.分享给大家供大家参考,具体如下: 树是一种非线性的数据结构,以分层的方式存储数据.树被用来存储具有层级关系的数据,比如文件系统中的文件:树还被用来存储有序列表.这里将研究一种特殊的树:二叉树.选择树而不是那些基本的数据结构,是因为在二叉树上进行查找非常快(而在链表上查找则不是这样),为二叉树添加或删除元素也非常快(而对数组执行添加或删除操作则不是这样). 树是n个结点的有限集.最上面的为根,下面为根的子树.树的节点包含一个数

  • JavaScript数据结构之二叉树的查找算法示例

    本文实例讲述了JavaScript数据结构之二叉树的查找算法.分享给大家供大家参考,具体如下: 前面文章介绍了二叉树的遍历,现在谈谈在二叉树中进行查找.对二叉查找树来说,一般有以下三类查找:最大值,最小值和给定值. 查找最小值就是遍历左子树,直到找到最后一个结点,这是因为在二叉查找树中较小的值总是在左子节点上的. 代码如下: function getMin(){//查找最小值 var current=this.root;//指向根节点 while(current.left!=null){ cur

  • javascript trie前缀树的示例

    引子 Trie树(来自单词retrieval),又称前缀字,单词查找树,字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构. 它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高. Trie的核心思想是空间换时间.利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. Trie树也有它的缺点, 假定我们只对字母与数字进行处理,那么每个节点至少有52+10个子节点.为了节省内存,我们可以用链表或数组.在JS中我们直接用数组,因为JS的数组是动态的,自带优化

  • 详解Java前缀树Trie的原理及代码实现

    目录 Trie的概念 Trie的实现 基本结构 构建Trie 查找字符串 Trie的总结 Trie的概念 Trie(发音类似 “try”)又被称为前缀树.字典树.Trie利用字符串的公共前缀来高效地存储和检索字符串数据集中的关键词,最大限度地减少无谓的字符串比较,其核心思想是用空间换时间. Trie树可被用来实现字符串查询.前缀查询.词频统计.自动拼写.补完检查等等功能. Trie树的三个性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起

  • go语言数据结构之前缀树Trie

    目录 介绍 流程 代码 初始化 插入 查找 统计以XXX开头的单词个数 删除数据 介绍 Trie树:又称为单词查找树,是一种树形结构,可以应用于统计字符串,会在搜索引擎系统中用于对文本的词频统计,下图是一个Trie树的结构,同时它也是在插入数时的一个顺序图. 流程 首先应该先创建一个结构体,里面保存的是每一个节点的信息 初始化根节点,根节点应该初始化啥?啥也不用初始化,给个空就好看上图 插入:串转字符数组:遍历数组,如果下一个节点为空,创建,则继续遍历 查找:串转字符数组,遍历如何所有字符都在树

  • Python容错的前缀树实现中文纠错

    目录 介绍 实现 参考 介绍 本文使用 Python 实现了前缀树,并且支持编辑距离容错的查询.文中的前缀树只存储了三个分词,格式为 (分词字符串,频率) ,如:('中海晋西园', 2).('中海西园', 24).('中南海', 4),可以换成自己的文件进行数据的替换.在查询的时候要指定一个字符串和最大的容错编辑距离. 实现 class Word: def __init__(self, word, freq): self.word = word self.freq = freq class Tr

  • C++实现LeetCode(208.实现字典树(前缀树))

    [LeetCode] 208. Implement Trie (Prefix Tree) 实现字典树(前缀树) Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple");   // returns true trie.search("app&

  • SpringBoot使用前缀树过滤敏感词的方法实例

    目录 一.前缀树 二.敏感词过滤器 总结 一.前缀树 一般设计网站的时候,会有问题发布或者是内容发布的功能,这些功能的有一个很重要的点在于如何实现敏感词过滤,要不然可能会有不良信息的发布,或者发布的内容中有夹杂可能会有恶意功能的代码片段,敏感词过滤的基本的算法是前缀树算法,前缀树也就是字典树,通过前缀树匹配可以加快敏感词匹配的速度. 前缀树又称为Trie.字典树.查找树.主要特点是:查找效率高,但内存消耗大:主要应用于字符串检索.词频统计.字符串排序等. 到底什么是前缀树?前缀树的功能是如何实现

  • Vue编程三部曲之模型树优化示例

    目录 前言 为什么要做优化? optimize isStaticKey isPlatformReservedTag HTML 保留标签 SVG 保留标签 标记静态节点 判断节点状态并标记 基础元素节点的处理 标记静态根 什么节点会成为静态根? 为什么子节点不能仅为一个文本节点? 标记静态节点和静态根节点有什么区别? 总结 前言 对编译过程的了解会让我们对 Vue 的指令.内置组件等有更好的理解.不过由于编译的过程是一个相对复杂的过程,我们只要求理解整体的流程.输入和输出即可,对于细节我们不必抠太

  • Go 语言前缀树实现敏感词检测

    目录 一.前言 二.敏感词检测 暴力匹配 正则匹配 三.Go 语言实现敏感词前缀树 前缀树结构 添加敏感词 匹配敏感词 过滤特殊字符 添加拼音检测 四.源代码 一.前言 大家都知道游戏文字.文章等一些风控场景都实现了敏感词检测,一些敏感词会被屏蔽掉或者文章无法发布.今天我就分享用Go实现敏感词前缀树来达到文本的敏感词检测,让我们一探究竟! 二.敏感词检测 实现敏感词检测都很多种方法,例如暴力.正则.前缀树等.例如一个游戏的文字交流的场景,敏感词会被和谐成 * ,该如何实现呢?首先我们先准备一些敏

  • JAVA使用前缀树(Tire树)实现敏感词过滤、词典搜索

    目录 简介 Trie树 code 结论 简介 有时候需要对用户输入的内容进行敏感词过滤,或者实现查找文本中出现的词典中的词,用遍历的方式进行替换或者查找效率非常低,这里提供一个基于Trie树的方式,进行关键词的查找与过滤,在词典比较大的情况下效率非常高. Trie树 Trie树,又叫前缀树,多说无益,直接看图就明白了 词典:[“猪狗”, “小狗”, “小猫”, “小猪”, “垃圾”, “狗东西”] Tire数据结构: code 树节点Node.class /** * trie tree * *

  • JavaScript中removeChild 方法开发示例代码

    1. 概述 删除后的节点虽然不在文档树中了,但其实它还在内存中,可以随时再次被添加到别的位置. 当你遍历一个父节点的子节点并进行删除操作时,要注意,children属性是一个只读属性,并且它在子节点变化时会实时更新 // 拿到待删除节点: var self = document.getElementById('to-be-removed'); // 拿到父节点: var parent = self.parentElement; // 删除: var removed = parent.remove

随机推荐