您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 綜合知識

PHP 權重計算演算法：基於 Trie 字典樹的多模式匹配實作解析

編輯：PHP 綜合知識

前言

文本分類、關鍵詞提取、敏感詞過濾、全文檢索等場景，常需對大量文本進行多模式匹配並計算權重。本文深度解析一個基於 Trie 字典樹 (前綴樹) 實現的 PHP 權重計算類，支援批量導入關鍵詞表、高效匹配、多種輸出規則（如取最高權重），並探討其在分詞、詞頻統計、垃圾檢測中的擴展應用。

核心資料結構：Trie 節點設計

每個節點為陣列：[字元 => 子節點索引, ..., 'acc' => [關鍵詞ID列表]]


// 內部字典結構示意
$aDict = [
    0 => [ '中' => 1, '日' => 5 ],           // 根節點
    1 => [ '國' => 2, '文' => 9, 'acc' => [] ],
    2 => [ '人' => 3, 'acc' => [0] ],       // 節點 3 結束「中國人」，關鍵詞 ID 0
    3 => [ 'acc' => [0] ],
    5 => [ '本' => 6, 'acc' => [] ],
    6 => [ '語' => 7, 'acc' => [1] ],       // 「日本語」ID 1
    // ...
];

索引 0 為根節點。
新增關鍵詞時，逐字元遍歷/建立節點，終點節點 acc 陣列記錄該關鍵詞 ID（支援同一路徑對應多個 ID）。
空間複雜度：O(總字元數)，共享前綴極大壓縮儲存。

完整類別程式碼 (現代化重寫 PHP 7.4+)

<?php
declare(strict_types=1);

class TrieWeightMatcher {
    /** @var array> 字典樹節點池 */
    private array $dict = [0 => []];
    /** @var array 待匹配文本集合 */
    private array $items = [];
    /** @var array> 快取匹配結果 [itemIdx => [keywordId => count]] */
    private array $matchCache = [];
    /** @var array> 快取輸出結果 [itemIdx => [keywordId]] */
    private array $outputCache = [];
    private string $lastRule = '';

    /** 重置快取 */
    private function resetCache(): void {
        $this->matchCache = [];
        $this->outputCache = [];
    }

    /** 導入待匹配文本 */
    public function setItems(array $items): self {
        $this->items = $items;
        $this->resetCache();
        return $this;
    }

    /**
     * 批量建立字典
     * @param array $table 每行格式：'keyword1,keyword2|keyword3'，逗號分隔同權重組，管道分隔不同權重層級
     */
    public function buildDictionary(array $table): self {
        foreach ($table as $weightIdx => $line) {
            // 統一分隔符：管道→逗號
            $keywords = explode(',', str_replace('|', ',', $line));
            foreach ($keywords as $keyword) {
                $keyword = trim($keyword);
                if ($keyword !== '') {
                    $this->insertKeyword($keyword, $weightIdx);
                }
            }
        }
        $this->resetCache();
        return $this;
    }

    /** 插入單個關鍵詞到 Trie */
    private function insertKeyword(string $keyword, int $weightIdx): void {
        $node = 0;
        $len = mb_strlen($keyword, 'UTF-8');
        for ($i = 0; $i < $len; $i++) {
            $char = mb_substr($keyword, $i, 1, 'UTF-8');
            if (!isset($this->dict[$node][$char])) {
                $this->dict[$node][$char] = count($this->dict);
                $this->dict[] = []; // 新節點
            }
            $node = $this->dict[$node][$char];
        }
        // 終點節點記錄權重索引
        $this->dict[$node]['acc'][] = $weightIdx;
    }

    /**
     * 核心匹配演算法：單文本掃描
     * @return array 命中的權重索引列表（含重複，反映出現次數）
     */
    public function match(string $text): array {
        $node = 0;
        $matches = [];
        $len = mb_strlen($text, 'UTF-8');
        for ($i = 0; $i < $len; $i++) {
            $char = mb_substr($text, $i, 1, 'UTF-8');
            if (isset($this->dict[$node][$char])) {
                $node = $this->dict[$node][$char];
                if (isset($this->dict[$node]['acc'])) {
                    $matches = array_merge($matches, $this->dict[$node]['acc']);
                    // 可選：重疊匹配策略 - 此處重置節點以允許非重疊匹配
                    // 若需允許重疊（如「aaa」匹配「aa」兩次），移除下行
                    $node = 0;
                }
            } else {
                $node = 0; // 失配回根
            }
        }
        return $matches;
    }

