关闭

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

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

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

关闭

程序员必知必会的10 大基础算法!

快速排序算法:快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(nlogn)算法更快

Js加密算法_Base64

首先有个小Tips,1个字母字符 = 1个字节(byte) = 8位(bit),这是表示单位.Base64是网络上最常见的用于传输 8bit 的编码方式之一,Base64就是一种基于64个可打印字符来表示二进制数据的方法。

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

在开发页面的时候,我们有时候会遇到这种需求:在页面某个dom节点中遍历,找到目标dom节点,我们正常做法是利用选择器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),

用js在控制台打印九九乘法表

不管是打印什么样三角形九九乘法表,我们都应该找到有规律的地方,比如第一列的数字是什么规律,第一行的数字是什么规律,只要找到了共性,九九乘法表就很简单

JS数据结构与算法_链表

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

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

JS数据结构与算法_集合&字典

集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是:集合中的成员是无序的;集合中不允许相同成员存在,计算机中的集合与数学中集合的概念相同,有一些概念我们必须知晓:

js实现斐波那契数列的几种方式

斐波那契指的是这样一个数列:1、1、2、3、5、8、13、21、34......在数学上,斐波纳契数列以如下被以递归的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*);随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…

JS排序算法:记数排序

计数排序是一个非基于比较的[排序算法],该算法于1954年由 Harold H. Seward 提出。 它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围), 快于任何比较排序算法。

js实现生成任意长度的随机字符串

js生成任意长度的随机字符串,包含:数字,字母,特殊字符。实现原理:可以手动指定字符库及随机字符长度,利用Math.round()和Math.random()两个方法实现获取随机字符

点击更多...

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