問題由來

前些天工作中遇到一個(gè)問題：

有 60萬 條短消息記錄日志，每條約 50 字，5萬 關(guān)鍵詞，長度 2-8 字，絕大部分為中文。要求將這 60萬 條記錄中包含的關(guān)鍵詞全部提取出來并統(tǒng)計(jì)各關(guān)鍵詞的命中次數(shù)。

原始 - grep

設(shè)計(jì)

一開始接到任務(wù)的時(shí)候，我的小心思立刻轉(zhuǎn)了起來，日志 + 關(guān)鍵詞 + 統(tǒng)計(jì)，我沒有想到自己寫代碼實(shí)現(xiàn)，而是首先想到了 linux 下常用的日志統(tǒng)計(jì)命令 grep。

grep命令的用法不再多提，使用 grep 'keyword' | wc -l 可以很方便地進(jìn)行統(tǒng)計(jì)關(guān)鍵詞命中的信息條數(shù)，而php的 exec() 函數(shù)允許我們直接調(diào)用 linux 的 shell 命令，雖然這樣執(zhí)行危險(xiǎn)命令時(shí)會(huì)有安全隱患。

代碼

上偽代碼：

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

在一臺(tái)老機(jī)器上跑的，話說老機(jī)器效率真的差，跑了6小時(shí)。估計(jì)最新機(jī)器2-3小時(shí)吧，后面的優(yōu)化都使用的新機(jī)器，而且需求又有變動(dòng)，正文才剛剛開始。

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

進(jìn)化 - 正則

設(shè)計(jì)

交了差之后，第二天產(chǎn)品又提出了新的想法，說以后想把某數(shù)據(jù)源接入進(jìn)來，消息以數(shù)據(jù)流的形式傳遞，而不再是文件了。而且還要求了消息統(tǒng)計(jì)的實(shí)時(shí)性，一下把我想把數(shù)據(jù)寫到文件再統(tǒng)計(jì)的想法也推翻了，為了方案的可擴(kuò)展性，現(xiàn)在的統(tǒng)計(jì)對(duì)象不再是一個(gè)整體，而是要考慮拿n個(gè)單條的消息來匹配了。

這時(shí)，略懵的我只好祭出了最傳統(tǒng)的工具- 正則。正則的實(shí)現(xiàn)也不難，各個(gè)語言也都封裝好了正則匹配函數(shù)，重點(diǎn)是模式(pattern)的構(gòu)建。

當(dāng)然這里的模式構(gòu)建也不難，/keyword1|keword2|.../，用|將關(guān)鍵詞連接起來即可。

正則小坑

這里介紹兩個(gè)使用中遇到的小坑：

1.正則模式長度太長導(dǎo)致匹配失?。?/p>

PHP 的正則有回溯限制，以防止消耗掉所有的進(jìn)程可用堆棧, 最終導(dǎo)致 php 崩潰。太長的模式會(huì)導(dǎo)致 PHP 檢測到回溯過多，中斷匹配，經(jīng)測試默認(rèn)設(shè)置時(shí)最大模式長度為 32000 字節(jié) 左右。

php.ini 內(nèi) pcre.backtrack_limit 參數(shù)為最大回溯次數(shù)限制，默認(rèn)值為 1000000，修改或php.ini 或在腳本開始時(shí)使用ini_set(‘pcre.backtrack_limit', n); 將其設(shè)置為一個(gè)較大的數(shù)可以提高單次匹配最大模式長度。當(dāng)然也可以將關(guān)鍵詞分批統(tǒng)計(jì)（我用了這個(gè)=_=）。

2.模式中含有特殊字符導(dǎo)致大量warning：

匹配過程中發(fā)現(xiàn) PHP 報(bào)出大量 warning：unknown modifier 亂碼，仔細(xì)檢查發(fā)現(xiàn)關(guān)鍵詞中有/字符，可以使用preg_quote()函數(shù)過濾一遍關(guān)鍵詞即可。

代碼

上偽代碼：

$end = 0;
$step = 1500;
$pattern = array();
// 先將pattern 拆成多個(gè)小塊
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);
}

為了完成任務(wù)，硬著頭皮進(jìn)程跑了一夜。當(dāng)?shù)诙煳野l(fā)現(xiàn)跑了近十個(gè)小時(shí)的時(shí)候內(nèi)心是崩潰的。。。太慢了，完全達(dá)不到使用要求，這時(shí)，我已經(jīng)開始考慮改換方法了。

