Trie – drzewo prefiksowe, autouzupełnianie, filtr spamu, benchmark vs array

Trie (drzewo prefiksowe) to struktura danych zoptymalizowana pod wyszukiwanie słów i prefiksów. Zamiast porównywać każde słowo ze słownikiem, Trie przechodzi po literach – każdy węzeł to jedna litera, każda ścieżka od korzenia to słowo. Autouzupełnianie w wyszukiwarce, walidacja SKU, wykrywanie spamu – Trie pojawia się w e-commerce częściej niż myślisz. Implementuję od zera w PHP z praktycznymi przykładami.

Czym jest Trie?

Wyobraź sobie słownik słów: „cat”, „car”, „card”, „care”, „bat”. W zwykłej tablicy szukasz każdego słowa liniowo – O(n). W Trie każda litera to węzeł. Szukasz „car” – c → a → r – trzy kroki niezależnie od rozmiaru słownika. Złożoność: O(m) gdzie m = długość szukanego słowa.

Implementacja węzła i Trie

<?php

declare(strict_types=1);

class TrieNode
{
    /** @var array<string, TrieNode> */
    public array $children = [];
    public bool $isEndOfWord = false;
    public mixed $value = null; // opcjonalne dane powiązane ze słowem

    public function hasChild(string $char): bool
    {
        return isset($this->children[$char]);
    }

    public function getChild(string $char): ?TrieNode
    {
        return $this->children[$char] ?? null;
    }

    public function addChild(string $char): TrieNode
    {
        $this->children[$char] = new TrieNode();
        return $this->children[$char];
    }
}

class Trie
{
    private TrieNode $root;

    public function __construct()
    {
        $this->root = new TrieNode();
    }

    // Wstaw słowo - O(m) gdzie m = długość słowa
    public function insert(string $word, mixed $value = null): void
    {
        $node = $this->root;
        $word = mb_strtolower($word);

        for ($i = 0; $i < mb_strlen($word); $i++) {
            $char = mb_substr($word, $i, 1);

            if (!$node->hasChild($char)) {
                $node->addChild($char);
            }

            $node = $node->getChild($char);
        }

        $node->isEndOfWord = true;
        $node->value       = $value;
    }

    // Szukaj dokładnego dopasowania - O(m)
    public function search(string $word): bool
    {
        $node = $this->findNode(mb_strtolower($word));
        return $node !== null && $node->isEndOfWord;
    }

    // Sprawdź czy istnieje słowo zaczynające się od prefiksu - O(m)
    public function startsWith(string $prefix): bool
    {
        return $this->findNode(mb_strtolower($prefix)) !== null;
    }

    // Pobierz wartość powiązaną ze słowem
    public function getValue(string $word): mixed
    {
        $node = $this->findNode(mb_strtolower($word));
        return ($node && $node->isEndOfWord) ? $node->value : null;
    }

    // Znajdź wszystkie słowa z danym prefiksem - autouzupełnianie
    public function autocomplete(string $prefix, int $limit = 10): array
    {
        $prefix = mb_strtolower($prefix);
        $node   = $this->findNode($prefix);

        if ($node === null) {
            return [];
        }

        $results = [];
        $this->dfs($node, $prefix, $results, $limit);
        return $results;
    }

    private function findNode(string $word): ?TrieNode
    {
        $node = $this->root;

        for ($i = 0; $i < mb_strlen($word); $i++) {
            $char = mb_substr($word, $i, 1);

            if (!$node->hasChild($char)) {
                return null;
            }

            $node = $node->getChild($char);
        }

        return $node;
    }

    // DFS po drzewie - zbiera wszystkie słowa od danego węzła
    private function dfs(TrieNode $node, string $current, array &$results, int $limit): void
    {
        if (count($results) >= $limit) {
            return;
        }

        if ($node->isEndOfWord) {
            $results[] = ['word' => $current, 'value' => $node->value];
        }

        foreach ($node->children as $char => $child) {
            $this->dfs($child, $current . $char, $results, $limit);
        }
    }

    // Usuń słowo - O(m)
    public function delete(string $word): bool
    {
        return $this->deleteNode($this->root, mb_strtolower($word), 0);
    }

    private function deleteNode(TrieNode $node, string $word, int $depth): bool
    {
        if ($depth === mb_strlen($word)) {
            if (!$node->isEndOfWord) {
                return false;
            }
            $node->isEndOfWord = false;
            return empty($node->children);
        }

        $char = mb_substr($word, $depth, 1);

        if (!$node->hasChild($char)) {
            return false;
        }

        $shouldDeleteChild = $this->deleteNode($node->getChild($char), $word, $depth + 1);

        if ($shouldDeleteChild) {
            unset($node->children[$char]);
            return empty($node->children) && !$node->isEndOfWord;
        }

        return false;
    }
}

Autouzupełnianie wyszukiwarki produktów

<?php

declare(strict_types=1);

// Budowanie indeksu produktów w Trie
$searchTrie = new Trie();

