溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下PHP優化巨量關鍵詞匹配的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
前些天工作中遇到一個問題：
有 60萬 條短消息記錄日志，每條約 50 字，5萬 關鍵詞，長度 2-8 字，絕大部分為中文。要求將這 60萬 條記錄中包含的關鍵詞全部提取出來并統計各關鍵詞的命中次數。
一開始接到任務的時候，我的小心思立刻轉了起來，日志 + 關鍵詞 + 統計，我沒有想到自己寫代碼實現，而是首先想到了 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 樹，是一種有序樹，用于保存關聯數組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。
我們可以類比字典的特性：我們在字典里通過拼音查找晃(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分鐘以內也妥妥的。
以上是“PHP優化巨量關鍵詞匹配的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
