ホームページ > 記事 > ウェブフロントエンド > JavaScript でのトライ接頭辞ツリーの詳細な解釈

JavaScript でのトライ接頭辞ツリーの詳細な解釈

亚连オリジナル: 2018-06-09 10:21:221680ブラウズ

この記事では主に JavaScript のトライワード検索ツリーの例を紹介し、トライの概念と実装について詳しく紹介します。興味のある方は参考にしてください

トライツリー (from)単語検索) は、接頭辞単語、単語検索ツリー、辞書ツリーとも呼ばれ、ツリー構造、ハッシュツリーの変形、および高速検索に使用されるマルチフォークツリー構造です。その利点は、不必要な文字列比較を最小限に抑え、ハッシュテーブルよりもクエリ効率が高いことです。

Trie の核となるアイデアは、空間を時間と交換することです。文字列の共通プレフィックスを使用してクエリ時間のオーバーヘッドを削減し、効率を向上させます。

Trie ツリーにも欠点があります。文字と数字のみを処理すると仮定すると、各ノードには少なくとも 52+10 の子ノードがあります。メモリを節約するには、リンクされたリストまたは配列を使用できます。 JS 配列は動的であり、最適化が組み込まれているため、JS では配列を直接使用します。

基本プロパティ

ルートノードには文字が含まれず、ルートノードを除くすべての子ノードには文字が1つ含まれます

ルートノードから特定のノードまで。パス上を通過する文字は接続されており、これはノードに対応する文字列です。Trie の挿入メソッドでは、各ノードのすべてのサブノードに異なる文字が含まれます。辞書ツリーは主に単語頻度統計に使用されるため、numPass、numEnd を含む多くのノード属性がありますが、非常に重要な属性です。
最適化

さて、各メソッドでは c=-48 という演算が行われていますが、実際には、数字、大文字、小文字の間に他の文字があり、不必要なスペースの無駄が発生します

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

Test

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

トライ木と他のデータ構造の比較

トライ木とバイナリ検索ツリー

二分探索ツリーは、私たちが最初に接触するツリー構造であるはずです。データサイズがnの場合、二分探索ツリーの挿入、検索、および削除操作の時間計算量は通常わずかO(log)であることがわかっています。 n ) の場合、最悪の場合、ツリー全体のすべてのノードが 1 つの子ノードのみを持ち、線形リストに縮退します。このとき、挿入、検索、および削除の操作の時間計算量は O(n) になります。

通常、トライ木の高さ n は検索文字列の長さ m よりもはるかに大きいため、検索操作の時間計算量は通常 O(m) であり、最悪の場合の時間計算量は O(n ）。トライツリーでの最悪の場合の検索が二分探索ツリーよりも高速であることが簡単にわかります。

この記事のトライツリーは例として文字列を使用しています。実際、キーが浮動小数点数の場合、トライツリー全体が非常に長くなり、ノードが長くなる可能性があります。可読性が低いため、この場合、データを保存するためにトライツリーを使用するのは適切ではありません。二分探索ツリーではこの問題は発生しません。

トライツリーとハッシュテーブル

ハッシュの衝突の問題を考えてみましょう。通常、ハッシュテーブルの複雑さは O(1) であると言われますが、実際、これは完全に近いハッシュテーブルの複雑さです。さらに、ハッシュ関数自体が必要とすることも考慮する必要があります。検索文字列を走査するための計算量は O(m ) です。異なるキーが「同じ位置」にマッピングされている場合 (クローズドハッシュを考慮すると、この「同じ位置」は通常のリンクリストで置き換えることができます)、検索の複雑さは「同じ位置」番号の下のノードの数に依存します。したがって、最悪の場合、ハッシュテーブルが一方向のリンクリストになる可能性もあります。トライツリーは、キーのアルファベット順に従って簡単にソートできます (ツリー全体が順番に一度走査されます)。これは、ほとんどのハッシュテーブルとは異なります (通常、ハッシュテーブルには異なるキーのシーケンスに対する機能がありません)。

理想的な状況では、ハッシュテーブルは O(1) の速度でターゲットに迅速にヒットします。テーブルが非常に大きく、ディスク上に配置する必要がある場合、ハッシュテーブルの検索アクセスは 1 回だけ行う必要があります。理想的な状況ではありますが、トライツリーによってアクセスされるディスクの数はノードの深さと同じである必要があります。多くの場合、トライツリーはハッシュテーブルよりも多くのスペースを必要とします。1 つのノードが 1 つの文字を保存する状況を考慮すると、文字列を保存するときにそれを別のブロックとして保存する方法はありません。トライツリーのノード圧縮により、この問題を大幅に軽減できます。これについては後で説明します。

トライツリーの改善

ビットワイズトライ(Bitwise Trie)

原理は通常のトライツリーと似ていますが、通常のトライツリーに格納される最小単位は文字ですが、ビットワイズトライはビットのみを格納する点が異なります。ビットデータのアクセスは、CPU 命令によって 1 回直接実装されます。バイナリデータの場合、理論的には通常のトライ木よりも高速です。

ノード圧縮。

ブランチ圧縮: 安定したトライツリー、基本的に検索および読み取り操作の場合、一部のブランチを圧縮できます。たとえば、前の図の右端のブランチの inn は、通常のサブツリーとして存在せずに、ノード「inn」に直接圧縮できます。基数ツリーは、トライツリーが深すぎるという問題を解決するために、この原理に基づいています。

ノードマッピングテーブル: この方法は、トライツリー内のノードの各状態について、状態の総数が多数の繰り返しによってほぼ完全に決定されている可能性がある場合にも使用されます。要素が数値である多次元配列。配列 (Triple Array Trie など) で表現されるため、追加のマッピングテーブルが導入されますが、Trie ツリー自体を格納するスペースのオーバーヘッドは小さくなります。

プレフィックスツリーの応用

プレフィックスツリーはやはり理解しやすく、その応用範囲も非常に広いです。

(1) 文字列の高速検索

辞書ツリーのクエリ時間計算量はO(logL)、Lは文字列の長さです。したがって、効率は依然として比較的高いです。ディクショナリツリーはハッシュテーブルよりも効率的です。

(2) 文字列の並べ替え

上の図から、単語が並べ替えられ、最初にアルファベット順にたどられていることが簡単にわかります。不要な共通部分文字列を減らします。

(3) 最長の共通接頭辞

inn と int の最長の共通接頭辞は in です。辞書ツリーを文字 n までたどると、この時点でこれらの単語の共通接頭辞は in になります。

(4) 接頭辞を自動的に照合して接尾辞を表示します

辞書や検索エンジンを使用する場合、「appl」と入力すると、接頭辞が「appl」のものが自動的に表示されます。前述したように、辞書ツリーは残りの接尾辞をたどって表示するだけで済みます。

上記は私があなたのためにまとめたものです。

Vue で合理化されたスタイルを実装する方法 (詳細なチュートリアル)