PHP資料結構：Trie樹的運用，有效率找出前綴匹配字符-php教程-PHP中文網

PHP資料結構：Trie樹的運用，有效率找出前綴匹配字符

WBOY

發布： 2024-06-02 18:00:01

原創

505 人瀏覽過

Trie 樹是一種樹狀資料結構，用於有效率地尋找前綴匹配字元。它由一系列節點組成，每個節點表示一個字元。要插入字串，從根節點開始，沿著字元的路徑建立或尋找節點。搜尋時，請依照字元逐層向下搜索，檢查是否有符合的單字。本案例中，Trie 樹用於儲存動物名稱，並能快速找到以特定前綴開頭的動物。

PHP資料結構：Trie樹的運用，有效率找出前綴匹配字符

PHP 資料結構：Trie 樹的運用，高效找出前綴匹配字元

##簡介

#Trie 樹是一種樹狀資料結構，專門用於儲存字串並支援快速前綴匹配查找。它以其效率和節省空間而著稱，廣泛應用於自然語言處理、拼字檢查和網路路由等領域。

Trie 樹的結構

Trie 樹由一系列節點組成，每個節點代表一個字元。從根節點開始，樹的每一層表示字串的一個前綴。每個節點可以有多個子節點，表示以該前綴為開頭的不同後綴。

插入

要將字串插入Trie 樹中，執行下列步驟：

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

登入後複製

搜尋

要搜尋Trie 樹中是否存在特定字串，執行以下步驟：

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

登入後複製

輸出結果將為：