詳解PHP優化巨量關鍵詞的匹配

問題由來

前些天工作中遇到一個問題：

有 60萬 條短消息記錄日志，每條約 50 字，5萬 關鍵詞，長度 2-8 字，絕大部分為中文。要求將這 60萬 條記錄中包含的關鍵詞全部提取出來並統計各關鍵詞的命中次數。

原始 – grep

設計

一開始接到任務的時候，我的小心思立刻轉瞭起來，日志 + 關鍵詞 + 統計，我沒有想到自己寫代碼實現，而是首先想到瞭 linux 下常用的日志統計命令 grep。

grep命令的用法不再多提，使用 grep ‘keyword’ | wc -l 可以很方便地進行統計關鍵詞命中的信息條數，而php的 exec() 函數允許我們直接調用 linux 的 shell 命令，雖然這樣執行危險命令時會有安全隱患。

代碼

上偽代碼：

foreach ($word_list as $keyword) {
    $count = intval(exec("grep '{$keyword}' file.log | wc -l"));
    record($keyword, $count);
}

在一臺老機器上跑的，話說老機器效率真的差，跑瞭6小時。估計最新機器2-3小時吧，後面的優化都使用的新機器，而且需求又有變動，正文才剛剛開始。

原始，原始在想法和方法。

進化 – 正則

設計

交瞭差之後，第二天產品又提出瞭新的想法，說以後想把某數據源接入進來，消息以數據流的形式傳遞，而不再是文件瞭。而且還要求瞭消息統計的實時性，一下把我想把數據寫到文件再統計的想法也推翻瞭，為瞭方案的可擴展性，現在的統計對象不再是一個整體，而是要考慮拿n個單條的消息來匹配瞭。

這時，略懵的我隻好祭出瞭最傳統的工具- 正則。正則的實現也不難，各個語言也都封裝好瞭正則匹配函數，重點是模式(pattern)的構建。

當然這裡的模式構建也不難，/keyword1|keword2|…/，用|將關鍵詞連接起來即可。

正則小坑

這裡介紹兩個使用中遇到的小坑：

1.正則模式長度太長導致匹配失敗：

PHP 的正則有回溯限制，以防止消耗掉所有的進程可用堆棧, 最終導致 php 崩潰。太長的模式會導致 PHP 檢測到回溯過多，中斷匹配，經測試默認設置時最大模式長度為 32000 字節 左右。

php.ini 內 pcre.backtrack_limit 參數為最大回溯次數限制，默認值為 1000000，修改或php.ini 或在腳本開始時使用ini_set(‘pcre.backtrack_limit’, n); 將其設置為一個較大的數可以提高單次匹配最大模式長度。當然也可以將關鍵詞分批統計（我用瞭這個=_=）。

2.模式中含有特殊字符導致大量warning：

匹配過程中發現 PHP 報出大量 warning：unknown modifier 亂碼，仔細檢查發現關鍵詞中有/字符，可以使用preg_quote()函數過濾一遍關鍵詞即可。

代碼

上偽代碼：

$end = 0;
$step = 1500;
$pattern = array();
// 先將pattern 拆成多個小塊
while ($end < count($word_list)) {
    $tmp_arr = array_slice($word_list, $end, $step);
    $end += $step;
    $item = implode('|', $tmp_arr);
    $pattern[] = preg_quote($item);
}

$content = file_get_contents($log_file);
$lines = explode("\n", $content);
foreach ($lines as $line) {
    // 使用各小塊pattern分別匹配
    for ($i = 0; $i < count($pattern); $i++) {
        preg_match_all("/{$pattern[$i]}/", $line, $match);
    }
    $match = array_unique(array_filter($match));
    dealResult($match);
}

為瞭完成任務，硬著頭皮進程跑瞭一夜。當第二天我發現跑瞭近十個小時的時候內心是崩潰的。。。太慢瞭，完全達不到使用要求，這時，我已經開始考慮改換方法瞭。

