「労働者が自分の仕事をうまくやりたいなら、まず自分の道具を研ぎ澄まさなければなりません。」 - 孔子、「論語。陸霊公」
表紙 > プログラミング > Trieの紹介(プレフィックスツリー)

Trieの紹介(プレフィックスツリー)

2025-02-07に投稿しました
ブラウズ:864

Introduction to Trie (Prefix Tree)

a trie は、特にオートコンプリート、スペルチェック、IPルーティングなどのアプリケーションで、文字列を効率的に保存および検索するために使用されるツリーのようなデータ構造です。


Trieの重要なプロパティ:

  1. nodes :各ノードは文字を表します。
  2. root :ルートノードは空で、出発点として機能します。
  3. 子供:各ノードには、文字セットに応じて、最大26人の子供(小文字の英語文字の場合)以上です。
  4. 単語の終わりのマーカー:いくつかのノードは、単語の終わりを示すようにマークされています。

基本的なトリー操作:

1。挿入

単語を挿入するには、存在しない文字のトライを横断し、新しいノードを作成することが含まれます。

2。検索

検索は、ノードを横断することにより、トライに単語が存在するかどうかをチェックします。

3。プレフィックス検索

これは、Trieの単語が特定のプレフィックスで始まるかどうかをチェックします。


JavaScriptにおける基本的なTrieの実装:

class TrieNode {
    constructor() {
        this.children = {}; // Stores child nodes
        this.isEndOfWord = false; // Marks the end of a word
    }
}

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

    // Insert a word
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

高度なトリー操作:

1。単語を削除します

単語の削除には、再帰的なアプローチが含まれ、必要でないノードを削除します。

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth   1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

2。 指定されたプレフィックスから始まる単語の数をカウントします。


countwordswithprefix(prefix){ let node = this.root; for(let char of prefix){ if(!node.children [char])return 0; node = node.children [char]; } this._countwords(node); } _countwords(node){ count = node.isendofwordとしますか? 1:0; for count = this._countwords(node.children [char]); } 返品数; }

countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isEndOfWord ? 1 : 0;
    for (let char in node.children) {
        count  = this._countWords(node.children[char]);
    }
    return count;
}

プレフィックスが与えられた場合、それから始まるすべての単語を返します。

getWordSwithPrefix(プレフィックス){ let node = this.root; for(let char of prefix){ if(!node.children [char])return []; node = node.children [char]; } this._collectwords(node、prefix)を返します。 } _collectwords(node、prefix){ 結果= []; if(node.isendofword)results.push(prefix); for 結果= results.concat(this._collectwords(node.children [char]、prefix char)); } 結果を返します。 }


時間の複雑さ:
getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix   char));
    }

    return results;
}

挿入

:o(l)(l = wordの長さ)
  1. 検索:o(l)
  2. プレフィックス検索:o(l)
  3. delete :o(l)
  4. Trieのアプリケーション:

autocomplete Systems

(たとえば、検索バー、テキストエディター)。
  1. スペルチェッカー
  2. IPルーティング(最長のプレフィックスマッチング)。
  3. Word Games (例えば、boggle)。
  4. DNAシーケンスマッチング
リリースステートメント この記事は、https://dev.to/keshav___dev/introduction-trie-prefix-tree-5g07?1に再現されています。
最新のチュートリアル もっと>

免責事項: 提供されるすべてのリソースの一部はインターネットからのものです。お客様の著作権またはその他の権利および利益の侵害がある場合は、詳細な理由を説明し、著作権または権利および利益の証拠を提出して、電子メール [email protected] に送信してください。 できるだけ早く対応させていただきます。

Copyright© 2022 湘ICP备2022001581号-3