導入

接頭辞ツリーとしても知られるトライは、効率的な情報検索に使用される特殊なツリーベースのデータ構造です。

これは、文字列内の検索と前方一致を伴うユースケースに特に役立ちます。

1. トライ アルゴリズムについてお話しすると、あなたはこのアルゴリズムに興味があるかもしれませんし、興味がないかもしれません

2. しかし、これを使用して オートコンプリート アルゴリズムを作成できると言いたいのですが。これを学ぶともっと興奮するでしょう。

このアルゴリズムの使用例

1.オートコンプリート:

a.トライは、オートコンプリート機能を実装するために検索エンジンやテキスト エディタでよく使用されます。
b.入力を開始すると、アプリケーションは入力した接頭辞に基づいて候補を提案します。

2.スペルチェッカー:

a. Try を使用してスペル チェッカーを実装できます。単語がトライに存在しない場合は、スペルが間違っている可能性があります。
b.トライでは、類似した単語を見つけて修正を提案することもできます。

3. IPルーティング:

a.トライはルーティング テーブルを保存するためにルーターで使用されます。
b.ルーターはトライを使用して最長のプレフィックスを照合し、パケットの次のホップを決定します。

4.文字列の効率的な保存と検索:

a.共有プレフィックスが多数ある文字列のデータセットがある場合、トライではこれらの文字列を個別に保存するよりも少ないスペースで保存できます。
b. 検索操作も効率的で、時間の複雑さは検索する文字列の長さに比例します。

class Node {
    constructor() {
        this.end = false;
        this.children = {}
    }
}

class Trie {
    constructor() {
        this.root = new Node ();
    }

    insert(word) {
        let head = this.root;

        for (let i = 0; i ', current.children);

        console.log('Possible Auto Complete Values are --->');
        for (let key in current.children) {
            console.log('---> ', word key);
        }
    }
}

const test = new Trie();
test.insert('ant');
test.insert('any');
console.log(test.search('ant'));
console.log(test.search('any'));
console.log(test.search('anj'));
test.autoComplete('an')
/*
true
true
false
children =--->  {
  t: Node { end: true, children: {} },
  y: Node { end: true, children: {} }
}
Possible Auto Complete Values are --->
--->  ant
--->  any
*/

ご不明な点やご質問がございましたら、お気軽にお問い合わせください。