未分类

javascript trie前缀树的示例_javascript技巧_脚本之家

26 3月 , 2020  

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

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

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

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

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

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

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

按位Trie树

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

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

基本性质

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

程序实现

优化

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

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

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

Trie树与Hash表

节点压缩。

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

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

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

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

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

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

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

Trie树的改进

var trie = new Trie; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; trie.insert; var map = {} trie.preTraversal{ if{ map[str] = node.numEnd } }) for{ console.log(i+" 出现了"+ map[i]+" 次") } console.log前缀的单词及出现次数:"); //console.log var map = {} trie.preTraversal{ if === 0 && node.isEnd){ map[str] = node.numEnd } }) for{ console.log(i+" 出现了"+ map[i]+" 次") }
// by 司徒正美class Trie { constructor() { this.root = new TrieNode { return /^[a-z1-9]+$/i.test { // addWord if  { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt; c -= 48; //减少”0“的charCode var node = cur.son[c]; if  { var node = (cur.son[c] = new TrieNode; node.value = word.charAt; node.numPass = 1; //有N个字符串经过它 } else { node.numPass++; } cur = node; } cur.isEnd = true; //樯记有字符串到此节点已经结束 cur.numEnd++; //这个字符串重复次数 return true; } else { return false; } } remove{ if  { var cur = this.root; var array = [], n = word.length for (var i = 0; i < n; i++) { var c = word.charCodeAt; c = this.getIndex var node = cur.son[c]; if{ array.push cur = node }else{ return false } } if{ array.forEach{ el.numPass-- }) cur.numEnd -- if{ cur.isEnd = false } } }else{ return false } } preTraversal{//先序遍历 function preTraversalImpl{ cb; for(let i = 0,n = root.son.length; i < n; i ++){ let node = root.son[i]; if{ preTraversalImpl(node, str + node.value, cb); } } } preTraversalImpl; } // 在字典树中查找是否存在某字符串为前缀开头的字符串 isContainPrefix { if  { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt; c -= 48; //减少”0“的charCode if  { cur = cur.son[c]; } else { return false; } } return true; } else { return false; } } isContainWord { // 在字典树中查找是否存在某字符串 if  { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt; c -= 48; //减少”0“的charCode if  { cur = cur.son[c]; } else { return false; } } return cur.isEnd; } else { return false; } } countPrefix { // 统计以指定字符串为前缀的字符串数量 if  { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt; c -= 48; //减少”0“的charCode if  { cur = cur.son[c]; } else { return 0; } } return cur.numPass; } else { return 0; } } countWord { // 统计某字符串出现的次数方法 if  { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt; c -= 48; //减少”0“的charCode if  { 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; }}

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

引子

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

测试

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

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

前缀树的应用

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

Trie树与二叉搜索树

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

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


相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图