js字典树算法_Trie树(字典树)实现与应用

时间: 2018-10-30阅读: 3230标签: 算法

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

字典树是处理字符串常见的一种树形数据结构,其优点是利用字符串的公共前缀来节约存储空间,比如加入‘abc’,‘abcd’,‘abd’,‘bcd’,‘efg’,‘hik’之后,其结构应该如下图所示:


假设我有一个题目,要求设计一个存储至少500W量级英文单词的数据结构,需要满足下面两个需求:

1.当有新的单词加入时,需要判断是否在已经存储的单词中,如果不存在则直接插入
2.来了一个单词的前缀,统计一下存储的单词中有多少个单词前缀是和该单词前缀相同  


下面我们开始来实现这个数据结构:  

//字典树
var triNode = function(key){
  this.key = key;
  this.son = [];
   this.isWord = false;//用于单词标记
}
var tree = function(){
  this.root = new triNode(null);
}
tree.prototype={
  insertData:function(stringData){
    //用于外部调用插入,目的是从根节点开始插入
    this.insert(stringData,this.root)
  },
  insert:function(stringData,node){
    //用于内部自身递归调用,层层判断是否存在或是否要插入
    if(stringData==''){
      //字符串为空,直接返回结束
      return;
    }
    //获取子节点
    var son = this.getSon(node);
    var haveData = null;
    //声明一个变量用来存储字符串第一个字符和子节点相同的节点,方便后续节点递归遍历
    for(var i in son){
      if(son[i].key==stringData[0]){
          haveData = son[i]
      }
    }
    if(haveData){
      if(stringData.length==1){
            haveData.isWord = true;
        }
        //havaData存在说明在子节点找到了,然后进行深入节点查找
        this.insert(stringData.substring(1),haveData)
    }else{
      if(son.length==0){
        //如果子节点为空,则直接插入
        var node = new triNode(stringData[0]);
        son.push(node);
        if(stringData.length==1){
            node.isWord = true;
        }
        //插入完毕后将后续字符串继续插入
        this.insert(stringData.substring(1),node);
      }else{
        var node = new triNode(stringData[0]);
        //将子节点的key进行排序插入,方便后续进行二分法查找,加快查找效率
        var vlPosition = 0;
        for(var j in son){
          if(son[j].key<stringData[0]){
              vlPosition++;
          }
        }
        if(stringData.length==1){
            node.isWord = true;
        }
        //子节点插入
        son.splice(vlPosition,0,node);
        //插入完毕后将后续字符串继续插入
        this.insert(stringData.substring(1),node);
      }
    }
  },
  justContentData:function(stringData){
    if(stringData==''){
        return 0
    }else{
      return this.justContent(stringData,this.root);
    }
  },
  justContent:function(stringData,node){
    if(stringData==''){
      //字符串为空,直接返回结束
      return 1;
    }
    var son = this.getSon(node);
    var havaData = null;
    for(var i in son){
      if(son[i].key==stringData[0]){
        havaData = son[i];
      }
    }
    if(havaData){
      return this.justContent(stringData.substring(1),havaData)
    }else{
      return 0
    }
  },
  countBeforeData:function(stringData){
    if(stringData==''){
        return 0;
    }
    var node = this.searchBeforeNode(stringData,this.root);
    if(!node){
      return 0;
    }
    return this.countBefore(node,0);
  },
  searchBeforeNode:function(stringData,node){
    if(stringData==''){
          //字符串为空,直接返回结束
          return node;
        }
        var son = this.getSon(node);
        var havaData = null;
        for(var i in son){
          if(son[i].key==stringData[0]){
            havaData = son[i];
          }
        }
        if(havaData){
          return this.searchBeforeNode(stringData.substring(1),havaData)
        }else{
          return null
        }
  },
  countBefore:function(node,num){
      if(node.isWord){
        num++;
      }
      var son  = this.getSon(node);
      var havaData = null;
      for(var i in son){
        num=this.countBefore(son[i],num);
      }
      return num;
  },
  getSon:function(node){
    //获取子节点
    return node.son;
  }
}
var msd = new tree()
//插入数据
msd.insertData("hello");
msd.insertData("helo");
msd.insertData("healo");
msd.insertData("haslo");
//前缀数量
msd.countBeforeData("ha");


以上便是完整的一个解决上述问题的代码。字典树的一个常用场景有代码补全,输入框单词提示等。

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

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

来自:https://www.oecom.cn/js-use-trie/


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/1227

关闭

js求数组中的最大差值的方法总汇

有一个无序整型数组,如何求出这个数组中最大差值。(例如:无序数组1, 3, 63, 44最大差值是 63-1=62)。实现原理:遍历一次数组,找到最大值和最小值,返回差值

JS数据结构与算法_链表

链表更加像是数组。链表和数组都是用于存储有序元素的集合,但有几点大不相同,链表的实现不像之前介绍的栈和队列一般依赖于数组(至少我们目前是这样实现的),它必须自己构建类并组织逻辑实现。我们先创建一个Node类

最短编辑距离

1.第一行表示从ME到空字符所要删除的字符的所以情况 2.第一列表示从空字符到MY所需要插入字符的所有情况 3.斜箭头表示相同字符不需要替换,不相同字符所有替换次数的所有情况

indexOf实现引申出来的各种字符串匹配算法

我们在表单验证时,经常遇到字符串的包含问题,比如说邮件必须包含indexOf。我们现在说一下indexOf。这是es3.1引进的API ,与lastIndexOf是一套的。可以用于字符串与数组中。一些面试经常用问数组的indexOf是如何实现的

动态规划解题思路

算法能力就是程序员的内力,内力强者对编程利剑的把控能力就更强。动态规划就是,通过递推的方式,由最基本的答案推导出更复杂答案的方法,直到找到最终问题的解。

迭代算法

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,在解决问题时总是重复利用一种方法。与迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题

Js哈希摘要算法

最近在看一些NPM库的时候总是看到各种哈希签名算法,之前工作中也有用到过签名算法,但并没有深入理解过其中的原理,于是找了点资料稍微了解了一下,总结了这篇文章。

用 JavaScript 实现链表

单链表是表示一系列节点的数据结构,其中每个节点指向链表中的下一个节点。 相反,双向链表具有指向其前后元素的节点。与数组不同,链表不提供对链表表中特定索引访问。

现在算法是新锐前端框架成功的重要因素

随着前端MVVM的流行,小型框架现在越来越难存活了!react, angular等打着大公司旗号的框架占了半壁江山,而avalon以其良好兼容性在国内份额不断上升。前端也与后端一样,遵循马太效应,强者愈强,弱者愈弱。最后只剩下两种框架

js实现:在字符串中找出第一个只出现一次的字符

在给出一个字符串,找出第一个只出现一次的字符。思路分析:可以用对象保存字符出现的次数。将值删除,用 indexOf 查找还有没有相同字符,并查找之前删过的字符,indexOf 的第二个参数,从当前值往后搜索,并查找之前已经查过的字符

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!