前些天工作中遇到一個問題:
有60萬個短訊息記錄日誌,每條約50 字,5萬關鍵字,長度2-8 字,絕大部分為中文。要求將這 60萬 筆記錄中包含的關鍵字全部提取出來並統計各關鍵字的命中次數。
本文完整介紹了我的實作方式,看我如何將需要運行十小時的任務優化到十分鐘以內。雖然實作語言是 PHP,但本文介紹的更多的思想,應該可以給大家一些幫助。
一開始接到任務的時候,我的小心思立刻轉了起來,日誌+ 關鍵字+ 統計,我沒有想到自己寫程式碼實現,而是先想到了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)的建構。
當然這裡的模式建構也不難,##/keyword優化巨量關鍵字的匹配|keword2|.../,用##|
將關鍵字連接起來即可。
正規小坑
pcre.backtrack_limit 參數為最大回溯次數限制,預設值為優化巨量關鍵字的匹配000000,修改或
#php.ini# 或在腳本開始時使用
ini_set('pcre.backtrack_limit', n); 將其設為一個較大的數字可以提高單次符合最大模式長度。當然也可以將關鍵字分批統計(我用了這個=_=)。
unknown modifier 亂碼<strong></strong>#,仔細檢查發現關鍵字中有
/字符,可以使用
preg_quote()函數過濾一遍關鍵字即可。
$end = 0; $step = 優化巨量關鍵字的匹配500; $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); }為了完成任務,硬著頭皮進程跑了一夜。當第二天我發現跑了將近十個小時的時候內心是崩潰的。 。 。太慢了,完全達不到使用要求,這時,我已經開始考慮改換方法了。
當產品又改換了關鍵字策略,替換了一些關鍵字,要求重新運行一遍,並表示還會繼續優化關鍵字時,我完全否定了現有方案。絕對不能用關鍵字去匹配訊息,這樣一條一條用全部關鍵字去匹配,效率實在是不可忍受。
進化,需求和實現的進化覺醒– 拆詞
可是一則短訊息,我如何把它拆分為剛好好的字去配對呢,分詞?分詞也是需要時間的,而且我的關鍵字都是些無語意的詞,建構詞庫、使用分詞工具又是很大的問題,最後我想到
拆詞 为什么叫拆词呢,我考虑以蛮力将一句话拆分为 其实分词并没有完整实现就被后一个方法替代了,只是一个极具实现可能的构想,写这篇文章时用伪代码实现了一下,供大家参考,即使不用在匹配关键词,用在其他地方也是有可能的。 我们知道一个 这里使用了 由于没有真正实现,也不知道效率如何。估算每个短句长度约为 優化巨量關鍵字的匹配0 字左右时,每条短消息约50字左右,会拆出 200 个词。虽然它会拆出很多无意义的词,但我相信效率绝不会低,由于其 hash 的高效率,甚至我觉得会可能比终极方法效率要高。 最终没有使用此方案是因为它对句子要求较高,拆词时的分隔符也不好确定,最重要的是它不够优雅。。。这个方法我不太想去实现,统计标识和语气词等活显得略为笨重,而且感觉拆出很多无意义的词感觉效率浪费得厉害。 觉醒,意识和思路的觉醒 于是我又来找谷哥帮忙了,搜索大量数据匹配,有人提出了 使用 trie 树的方式,没想到刚学习的 trie 树的就派上了用场。我上上篇文章刚介绍了 trie 树,在空间索引 – 四叉树 里 当然也为懒人复制了一遍我当时的解释(看过的可以跳过这一小节了)。 字典树,又称前缀树或 trie 树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。 我们可以类比字典的特性:我们在字典里通过拼音查找晃( 那么 trie 树怎么实现关键字的匹配呢? 这里以一幅图来讲解 trie 树匹配的过程。 其中要点: 将关键词用上面介绍的 在最后一个字符后添加一个特殊字符 检查根部是否有第一个字符(科)节点,如果有了此节点,到 依次检查并添加 在结尾添加 然后我们以 首先我们将句子拆分为单个字符 从根查询第一个字符 接着在节点 如此遍历,直到最后,返回所有匹配结果。 完整代码我已经放到了GitHub上:Trie-GitHub-zhenbianshu,这里放上核心。 首先是数据结构树结点的设计,当然它也是重中之重: 然后是树构建时子结点的插入: 最后是查询时的操作: 结果当然是喜人的,如此匹配,处理一千条数据只需要3秒左右。找了 Java 的同事试了下,Java 处理一千条数据只需要優化巨量關鍵字的匹配秒。 这里来分析一下为什么这种方法这么快: 正则匹配:要用所有的关键词去信息里匹配匹配次数是 而 trie 树效率最差的时候是 至此方法的优化到此结束,从每秒钟匹配 優化巨量關鍵字的匹配0 个,到 300 个,30 倍的性能提升还是巨大的。 终级,却不一定是终极 匹配方法的优化结束了,开头说的优化到十分钟以内的目标还没有实现,这时候就要考虑一些其他方法了。 我们一提到高效,必然想到的是 那么一个日志文件,用多个进程怎么读呢?这里当然也提供几个方案: 在進程內新增日誌行數計數器,各個進程支援傳入參數n,進程只處理第行數 使用linux 的 使用 Redis 的 list 佇列暫存日誌,開啟多個行程消費佇列。此方法需要另外向 Redis 內寫入數據,多了一個步驟,但它擴展靈活,而且程式碼簡單優雅。 最終使用了第三種方式來進行。 這種方式雖然也會有瓶頸,最後應該會落在 Redis 的網路 IO 上。我也沒有閒心開 n 個進程去挑戰公司 Redis 的效能,運行 優化巨量關鍵字的匹配0 個進程三四分鐘就完成了統計。即使再加上 Redis 寫入的耗時,優化巨量關鍵字的匹配0分鐘以內也妥妥的。 一開始產品對匹配速度已經有了小時的定位了,當我優化巨量關鍵字的匹配0 分鐘就拿出了新的日誌匹配結果,看到產品驚訝的表情,心裡也是略爽的,哈哈~ 他徑,也能幫你走得更遠 解決問題的方法有很多種,我認為在解決各種在問題之前,要先了解很多知識,即使只知道它的作用。就像一個工具架,你要先把工具盡量擺得多,才能在遇到問題時選取一個最適合的。接著當然要把這些工具用是純熟了,這樣才能用它們去解決一些怪異問題。 工欲善其事,必先利其器,要解決效能問題,掌握系統層級的方法還略顯不夠,有時候換一種資料結構或演算法,效果可能會更好。感覺自己在這方面還略顯薄弱,慢慢加強吧,各位也共勉。 。
<strong>所有可能</strong>的
词。如(我是好人)
就可以拆成(我是、是好、好人、我是好、是好人、我是好人)
等词,我的关键词长度为 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('/(?
是通过正则匹配到两个字符之间的''
来将两个字符拆散,而两个括号里的 (?
是分别用来限定捕获组不是第一个,也不是最后一个(不使用这两个捕获组限定符也是可以的,直接使用//
作为模式会导致拆分结果在前后各多出一个空字符串项)。 捕获组的概念和用法可见我之前的博客 PHP正则中的捕获组与非捕获组终级 – Trie树
trie树
字典树
这一小节,大家可以查看一下。huang
)这个字的时候,我们会发现它的附近都是读音为huang
的,可能是声调有区别,再往前翻,我们会看到读音前缀为huan
的字,再往前,是读音前缀为hua
的字… 取它们的读音前缀分别为 h qu hua huan huang
。我们在查找时,根据 abc...xyz
的顺序找到h
前缀的部分,再根据 ha he hu
找到 hu
前缀的部分…最后找到 huang
,我们会发现,越往后其读音前缀越长,查找也越精确,这种类似于字典的树结构就是字典树,也是前缀树。设计
构造trie树
preg_split()
函数拆分为单个字符。如科学家
就拆分为科、学、家
三个字符。`
,此字符作为一个关键词的结尾(图中的粉红三角),以此字符来标识查到了一个关键词(不然,我们不知道匹配到科、学
两个字符时算不算匹配成功)。步骤4
。 如果还没有,在根部添加值为科
的节点。学、家
两个节点。`
节点,并继续下一个关键词的插入。匹配
<strong>这位科学家很了不起</strong>!
为例来发起匹配。
这、位
、...
;这
,并没有以这个字符开头的关键词,将字符“指针”向后移,直到找到根下有的字符节点科
;科
下寻找值为 学
节点,找到时,结果子树的深度已经到了2,关键词的最短长度是2,此时需要在学
结点下查找是否有`
,找到意味着匹配成功,返回关键词,并将字符“指针”后移,如果找不到则继续在此结点下寻找下一个字符。代码
$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'] + 優化巨量關鍵字的匹配,
'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'] > 優化巨量關鍵字的匹配 && isset($node['next'][$word]['next']['`'])) {
return true;
}
return $this->query($node['next'][$word], $words, $matched);
} else {
$matched = array();
return false;
}
}
结果
key_len * msg_len
,当然正则会进行优化,但基础这样,再优化效率可想而知。msg_len * 9(最长关键词长度 + 優化巨量關鍵字的匹配个特殊字符)
次 hash 查找,即最长关键词类似 AAA
,信息内容为 AAA...
时,而这种情况的概率可想而知。他径 – 多进程
设计
并发
,那么接下来的优化就要从并发说起。PHP 是单线程的(虽然也有不好用的多线程扩展),这没啥好的解决办法,并发方向只好从多进程进行了。
% n = n
的日誌,這種hack 的反向分散式我已經用得很熟練了,哈哈。這種方法需要進程傳參數,還需要每個進程都分配讀取整個日誌的的內存,而且不夠優雅。 split -l n file.log output_pre
指令,將檔案分割成每份為n 行的文件,然後用多個行程去讀取多個檔案。此方法的缺點就是不靈活,想換一下進程數時需要重新切分檔。 結果
總結
以上是優化巨量關鍵字的匹配的詳細內容。更多資訊請關注PHP中文網其他相關文章!