當(dāng)產(chǎn)品又改換了關(guān)鍵詞策略，替換了一些關(guān)鍵詞，要求重新運(yùn)行一遍，并表示還會(huì)繼續(xù)優(yōu)化關(guān)鍵詞時(shí)，我完全否定了現(xiàn)有方案。絕對(duì)不能用關(guān)鍵詞去匹配信息，這樣一條一條用全部關(guān)鍵詞去匹配，效率實(shí)在是不可忍受。

進(jìn)化，需求和實(shí)現(xiàn)的進(jìn)化

覺醒 - 拆詞

設(shè)計(jì)

我終于開始意識(shí)到要拿信息去關(guān)鍵詞里對(duì)比。如果我用關(guān)鍵詞為鍵建立一個(gè) hash 表，用信息里的詞去 hash 表里查找，如果查到就認(rèn)為匹配命中，這樣不是能達(dá)到 O(1) 的效率了么？

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

為什么叫拆詞呢，我考慮以蠻力將一句話拆分為所有可能的詞。如我是好人就可以拆成 我是、是好、好人、我是好、是好人、我是好人等詞，我的關(guān)鍵詞長度為 2-8，所以可拆詞個(gè)數(shù)會(huì)隨著句子長度迅速增加。不過，可以用標(biāo)點(diǎn)符號(hào)、空格、語氣詞（如的、是等）作為分隔將句子拆成小短語再進(jìn)行拆詞，會(huì)大大減少拆出的詞量。

其實(shí)分詞并沒有完整實(shí)現(xiàn)就被后一個(gè)方法替代了，只是一個(gè)極具實(shí)現(xiàn)可能的構(gòu)想，寫這篇文章時(shí)用偽代碼實(shí)現(xiàn)了一下，供大家參考，即使不用在匹配關(guān)鍵詞，用在其他地方也是有可能的。

代碼

$str_list = getStrList($msg);
foreach ($str_list as $str) {
    $keywords = getKeywords($str);
    foreach ($keywords as $keyword) {
        // 直接通過PHP數(shù)組的哈希實(shí)現(xiàn)來進(jìn)行快速查找
        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);
}

/**
 * 從短句中取出各個(gè)詞
 */
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 限制一下不要超過數(shù)組最大長度
        }
    }

    return $keywords;
}

結(jié)果

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

這里使用了 preg_split('/(?<!^)(?!$)/u', $msg) 是通過正則匹配到兩個(gè)字符之間的''來將兩個(gè)字符拆散，而兩個(gè)括號(hào)里的 (?<!^)(?!$) 是分別用來限定捕獲組不是第一個(gè)，也不是最后一個(gè)（不使用這兩個(gè)捕獲組限定符也是可以的，直接使用//作為模式會(huì)導(dǎo)致拆分結(jié)果在前后各多出一個(gè)空字符串項(xiàng)）。 捕獲組的概念和用法可見我之前的博客 PHP正則中的捕獲組與非捕獲組

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

最終沒有使用此方案是因?yàn)樗鼘?duì)句子要求較高，拆詞時(shí)的分隔符也不好確定，最重要的是它不夠優(yōu)雅。。。這個(gè)方法我不太想去實(shí)現(xiàn)，統(tǒng)計(jì)標(biāo)識(shí)和語氣詞等活顯得略為笨重，而且感覺拆出很多無意義的詞感覺效率浪費(fèi)得厲害。

覺醒，意識(shí)和思路的覺醒

終級(jí) - Trie樹

trie樹

于是我又來找谷哥幫忙了，搜索大量數(shù)據(jù)匹配，有人提出了 使用 trie 樹的方式，沒想到剛學(xué)習(xí)的 trie 樹的就派上了用場。我上上篇文章剛介紹了 trie 樹，在空間索引 - 四叉樹 里字典樹這一小節(jié)，大家可以查看一下。

當(dāng)然也為懶人復(fù)制了一遍我當(dāng)時(shí)的解釋(看過的可以跳過這一小節(jié)了)。

字典樹，又稱前綴樹或 trie 樹，是一種有序樹，用于保存關(guān)聯(lián)數(shù)組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節(jié)點(diǎn)中，而是由節(jié)點(diǎn)在樹中的位置決定。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串，而根節(jié)點(diǎn)對(duì)應(yīng)空字符串。