當產品又改換瞭關鍵詞策略，替換瞭一些關鍵詞，要求重新運行一遍，並表示還會繼續優化關鍵詞時，我完全否定瞭現有方案。絕對不能用關鍵詞去匹配信息，這樣一條一條用全部關鍵詞去匹配，效率實在是不可忍受。

進化，需求和實現的進化

覺醒 – 拆詞

設計

我終於開始意識到要拿信息去關鍵詞裡對比。如果我用關鍵詞為鍵建立一個 hash 表，用信息裡的詞去 hash 表裡查找，如果查到就認為匹配命中，這樣不是能達到 O(1) 的效率瞭麼？

可是一條短消息，我如何把它拆分為剛好的詞去匹配呢，分詞？分詞也是需要時間的，而且我的關鍵詞都是些無語義的詞，構建詞庫、使用分詞工具又是很大的問題，最終我想到 拆詞。

為什麼叫拆詞呢，我考慮以蠻力將一句話拆分為所有可能的詞。如我是好人就可以拆成 我是、是好、好人、我是好、是好人、我是好人等詞，我的關鍵詞長度為 2-8，所以可拆詞個數會隨著句子長度迅速增加。不過，可以用標點符號、空格、語氣詞（如的、是等）作為分隔將句子拆成小短語再進行拆詞，會大大減少拆出的詞量。

其實分詞並沒有完整實現就被後一個方法替代瞭，隻是一個極具實現可能的構想，寫這篇文章時用偽代碼實現瞭一下，供大傢參考，即使不用在匹配關鍵詞，用在其他地方也是有可能的。

代碼

$str_list = getStrList($msg);
foreach ($str_list as $str) {
    $keywords = getKeywords($str);
    foreach ($keywords as $keyword) {
        // 直接通過PHP數組的哈希實現來進行快速查找
        if (isset($word_list[$keyword])) {
            record($keyword);
        }
    }
}
/**
 * 從消息中拆出短句子
 */
function getStrList($msg) {
    $str_list = array();
    $seperators = array('，', '。', '的', ...);

    $words = preg_split('/(?<!^)(?!$)/u', $msg);
    $str = array();
    foreach ($words as $word) {
        if (in_array($word, $seperators)) {
            $str_list[] = $str;
            $str = array();
        } else {
            $str[] = $word;
        }
    }

    return array_filter($str_list);
}

/**
 * 從短句中取出各個詞
 */
function getKeywords($str) {
    if (count($str) < 2) {
        return array();
    }

    $keywords = array();
    for ($i = 0; $i < count($str); $i++) {
        for ($j = 2; $j < 9; $j++) {
            $keywords[] = array_slice($str, $i, $j); // todo 限制一下不要超過數組最大長度
        }
    }

    return $keywords;
}

結果

我們知道一個 utf-8 的中文字符要占用三個字節，為瞭拆分出包含中英文的每一個字符，使用簡單的 split() 函數是做不到的。

這裡使用瞭 preg_split(‘/(?<!^)(?!$)/u’, $msg) 是通過正則匹配到兩個字符之間的”來將兩個字符拆散，而兩個括號裡的 (?<!^)(?!$) 是分別用來限定捕獲組不是第一個，也不是最後一個（不使用這兩個捕獲組限定符也是可以的，直接使用//作為模式會導致拆分結果在前後各多出一個空字符串項）。 捕獲組的概念和用法可見我之前的博客 PHP正則中的捕獲組與非捕獲組

由於沒有真正實現，也不知道效率如何。估算每個短句長度約為 10 字左右時，每條短消息約50字左右，會拆出 200 個詞。雖然它會拆出很多無意義的詞，但我相信效率絕不會低，由於其 hash 的高效率，甚至我覺得會可能比終極方法效率要高。

最終沒有使用此方案是因為它對句子要求較高，拆詞時的分隔符也不好確定，最重要的是它不夠優雅。。。這個方法我不太想去實現，統計標識和語氣詞等活顯得略為笨重，而且感覺拆出很多無意義的詞感覺效率浪費得厲害。

覺醒，意識和思路的覺醒

