文字列検索についての知識はすべて忘れてください - 試してみるとびっくりします!

Try データ構造の概要

トライはプレフィックス ツリーとも呼ばれ、文字列の保存と取得に使用される効率的なツリー状のデータ構造です。これは、文字列検索、プレフィックス マッチング、オートコンプリート機能を含むタスクに特に役立ちます。

発音：

• それは単一音節の単語です
• 最後の「ie」は、「see」や「tree」と同様に、長い「e」音として発音されます
• 「パイ」や「ダイ」と韻を踏みません。 この発音は、他の似たような単語と区別するのに役立ち、データ検索操作との関連性を強調します。

いつトライを使用するか

トライは、次のことが必要なシナリオに最適です。

1. プレフィックスベースの検索を迅速に実行します
2. オートコンプリート機能を実装する
3. スペルチェック用に単語の辞書を保存します
4. 共通のプレフィックスを持つ文字列を効率的に保存および取得する ## トライの視覚化

「猫」、「車」、「犬」という単語を含むトライを視覚化してみましょう:

       root
     /   |   \
    c    d    ...
   /     |
  a      o
 / \     |
t   r    g

各ノードは文字を表し、ルート ノードからリーフ ノードまでのパスが完全な単語を形成します。

JavaScript でのトライの実装

JavaScript で基本的なトライ構造を実装してみましょう:

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

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

  // Insert a word into the trie
  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;
  }

  // Search for a word in the trie
  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();

// Insert words
trie.insert("apple");
trie.insert("app");
trie.insert("banana");

console.log(trie.search("apple"));    // Output: true
console.log(trie.search("app"));      // Output: true
console.log(trie.search("appl"));     // Output: false
console.log(trie.startsWith("app"));  // Output: true
console.log(trie.startsWith("ban"));  // Output: true
console.log(trie.startsWith("cat"));  // Output: false

コードの説明

1. class TrieNode: トライ内のノードを表します。各ノードには次のものがあります:: 子ノードを格納するオブジェクト: 単語の終わりをマークするブール値のフラグ
2. クラストリー：メソッドを備えたメイントライ構造：
   • 挿入: トライに単語を追加します
   • 検索：trie
   に単語が存在するかどうかをチェックします
   • Startswith：Trieの単語が指定されたプレフィックスで始まるかどうかを確認
3. メソッドはトライを横断し、存在しない文字の新しいノードを作成し、最後のノードを単語の終わりとしてマークします。
メソッドは、指定された単語のパスに沿ってトライを走査し、単語全体が見つかって完全な単語としてマークされているかどうかを返します。
メソッドは、完全な単語であるかどうかにかかわらず、指定されたプレフィックスがトライに存在するかどうかのみに似ていますが、チェックします。
時間と空間の複雑さ

時間の複雑さ：

• 挿入：o（m）、mは単語の長さ
  • 検索：o（m）、ここでmは単語の長さ
  • startswith：o（m）、ここでmはプレフィックスの長さ
  空間の複雑さ：o（n * m）、nは単語の数、mは単語の平均長です
試行は、特に一般的な接頭辞を備えた単語の大規模なセットを扱う場合、文字列関連操作に優れたパフォーマンスを提供します。これらは高速なルックアップとプレフィックス マッチングを提供するため、オートコンプリート システム、IP ルーティング テーブル、辞書実装などのさまざまなアプリケーションで非常に役立ちます。

このチュートリアルが気に入った場合は、@turckaliciousのX/Twitterで私をフォローしてください。この記事は、Wonderfall (https://wonderfall.xyz) の助けを借りて作成されました。Wonderfall は、調査、執筆、反復作業を迅速に行うのに役立つ、AI を活用した対話型ドキュメント エディターです。

以上が文字列検索についての知識はすべて忘れてください - 試してみるとびっくりします!の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。