PHP データ構造: 前方一致文字を効率的に見つけるためのトライ ツリーの使用

トライツリーは、前方一致する文字を効率的に見つけるために使用されるツリーデータ構造です。これは一連のノードで構成され、各ノードが文字を表します。文字列を挿入するには、ルート ノードから開始して、キャラクターのパスに沿ってノードを作成または検索します。検索する場合は、一文字ずつ下方向に検索して、一致する単語があるかどうかを確認します。この場合、Trie ツリーを使用して動物の名前を保存し、特定の接頭辞で始まる動物をすばやく見つけます。

PHP データ構造: 前方一致文字を効率的に見つけるためのトライ ツリーの使用

はじめに

トライ ツリーは、文字列を保存し、高速前方一致検索をサポートするために特別に使用されるツリー データ構造です。効率性とスペースの節約で知られており、自然言語処理、スペルチェック、ネットワークルーティングなどの分野で広く使用されています。

トライツリー構造

トライツリーは一連のノードで構成され、各ノードはキャラクターを表します。ルート ノードから始まり、ツリーの各レベルは文字列のプレフィックスを表します。各ノードは、そのプレフィックスで始まる異なるサフィックスを表す複数の子ノードを持つことができます。

挿入

トライ ツリーに文字列を挿入するには、次の手順を実行します。

function insert(TrieNode $root, $string) {
    $node = $root;
    for ($i = 0; $i < strlen($string); $i++) {
        $char = $string[$i];
        if (!isset($node->children[$char])) {
            $node->children[$char] = new TrieNode();
        }
        $node = $node->children[$char];
    }
    $node->isWord = true;
}

検索

特定の文字列がトライ ツリーに存在するかどうかを検索するには、次の手順を実行します。

function search(TrieNode $root, $string) {
    $node = $root;
    for ($i = 0; $i < strlen($string); $i++) {
        $char = $string[$i];
        if (!isset($node->children[$char])) {
            return false;
        }
        $node = $node->children[$char];
    }
    return $node->isWord;
}

実用的なケース

次のような動物の名前を含むリストがあるとします:

$animals = ['dog', 'cat', 'rabbit', 'turtle', 'bird'];

これらの動物の名前を保存するために Trie ツリーを作成します:

$root = new TrieNode();
foreach ($animals as $animal) {
    insert($root, $animal);
}

さて、Trie ツリーを使用して、一致する接頭辞を持つ動物を簡単に見つけることができます。たとえば、「d で始まる動物」を検索します:

$prefix = 'd';
$result = [];
foreach ($animals as $animal) {
    if (search($root, $prefix . $animal)) {
        $result[] = $animal;
    }
}
print_r($result);

出力結果は次のようになります:

Array
(
    [0] => dog
)

以上がPHP データ構造: 前方一致文字を効率的に見つけるためのトライ ツリーの使用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。