Structure de données PHP : utilisation de l'arbre Trie pour trouver efficacement les caractères correspondant au préfixe

L'arbre Trie est une structure de données arborescente utilisée pour trouver efficacement les caractères correspondant au préfixe. Il se compose d'une série de nœuds, chaque nœud représente un personnage. Pour insérer une chaîne, commencez par le nœud racine et créez ou recherchez des nœuds le long du chemin du caractère. Lors de la recherche, recherchez vers le bas caractère par caractère pour vérifier s'il existe un mot correspondant. Dans ce cas, un arbre de Trie est utilisé pour stocker les noms d'animaux et trouver rapidement des animaux commençant par un préfixe spécifique.

Structure de données PHP : Utilisation de l'arbre Trie pour trouver efficacement les caractères correspondant au préfixe

Introduction

L'arbre Trie est une structure de données arborescente spécialement utilisée pour stocker des chaînes et prendre en charge la recherche rapide de correspondance de préfixe. Connu pour son efficacité et son gain de place, il est largement utilisé dans des domaines tels que le traitement du langage naturel, la vérification orthographique et le routage réseau.

Structure de l'arbre Trie

L'arbre Trie se compose d'une série de nœuds, chaque nœud représente un personnage. En partant du nœud racine, chaque niveau de l'arborescence représente un préfixe de la chaîne. Chaque nœud peut avoir plusieurs nœuds enfants, représentant différents suffixes commençant par ce préfixe.

Insérer

Pour insérer une chaîne dans un arbre Trie, effectuez les étapes suivantes :

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

Recherche

Pour rechercher si une chaîne spécifique existe dans l'arbre Trie, effectuez les étapes suivantes :

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

Cas pratique

Supposons que nous ayons une liste contenant des noms d'animaux comme suit :

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

Nous créons un arbre Trie pour stocker ces noms d'animaux :

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

Maintenant, nous pouvons utiliser l'arbre Trie pour trouver facilement des animaux avec des préfixes correspondants, par exemple Par exemple, recherchez « Animaux commençant par d » :

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

Le résultat de sortie sera :

Array
(
    [0] => dog
)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!