Struktur data PHP: Penggunaan pepohon Trie untuk mencari aksara padanan awalan dengan cekap

Pokok Trie ialah struktur data pokok yang digunakan untuk mencari aksara padanan awalan dengan cekap. Ia terdiri daripada satu siri nod, setiap nod mewakili watak. Untuk memasukkan rentetan, mulakan pada nod akar dan buat atau cari nod di sepanjang laluan watak. Semasa mencari, cari ke bawah aksara demi aksara untuk menyemak sama ada terdapat perkataan yang sepadan. Dalam kes ini, pokok Trie digunakan untuk menyimpan nama haiwan dan mencari haiwan dengan cepat bermula dengan awalan tertentu.

struktur data PHP: Penggunaan pepohon Trie untuk mencari aksara padanan awalan dengan cekap

Pengenalan

Pepohon trie ialah struktur data pepohon yang digunakan khas untuk menyimpan rentetan dan sokongan carian pantas padanan Terkenal dengan kecekapan dan penjimatan ruang, ia digunakan secara meluas dalam bidang seperti pemprosesan bahasa semula jadi, semakan ejaan dan penghalaan rangkaian.

Struktur pokok trie

Pokok trie terdiri daripada satu siri nod, setiap nod mewakili aksara. Bermula dari nod akar, setiap peringkat pokok mewakili awalan rentetan. Setiap nod boleh mempunyai berbilang nod anak, mewakili akhiran berbeza bermula dengan awalan itu.

Sisipkan

Untuk memasukkan rentetan ke dalam pokok Trie, lakukan langkah berikut:

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

Cari

Untuk mencari sama ada rentetan tertentu wujud dalam pokok Trie, lakukan langkah berikut:

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

Kes praktikal

Andaikan kita mempunyai senarai yang mengandungi nama haiwan seperti berikut:

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

Kami mencipta pokok Trie untuk menyimpan nama haiwan ini:

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

Kini, kami boleh menggunakan pokok Trie untuk mencari haiwan dengan awalan yang sepadan dengan mudah, untuk contoh, cari " Haiwan bermula dengan d":

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

Hasil keluarannya ialah:

Array
(
    [0] => dog
)

Atas ialah kandungan terperinci Struktur data PHP: Penggunaan pepohon Trie untuk mencari aksara padanan awalan dengan cekap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!