終級 – Trie樹

trie樹

於是我又來找谷哥幫忙瞭，搜索大量數據匹配，有人提出瞭 使用 trie 樹的方式，沒想到剛學習的 trie 樹的就派上瞭用場。我上上篇文章剛介紹瞭 trie 樹，在空間索引 – 四叉樹 裡字典樹這一小節，大傢可以查看一下。

當然也為懶人復制瞭一遍我當時的解釋(看過的可以跳過這一小節瞭)。

字典樹，又稱前綴樹或 trie 樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。

我們可以類比字典的特性：我們在字典裡通過拼音查找晃(huang)這個字的時候，我們會發現它的附近都是讀音為huang的，可能是聲調有區別，再往前翻，我們會看到讀音前綴為huan的字，再往前，是讀音前綴為hua的字… 取它們的讀音前綴分別為 h qu hua huan huang。我們在查找時，根據 abc…xyz 的順序找到h前綴的部分，再根據 ha he hu找到 hu 前綴的部分…最後找到 huang，我們會發現，越往後其讀音前綴越長，查找也越精確，這種類似於字典的樹結構就是字典樹，也是前綴樹。

設計

那麼 trie 樹怎麼實現關鍵字的匹配呢? 這裡以一幅圖來講解 trie 樹匹配的過程。

其中要點：

構造trie樹

將關鍵詞用上面介紹的preg_split()函數拆分為單個字符。如科學傢就拆分為科、學、傢三個字符。在最後一個字符後添加一個特殊字符 `，此字符作為一個關鍵詞的結尾（圖中的粉紅三角），以此字符來標識查到瞭一個關鍵詞（不然，我們不知道匹配到科、學兩個字符時算不算匹配成功）。檢查根部是否有第一個字符(科)節點，如果有瞭此節點，到步驟4。 如果還沒有，在根部添加值為科的節點。依次檢查並添加學、傢 兩個節點。在結尾添加`節點，並繼續下一個關鍵詞的插入。

匹配

然後我們以 這位科學傢很瞭不起！為例來發起匹配。

• 首先我們將句子拆分為單個字符 這、位、…；
• 從根查詢第一個字符這，並沒有以這個字符開頭的關鍵詞，將字符“指針”向後移，直到找到根下有的字符節點科;
• 接著在節點科下尋找值為 學節點，找到時，結果子樹的深度已經到瞭2，關鍵詞的最短長度是2，此時需要在學結點下查找是否有`，找到意味著匹配成功，返回關鍵詞，並將字符“指針”後移，如果找不到則繼續在此結點下尋找下一個字符。
• 如此遍歷，直到最後，返回所有匹配結果。

代碼

完整代碼我已經放到瞭GitHub上：Trie-GitHub-zhenbianshu，這裡放上核心。

首先是數據結構樹結點的設計，當然它也是重中之重：

$node = array(
    'depth' => $depth, // 深度，用以判斷已命中的字數
    'next' => array(
        $val => $node, // 這裡借用php數組的哈希底層實現，加速子結點的查找
        ...
    ),
);

然後是樹構建時子結點的插入：

// 這裡要往節點內插入子節點，所以將它以引用方式傳入
private function insert(&$node, $words) {
         if (empty($words)) {
            return;
        }
        $word = array_shift($words);
        // 如果子結點已存在，向子結點內繼續插入
        if (isset($node['next'][$word])) {
            $this->insert($node['next'][$word], $words);
        } else {
            // 子結點不存在時，構造子結點插入結果
            $tmp_node = array(
                'depth' => $node['depth'] + 1,
                'next' => array(),
            );
            $node['next'][$word] = $tmp_node;
            $this->insert($node['next'][$word], $words);
        }
    }

最後是查詢時的操作：

// 這裡也可以使用一個全局變量來存儲已匹配到的字符，以替換$matched
private function query($node, $words, &$matched) {
        $word = array_shift($words);
        if (isset($node['next'][$word])) {
            // 如果存在對應子結點，將它放到結果集裡
            array_push($matched, $word);
            // 深度到達最短關鍵詞時，即可判斷是否到詞尾瞭
            if ($node['next'] > 1 && isset($node['next'][$word]['next']['`'])) {
                return true;
            }
            return $this->query($node['next'][$word], $words, $matched);
        } else {
            $matched = array();
            return false;
        }
    }

