この記事では主に 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
トライ木とバイナリ検索ツリー 通常、トライ木の高さ 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 で合理化されたスタイルを実装する方法 (詳細なチュートリアル) Vue でカスタム グローバル コンポーネントを実行するには? 以上がJavaScript でのトライ接頭辞ツリーの詳細な解釈の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
トライ木と他のデータ構造の比較// 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
}
}ログイン後にコピー
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
