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

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

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

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

RSA 背后的算法

随着科技发展,计算能力越来越强,特别是量子计算的兴起,我们对超大质数的位数要求也越来越高,512 bit 的 RSA 已经被破解,而 1024 bit 也已经摇摇欲坠,现阶段 2048 bit 长度还是安全的,可是未来,谁又知道呢?

数据结构算法在专网项目中的实践

数据结构与算法作为计算机学科中至关重要的一门课程,在日常业务代码中常常很难用到或者说很难进行相关的实践,我们常常在leetcode中练习的习题感到没有用武之地。实际上,我们可以通过优化页面中的一些代码及在需求实现过程中对之前阅读过的源码或者之前练习过的习题进行相关的举一反三和触类旁通

js算法_奇偶分割数组

分割一个整数数组,使得奇数在前偶数在后。 比如:给定 [1, 2, 3, 4],返回 [1, 3, 2, 4]。思路分析:排序好的数组:找到奇数进行操作。乱序的数组:使用sort方法进行排序+提取奇数

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

用 JavaScript 学习算法复杂度

在后面的例子中,我将引用这两个数组,一个包含 5 个元素,另一个包含 50 个元素。我还会用到 JavaScript 中方便的 performance API 来衡量执行时间的差异

数据结构与算法之绪论

什么是数据结构?简单来说可以解释为:程序设计=数据结构+算法;主要是用来研究数据结构的关系,数据元素之间存在的一种或多种特定关系的集合;

LZW算法压缩字符串数据

有的时候代码里不得不带上一串长的字符数据表,本来就是小功能,将这种不大不小的数据外部存放显得累赘,放源码里又碍眼又占空间。

用 Javascript 写排序算法

至于为什么选择用 Javascript,则是因为我觉得 Javascript 是最方便运行和调试的,只需要复制代码粘贴到浏览器的控制台就可以了,我为所有的算法附上了测试用例,通过引入 Mocha 就可以在浏览器中显示用例的通过情况

js生成guid

全局唯一标识符(GUID,Globally Unique Identifier)也称作 UUID(Universally Unique IDentifier) 。GUID是一种由算法生成的二进制长度为128位的数字标识符。GUID 的格式为“xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx”

Js实现首字母大写

一小段字母文本可以手动输入进行字母大小写的改变,如果是一大段文本只好借助程序来实现,中字母大小写转换是基本功能。 返回一个字符串,确保字符串的每个单词首字母都大写,其余部分小写

点击更多...

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