javascript trie前缀树的示例

日期：2020-05-11 栏目：程序人生浏览：次

引子

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

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

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

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

基本性质

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

程序实现

// 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;
 }
}

转载注明出处：http://www.heiqu.com/110.html

javascript trie前缀树的示例

相关推荐