    /**
     * 批量匹配所有文本
     * @return array> [itemIdx => [weightIdx => count]]
     */
    public function matchAll(): array {
        if (empty($this->items) || empty($this->dict)) return [];
        if (!empty($this->matchCache)) return $this->matchCache;

        foreach ($this->items as $idx => $text) {
            $matches = $this->match($text);
            $this->matchCache[$idx] = array_count_values($matches); // 統計各權重出現次數
        }
        return $this->matchCache;
    }

    /**
     * 獲取輸出結果
     * @param string $rule 'max' 取出現次數最多的權重；可擴展 'sum'、'first' 等
     * @return array> [itemIdx => [weightIdx...]]
     */
    public function getResult(string $rule = 'max'): array {
        if (empty($this->items) || empty($this->dict)) return [];
        if (!empty($this->outputCache) && $rule === $this->lastRule) {
            return $this->outputCache;
        }

        $allMatches = $this->matchAll();
        $result = [];
        foreach ($allMatches as $itemIdx => $weightCounts) {
            switch ($rule) {
                case 'max':
                    $maxCount = max($weightCounts);
                    $result[$itemIdx] = array_keys($weightCounts, $maxCount);
                    break;
                // 可擴展其他規則
                default:
                    $result[$itemIdx] = array_keys($weightCounts);
            }
        }
        $this->outputCache = $result;
        $this->lastRule = $rule;
        return $result;
    }
}

使用範例


// 1. 待分析文本
$items = [
    'chinaisbig',
    'whichisnot',
    'totalyrightforme',
];

// 2. 權重表：每行一個權重層級，逗號分隔同層關鍵詞
$table = [
    'china,is,small',        // 權重 0
    'china,big,me',          // 權重 1
    'china,is,big,which,not,me', // 權重 2
    'totaly,right,for,me',   // 權重 3
];

// 3. 執行
$matcher = new TrieWeightMatcher();
$matcher->setItems($items)->buildDictionary($table);
$result = $matcher->getResult('max');

print_r($result);
/*
輸出示意：
Array
(
    [0] => Array ( [0] => 1 )  // "chinaisbig" 命中權重 1 (china,big) 次數最多
    [1] => Array ( [0] => 0 )  // "whichisnot" 命中權重 0 (china,is,small) 中的 is
    [2] => Array ( [0] => 3 )  // "totalyrightforme" 命中權重 3
)
*/

演算法複雜度分析

階段	時間複雜度	空間複雜度
建立字典	O(關鍵詞總字元數)	O(字典節點數) ≈ O(關鍵詞總字元數)
單文本匹配	O(文本長度)	O(1) 額外空間
批量匹配 N 文本	O(所有文本總長度)	O(N × 平均匹配關鍵詞數)

優於暴力多模式匹配 O(N × M × L)，適合關鍵詞固定、文本流式處理場景。

擴展應用場景

中文分詞輔助：將詞典詞建立 Trie，正向最大匹配 (MM) 分詞，配合詞頻優化歧義。
敏感詞過濾：acc 存儲替換規則，匹配即替換為 ***，支援 DFA 模式無回溯。
垃圾郵件檢測：關鍵詞賦予權重分值，匹配後加總得分，超過閾值判定為垃圾。
實體識別：結合 AC 自動機 (Aho-Corasick) 在 Trie 基礎上添加 fail 指針，實現真正 O(N) 多模式匹配（本實現為簡化版，失配直接回根，非 AC 自動機）。

進階優化方向

AC 自動機：建立 fail 指針，失配時跳轉而非回根，保證嚴格 O(文本長度) 且支援重疊匹配。
Double-Array Trie：將 Trie 壓縮為兩個陣列 base[], check[]，極大降低記憶體佔用，提升緩存命中率（參考 Darts、PHP-Double-Array-Trie）。
持久化儲存：字典序列化為二進位檔案，啟動時 mmap 載入，避免每次重建。
並行處理：文本集合分片，多進程並行 matchAll()，主進程聚合結果。

結語

基於 Trie 字典樹的權重計算演算法，以 線性掃描時間、共享前綴空間 特性，成為多模式匹配的經典選擇。本文實現的簡化版 Trie 匹配器，已支援批量建表、多規則輸出，並易於擴展為 AC 自動機、Double-Array Trie 等工業級形態。適用於關鍵詞固定、文本量大、需高吞吐的文本分析、過濾、分類場景。