我們可以類比字典的特性：我們?cè)谧值淅锿ㄟ^拼音查找晃(huang)這個(gè)字的時(shí)候，我們會(huì)發(fā)現(xiàn)它的附近都是讀音為huang的，可能是聲調(diào)有區(qū)別，再往前翻，我們會(huì)看到讀音前綴為huan的字，再往前，是讀音前綴為hua的字... 取它們的讀音前綴分別為 h qu hua huan huang。我們?cè)诓檎視r(shí)，根據(jù) abc...xyz 的順序找到h前綴的部分，再根據(jù) ha he hu找到 hu 前綴的部分...最后找到 huang，我們會(huì)發(fā)現(xiàn)，越往后其讀音前綴越長，查找也越精確，這種類似于字典的樹結(jié)構(gòu)就是字典樹，也是前綴樹。

設(shè)計(jì)

那么 trie 樹怎么實(shí)現(xiàn)關(guān)鍵字的匹配呢? 這里以一幅圖來講解 trie 樹匹配的過程。

其中要點(diǎn)：

構(gòu)造trie樹

將關(guān)鍵詞用上面介紹的preg_split()函數(shù)拆分為單個(gè)字符。如科學(xué)家就拆分為科、學(xué)、家三個(gè)字符。在最后一個(gè)字符后添加一個(gè)特殊字符 `，此字符作為一個(gè)關(guān)鍵詞的結(jié)尾（圖中的粉紅三角），以此字符來標(biāo)識(shí)查到了一個(gè)關(guān)鍵詞（不然，我們不知道匹配到科、學(xué)兩個(gè)字符時(shí)算不算匹配成功）。檢查根部是否有第一個(gè)字符(科)節(jié)點(diǎn)，如果有了此節(jié)點(diǎn)，到步驟4。 如果還沒有，在根部添加值為科的節(jié)點(diǎn)。依次檢查并添加學(xué)、家 兩個(gè)節(jié)點(diǎn)。在結(jié)尾添加`節(jié)點(diǎn)，并繼續(xù)下一個(gè)關(guān)鍵詞的插入。

匹配

然后我們以 這位科學(xué)家很了不起！為例來發(fā)起匹配。

• 首先我們將句子拆分為單個(gè)字符 這、位、...；
• 從根查詢第一個(gè)字符這，并沒有以這個(gè)字符開頭的關(guān)鍵詞，將字符“指針”向后移，直到找到根下有的字符節(jié)點(diǎn)科;
• 接著在節(jié)點(diǎn)科下尋找值為 學(xué)節(jié)點(diǎn)，找到時(shí)，結(jié)果子樹的深度已經(jīng)到了2，關(guān)鍵詞的最短長度是2，此時(shí)需要在學(xué)結(jié)點(diǎn)下查找是否有`，找到意味著匹配成功，返回關(guān)鍵詞，并將字符“指針”后移，如果找不到則繼續(xù)在此結(jié)點(diǎn)下尋找下一個(gè)字符。
• 如此遍歷，直到最后，返回所有匹配結(jié)果。

代碼

完整代碼我已經(jīng)放到了GitHub上：Trie-GitHub-zhenbianshu，這里放上核心。

首先是數(shù)據(jù)結(jié)構(gòu)樹結(jié)點(diǎn)的設(shè)計(jì)，當(dāng)然它也是重中之重：

$node = array(
    'depth' => $depth, // 深度，用以判斷已命中的字?jǐn)?shù)
    'next' => array(
        $val => $node, // 這里借用php數(shù)組的哈希底層實(shí)現(xiàn)，加速子結(jié)點(diǎn)的查找
        ...
    ),
);

然后是樹構(gòu)建時(shí)子結(jié)點(diǎn)的插入：

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

最后是查詢時(shí)的操作：

// 這里也可以使用一個(gè)全局變量來存儲(chǔ)已匹配到的字符，以替換$matched
private function query($node, $words, &$matched) {
        $word = array_shift($words);
        if (isset($node['next'][$word])) {
            // 如果存在對(duì)應(yīng)子結(jié)點(diǎn)，將它放到結(jié)果集里
            array_push($matched, $word);
            // 深度到達(dá)最短關(guān)鍵詞時(shí)，即可判斷是否到詞尾了
            if ($node['next'] > 1 && isset($node['next'][$word]['next']['`'])) {
                return true;
            }
            return $this->query($node['next'][$word], $words, $matched);
        } else {
            $matched = array();
            return false;
        }
    }

結(jié)果

結(jié)果當(dāng)然是喜人的，如此匹配，處理一千條數(shù)據(jù)只需要3秒左右。找了 Java 的同事試了下，Java 處理一千條數(shù)據(jù)只需要1秒。

