PHP-Datenstruktur: Verwendung des Trie-Baums, um Präfix-passende Zeichen effizient zu finden

Der Trie-Baum ist eine Baumdatenstruktur, mit der Präfix-Übereinstimmungszeichen effizient gefunden werden können. Es besteht aus einer Reihe von Knoten, wobei jeder Knoten ein Zeichen darstellt. Um eine Zeichenfolge einzufügen, beginnen Sie am Stammknoten und erstellen oder suchen Sie Knoten entlang des Zeichenpfads. Suchen Sie bei der Suche Zeichen für Zeichen nach unten, um zu prüfen, ob ein passendes Wort vorhanden ist. In diesem Fall wird ein Trie-Baum verwendet, um Tiernamen zu speichern und Tiere, die mit einem bestimmten Präfix beginnen, schnell zu finden.

PHP-Datenstruktur: Verwendung des Trie-Baums zur effizienten Suche nach Präfix-Übereinstimmungszeichen

Einführung

Der Trie-Baum ist eine Baumdatenstruktur, die speziell zum Speichern von Zeichenfolgen und zur Unterstützung einer schnellen Suche nach Präfix-Übereinstimmungen verwendet wird. Es ist für seine Effizienz und Platzersparnis bekannt und wird häufig in Bereichen wie der Verarbeitung natürlicher Sprache, der Rechtschreibprüfung und dem Netzwerkrouting eingesetzt.

Trie-Baumstruktur

Der Trie-Baum besteht aus einer Reihe von Knoten, wobei jeder Knoten ein Zeichen darstellt. Ausgehend vom Wurzelknoten stellt jede Ebene des Baums ein Präfix der Zeichenfolge dar. Jeder Knoten kann mehrere untergeordnete Knoten haben, die unterschiedliche Suffixe darstellen, beginnend mit diesem Präfix.

Einfügen

Um eine Zeichenfolge in einen Trie-Baum einzufügen, führen Sie die folgenden Schritte aus:

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

Suchen

Um zu suchen, ob eine bestimmte Zeichenfolge im Trie-Baum vorhanden ist, führen Sie die folgenden Schritte aus:

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

Praktischer Fall

Angenommen, wir haben eine Liste mit Tiernamen wie folgt:

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

Wir erstellen einen Trie-Baum, um diese Tiernamen zu speichern:

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

Jetzt können wir den Trie-Baum verwenden, um leicht Tiere mit passenden Präfixen zu finden, z Suchen Sie beispielsweise nach „Tiere beginnend mit d“:

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

Das Ausgabeergebnis lautet:

Array
(
    [0] => dog
)

Das obige ist der detaillierte Inhalt vonPHP-Datenstruktur: Verwendung des Trie-Baums, um Präfix-passende Zeichen effizient zu finden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!