$products = [
    ['id' => 1,  'sku' => 'WIDGET-PRO',   'name' => 'Widget Pro'],
    ['id' => 2,  'sku' => 'WIDGET-LITE',  'name' => 'Widget Lite'],
    ['id' => 3,  'sku' => 'GADGET-X500',  'name' => 'Gadget X500'],
    ['id' => 4,  'sku' => 'GADGET-X1000', 'name' => 'Gadget X1000'],
    ['id' => 5,  'sku' => 'CABLE-USB-C',  'name' => 'Kabel USB-C 2m'],
    ['id' => 6,  'sku' => 'CABLE-HDMI',   'name' => 'Kabel HDMI 4K'],
    ['id' => 7,  'sku' => 'PHONE-CASE-A', 'name' => 'Etui na telefon model A'],
    ['id' => 8,  'sku' => 'CHARGER-65W',  'name' => 'Ładowarka 65W GaN'],
];

// Indeksuj po nazwie i SKU
foreach ($products as $product) {
    // Indeksuj całą nazwę
    $searchTrie->insert($product['name'], $product);

    // Indeksuj każde słowo z nazwy osobno (dla wyszukiwania po słowie)
    foreach (explode(' ', $product['name']) as $word) {
        if (strlen($word) >= 3) {
            $searchTrie->insert($word, $product);
        }
    }

    // Indeksuj SKU
    $searchTrie->insert($product['sku'], $product);
}

// Autouzupełnianie - "wid" → sugeruje Widget Pro, Widget Lite
$suggestions = $searchTrie->autocomplete('wid', limit: 5);
foreach ($suggestions as $s) {
    echo "Sugestia: {$s['word']} (ID: {$s['value']['id']})\n";
}
// Sugestia: widget lite (ID: 2)
// Sugestia: widget pro (ID: 1)

// Szybkie sprawdzenie czy SKU istnieje - walidacja importu
$skusToCheck = ['WIDGET-PRO', 'WIDGET-XXX', 'CABLE-USB-C'];
foreach ($skusToCheck as $sku) {
    $exists = $searchTrie->search($sku);
    echo "{$sku}: " . ($exists ? 'istnieje' : 'nie istnieje') . "\n";
}

Trie jako filtr spamu – lista zakazanych słów

<?php

declare(strict_types=1);

class SpamFilter
{
    private Trie $trie;

    public function __construct(array $bannedWords)
    {
        $this->trie = new Trie();
        foreach ($bannedWords as $word) {
            $this->trie->insert($word, true);
        }
    }

    public function containsSpam(string $text): bool
    {
        $words = preg_split('/\s+/', mb_strtolower($text));

        foreach ($words as $word) {
            // Usuń interpunkcję
            $clean = preg_replace('/[^a-z0-9ąćęłńóśźż]/u', '', $word);

            if ($this->trie->search($clean)) {
                return true;
            }
        }

        return false;
    }

    public function censorText(string $text): string
    {
        $words = explode(' ', $text);

        return implode(' ', array_map(function(string $word) {
            $clean = preg_replace('/[^a-z0-9ąćęłńóśźż]/ui', '', mb_strtolower($word));

            if ($this->trie->search($clean)) {
                return str_repeat('*', mb_strlen($word));
            }

            return $word;
        }, $words));
    }
}

$filter = new SpamFilter(['spam', 'reklama', 'kliknij', 'wygraj']);
echo $filter->containsSpam('Kliknij tutaj żeby wygrać nagrodę') ? "SPAM\n" : "OK\n";
// SPAM

echo $filter->censorText('To jest reklama produktu');
// To jest ******* produktu

Porównanie wydajności – Trie vs in_array vs array_search

<?php

// Benchmark dla 100 000 SKU i 10 000 wyszukiwań

$skus = array_map(fn($i) => 'SKU-' . str_pad((string) $i, 8, '0', STR_PAD_LEFT), range(1, 100000));

// Trie - O(m) per wyszukiwanie
$trie = new Trie();
foreach ($skus as $sku) {
    $trie->insert($sku);
}

// Test wyszukiwania
$searchTerms = array_rand(array_flip($skus), 10000);

$start = microtime(true);
foreach ($searchTerms as $sku) {
    $trie->search($sku);
}
$trieTime = (microtime(true) - $start) * 1000;

// in_array - O(n) per wyszukiwanie
$start = microtime(true);
foreach ($searchTerms as $sku) {
    in_array($sku, $skus, true);
}
$inArrayTime = (microtime(true) - $start) * 1000;

// isset na tablicy asocjacyjnej - O(1) hash lookup
$skusMap = array_flip($skus);
$start = microtime(true);
foreach ($searchTerms as $sku) {
    isset($skusMap[$sku]);
}
$issetTime = (microtime(true) - $start) * 1000;

echo "Trie:      {$trieTime}ms\n";        // ~15ms
echo "in_array:  {$inArrayTime}ms\n";     // ~8000ms (O(n) per lookup!)
echo "isset:     {$issetTime}ms\n";        // ~2ms (hash table O(1))

// Wniosek: dla exact match - isset na tablicy asocjacyjnej jest najszybsze
// Trie błyszczy przy prefix search i autocomplete - czego isset nie oferuje

Kiedy Trie, kiedy inna struktura?

Podsumowanie

Trie to wyspecjalizowana struktura danych która błyszczy przy prefix search i autouzupełnianiu. W PHP masz do dyspozycji gotowe rozwiązania jak Elasticsearch dla wyszukiwania pełnotekstowego – Trie warto znać gdy potrzebujesz lekką, in-process strukturę bez zewnętrznych zależności. Klasyczny przykład użycia: walidacja setek tysięcy SKU podczas importu lub dynamiczne autouzupełnianie bez trafienia do bazy przy każdym keystroke.