這里來分析一下為什么這種方法這么快：

• 正則匹配：要用所有的關(guān)鍵詞去信息里匹配匹配次數(shù)是 key_len * msg_len，當(dāng)然正則會(huì)進(jìn)行優(yōu)化，但基礎(chǔ)這樣，再優(yōu)化效率可想而知。
• 而 trie 樹效率最差的時(shí)候是 msg_len * 9(最長關(guān)鍵詞長度 + 1個(gè)特殊字符)次 hash 查找，即最長關(guān)鍵詞類似 AAA，信息內(nèi)容為 AAA...時(shí)，而這種情況的概率可想而知。

至此方法的優(yōu)化到此結(jié)束，從每秒鐘匹配 10 個(gè)，到 300 個(gè)，30 倍的性能提升還是巨大的。

終級(jí)，卻不一定是終極

他徑 - 多進(jìn)程

設(shè)計(jì)

匹配方法的優(yōu)化結(jié)束了，開頭說的優(yōu)化到十分鐘以內(nèi)的目標(biāo)還沒有實(shí)現(xiàn)，這時(shí)候就要考慮一些其他方法了。

我們一提到高效，必然想到的是 并發(fā)，那么接下來的優(yōu)化就要從并發(fā)說起。PHP 是單線程的（雖然也有不好用的多線程擴(kuò)展），這沒啥好的解決辦法，并發(fā)方向只好從多進(jìn)程進(jìn)行了。

那么一個(gè)日志文件，用多個(gè)進(jìn)程怎么讀呢？這里當(dāng)然也提供幾個(gè)方案：

進(jìn)程內(nèi)添加日志行數(shù)計(jì)數(shù)器，各個(gè)進(jìn)程支持傳入?yún)?shù) n，進(jìn)程只處理第 行數(shù) % n = n 的日志，這種 hack 的反向分布式我已經(jīng)用得很熟練了，哈哈。

這種方法需要進(jìn)程傳參數(shù)，還需要每個(gè)進(jìn)程都分配讀取整個(gè)日志的的內(nèi)存，而且也不夠優(yōu)雅。

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

此方法的缺點(diǎn)就是不靈活，想換一下進(jìn)程數(shù)時(shí)需要重新切分文件。

使用 Redis 的 list 隊(duì)列臨時(shí)存儲(chǔ)日志，開啟多個(gè)進(jìn)程消費(fèi)隊(duì)列。

此方法需要另外向 Redis 內(nèi)寫入數(shù)據(jù)，多了一個(gè)步驟，但它擴(kuò)展靈活，而且代碼簡單優(yōu)雅。

最終使用了第三種方式來進(jìn)行。

結(jié)果

這種方式雖然也會(huì)有瓶頸，最后應(yīng)該會(huì)落在 Redis 的網(wǎng)絡(luò) IO 上。我也沒有閑心開 n 個(gè)進(jìn)程去挑戰(zhàn)公司 Redis 的性能，運(yùn)行 10 個(gè)進(jìn)程三四分鐘就完成了統(tǒng)計(jì)。即使再加上 Redis 寫入的耗時(shí)，10分鐘以內(nèi)也妥妥的。

一開始產(chǎn)品對(duì)匹配速度已經(jīng)有了小時(shí)級(jí)的定位了，當(dāng)我 10 分鐘就拿出了新的日志匹配結(jié)果，看到產(chǎn)品驚訝的表情，心里也是略爽的，哈哈~

他徑，也能幫你走得更遠(yuǎn)

總結(jié)

解決問題的方法有很多種，我認(rèn)為在解決各種問題之前，要了解很多種知識(shí)，即使只知道它的作用。就像一個(gè)工具架，你要先把工具盡量擺得多，才能在遇到問題時(shí)選取一個(gè)最合適的。接著當(dāng)然要把這些工具用是純熟了，這樣才能使用它們?nèi)ソ鉀Q一些怪異問題。

工欲善其事，必先利其器，要想解決性能問題，掌握系統(tǒng)級(jí)的方法還略顯不夠，有時(shí)候換一種數(shù)據(jù)結(jié)構(gòu)或算法，效果可能會(huì)更好。感覺自己在這方面還略顯薄弱，慢慢加強(qiáng)吧，各位也共勉。

以上就是詳解PHP優(yōu)化巨量關(guān)鍵詞的匹配的詳細(xì)內(nèi)容，更多關(guān)于PHP優(yōu)化巨量關(guān)鍵詞的匹配的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論