結果

結果當然是喜人的，如此匹配，處理一千條數據隻需要3秒左右。找瞭 Java 的同事試瞭下，Java 處理一千條數據隻需要1秒。

這裡來分析一下為什麼這種方法這麼快：

• 正則匹配：要用所有的關鍵詞去信息裡匹配匹配次數是 key_len * msg_len，當然正則會進行優化，但基礎這樣，再優化效率可想而知。
• 而 trie 樹效率最差的時候是 msg_len * 9(最長關鍵詞長度 + 1個特殊字符)次 hash 查找，即最長關鍵詞類似 AAA，信息內容為 AAA…時，而這種情況的概率可想而知。

至此方法的優化到此結束，從每秒鐘匹配 10 個，到 300 個，30 倍的性能提升還是巨大的。

終級，卻不一定是終極

他徑 – 多進程

設計

匹配方法的優化結束瞭，開頭說的優化到十分鐘以內的目標還沒有實現，這時候就要考慮一些其他方法瞭。

我們一提到高效，必然想到的是 並發，那麼接下來的優化就要從並發說起。PHP 是單線程的（雖然也有不好用的多線程擴展），這沒啥好的解決辦法，並發方向隻好從多進程進行瞭。

那麼一個日志文件，用多個進程怎麼讀呢？這裡當然也提供幾個方案：

進程內添加日志行數計數器，各個進程支持傳入參數 n，進程隻處理第 行數 % n = n 的日志，這種 hack 的反向分佈式我已經用得很熟練瞭，哈哈。

這種方法需要進程傳參數，還需要每個進程都分配讀取整個日志的的內存，而且也不夠優雅。

使用 linux 的 split -l n file.log output_pre 命令，將文件分割為每份為 n 行的文件，然後用多個進程去讀取多個文件。

此方法的缺點就是不靈活，想換一下進程數時需要重新切分文件。

使用 Redis 的 list 隊列臨時存儲日志，開啟多個進程消費隊列。

此方法需要另外向 Redis 內寫入數據，多瞭一個步驟，但它擴展靈活，而且代碼簡單優雅。

最終使用瞭第三種方式來進行。

結果

這種方式雖然也會有瓶頸，最後應該會落在 Redis 的網絡 IO 上。我也沒有閑心開 n 個進程去挑戰公司 Redis 的性能，運行 10 個進程三四分鐘就完成瞭統計。即使再加上 Redis 寫入的耗時，10分鐘以內也妥妥的。

一開始產品對匹配速度已經有瞭小時級的定位瞭，當我 10 分鐘就拿出瞭新的日志匹配結果，看到產品驚訝的表情，心裡也是略爽的，哈哈~

他徑，也能幫你走得更遠

總結

解決問題的方法有很多種，我認為在解決各種問題之前，要瞭解很多種知識，即使隻知道它的作用。就像一個工具架，你要先把工具盡量擺得多，才能在遇到問題時選取一個最合適的。接著當然要把這些工具用是純熟瞭，這樣才能使用它們去解決一些怪異問題。

工欲善其事，必先利其器，要想解決性能問題，掌握系統級的方法還略顯不夠，有時候換一種數據結構或算法，效果可能會更好。感覺自己在這方面還略顯薄弱，慢慢加強吧，各位也共勉。

以上就是詳解PHP優化巨量關鍵詞的匹配的詳細內容，更多關於PHP優化巨量關鍵詞的匹配的資料請關註WalkonNet其它相關文章！

推薦閱讀：

• 詳解PHP調用Go服務的正確方式
• php使用正則驗證密碼字段的復雜強度 原創
• python 共現矩陣的實現代碼
• php中str_replace替換實例講解
• C++實現LeetCode(648.替換單詞)