PHP data structure: Use of Trie tree to efficiently find prefix matching characters

Trie tree is a tree data structure used to efficiently find prefix matching characters. It consists of a series of nodes, each node represents a character. To insert a string, start at the root node and create or find nodes along the character's path. When searching, search downwards character by character to check whether there is a matching word. In this case, a Trie tree is used to store animal names and quickly find animals starting with a specific prefix.

PHP data structure: Use of Trie tree to efficiently search for prefix matching characters

Introduction

Trie tree is a tree data structure specially designed to store strings and support fast prefix matching lookup. Known for its efficiency and space saving, it is widely used in areas such as natural language processing, spell checking, and network routing.

Trie tree structure

Trie tree consists of a series of nodes, each node represents a character. Starting from the root node, each level of the tree represents a prefix of the string. Each node can have multiple child nodes, representing different suffixes starting with that prefix.

Insertion

To insert a string into a Trie, perform the following steps:

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;
}

Search

To search whether a specific string exists in the Trie tree, perform the following steps:

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;
}

Practical case

Suppose we have a list containing animal names, as follows :

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

We create a Trie tree to store these animal names:

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

Now, we can use the Trie tree to easily find animals with matching prefixes, for example, search for animals starting with "d":

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

The output will be:

Array
(
    [0] => dog
)

The above is the detailed content of PHP data structure: Use of Trie tree to efficiently find prefix matching characters. For more information, please follow other related articles on the PHP Chinese website!