トライアルゴリズム || Javascriptを使用したオートコンプリート機能

導入

トライはプレフィックス ツリーとも呼ばれ、効率的な情報検索に使用される特殊なツリーベースのデータ構造です。

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

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< word.length; i++) {
            if (!head.children[word[i]]) {
                head.children[word[i]] = new Node();
            }
            head = head.children[word[i]];
        }
        head.end = true;
    }

    search(word){
        let current = this.root;

        for (let i = 0; i < word.length; i++) {
            if (!current.children[word[i]]) {
                return false;
            }
            current = current.children[word[i]]
        }

        return true;
    }

    autoComplete(word) {
        let current = this.root;

        for (let i = 0; i< word.length; i++) {
            if (!current.children[word[i]]) {
                return false;
            }
            current = current.children[word[i]];
        }
        if (Object.keys(current.children).length === 1) {
            console.log('Please Type More...');
            return;
        }
        console.log('children =---> ', 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
*/

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

以上がトライアルゴリズム || Javascriptを使用したオートコンプリート機能の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。