대량의 키워드 매칭 최적화

문제의 원인

며칠 전에 직장에서 문제가 발생했습니다.

단문 메시지 로그가 600,000개 있고 각각 약 50단어, 50,000개 키워드, 2-8단어 길이이며 대부분은 다음과 같습니다. 중국인. 이 60만 개의 레코드에 포함된 모든 키워드를 추출하고 각 키워드에 대한 조회수를 계산하는 작업이 필요합니다.

이 글에서는 대량의 키워드 매칭 최적화0시간에서 대량의 키워드 매칭 최적화0분 이내로 실행해야 하는 작업을 어떻게 최적화할 수 있는지 구현 방법을 자세히 소개합니다. 구현 언어는 PHP이지만 이 기사에서 소개된 더 많은 아이디어가 도움이 될 것입니다.

Original – grep

Design

처음 작업을 받았을 때 내 작은 마음은 즉시 로그 + 키워드 + 통계로 바뀌었습니다. 직접 코드를 작성할 생각은 없었지만 먼저 일반적으로 사용되는 Linux 실행을 생각했습니다. 로그 통계 명령 grepgrep。

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|.../，用|将关键词连接起来即可。

正则小坑

这里介绍两个使用中遇到的小坑：

• 正则模式长度太长导致匹配失败：PHP 的正则有回溯限制，以防止消耗掉所有的进程可用堆栈, 最终导致 php 崩溃。太长的模式会导致 PHP 检测到回溯过多，中断匹配，经测试默认设置时最大模式长度为 32000 字节 左右。php.ini 内 pcre.backtrack_limit 参数为最大回溯次数限制，默认值为 대량의 키워드 매칭 최적화000000，修改或 php.ini 或在脚本开始时使用 ini_set(‘pcre.backtrack_limit’, n); 将其设置为一个较大的数可以提高单次匹配最大模式长度。当然也可以将关键词分批统计（我用了这个=_=）。

• 模式中含有特殊字符导致大量warning：匹配过程中发现 PHP 报出大量 warning：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(&#39;|&#39;, $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(대량의 키워드 매칭 최적화) 的效率了么？

可是一条短消息，我如何把它拆分为刚好的词去匹配呢，分词？分词也是需要时间的，而且我的关键词都是些无语义的词，构建词库、使用分词工具又是很大的问题，最终我想到 拆词.

🎜grep🎜명령어 사용법은 다시 언급되지 않습니다. 🎜grep 'keyword' | wc -l🎜를 사용하면 키워드 조회수 정보 표시줄을 쉽게 계산할 수 있습니다. .Number 및 PHP의 🎜exec()🎜 함수를 사용하면 Linux 쉘 명령을 직접 호출할 수 있지만 위험한 명령을 실행할 때 보안 위험이 있습니다. 🎜🎜Code🎜🎜위 의사 코드: 🎜

$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(&#39;/(?<!^)(?!$)/u&#39;, $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;
}

🎜오래된 기계에서 실행합니다. 오래된 기계의 효율성은 정말 낮고 실행하는 데 6시간이 걸렸습니다. 최신 머신은 2~3시간이 소요될 것으로 예상됩니다. 이후의 모든 최적화는 새 머신을 사용하며 요구 사항이 변경되었습니다. 🎜🎜아이디어와 방법이 독창적이고 독창적입니다. 🎜🎜Evolution – Regular 🎜🎜Design🎜🎜작업을 건네주고 다음날 특정 데이터 소스를 연결하고 싶다며 제품이 새로운 아이디어를 내놓았고, 그 메시지는 파일 대신 데이터 스트림 형태. 또한 메시지 통계의 실시간 특성이 필요합니다.솔루션의 확장성을 위해 현재 통계 개체가 더 이상 전체가 아니라 데이터를 파일에 기록해야 한다는 나의 생각이 뒤집혔습니다. 단일 메시지가 일치하는 것으로 간주됩니다. 🎜🎜이때 조금 혼란스러워서 가장 전통적인 도구-레귤러에 의존해야 했습니다. 정규식의 구현은 어렵지 않으며 각 언어에는 정규 일치 기능이 캡슐화되어 있으며 패턴 구성에 중점을 두고 있습니다. 🎜🎜물론 여기서 패턴 구성은 어렵지 않습니다. 🎜/keyword대량의 키워드 매칭 최적화|keword2|.../🎜, 🎜|🎜를 사용하여 키워드를 연결하면 됩니다. 🎜🎜정규적인 함정🎜🎜사용 중에 직면하게 되는 두 가지 함정은 다음과 같습니다. 🎜

• 🎜정규 패턴의 길이가 너무 길어서 일치 실패가 발생합니다. PHP의 일반 패턴에는 역추적 기능이 있습니다. 모든 프로세스의 사용 가능한 스택을 소비하여 결국 PHP가 충돌하는 것을 방지하기 위해 제한합니다. 패턴이 너무 길면 PHP가 너무 많은 역추적 및 인터럽트 일치를 감지하게 됩니다. 테스트 후 최대 패턴 길이는 기본 설정에서 약 32,000바이트입니다. php.ini의 🎜pcre.backtrack_limit🎜 매개변수는 최대 역추적 횟수입니다. 기본값은 대량의 키워드 매칭 최적화000000입니다. 수정하거나 🎜php.ini🎜에서 사용하세요. 스크립트의 시작 부분 🎜ini_set('pcre.backtrack_limit', n);🎜 더 큰 숫자로 설정하면 단일 일치에 대한 최대 패턴 길이가 늘어날 수 있습니다. 물론 키워드를 일괄적으로 계산할 수도 있습니다(저는 이것을 사용했습니다 =_=). 🎜
• 🎜패턴에 특수 문자가 포함되어 있어 많은 수의 경고가 발생합니다. 일치 프로세스 중에 PHP가 많은 수의 경고를 보고한 것으로 나타났습니다. 🎜알 수 없는 수정자 🎜잘못된 문자🎜 🎜, 주의 깊게 조사한 결과 🎜/🎜 문자가 있는 것으로 나타났습니다. 🎜preg_quote()🎜 함수를 사용하여 키워드를 필터링할 수 있습니다. 🎜

🎜Code🎜🎜pseudocode: 🎜

$node = array(
    'depth' => $depth, // 深度，用以判断已命中的字数
    'next' => array(
        $val => $node, // 这里借用php数组的哈希底层实现，加速子结点的查找
        ...
    ),
);

🎜작업을 완료하기 위해 프로세스가 밤새도록 실행되었습니다. 거의 대량의 키워드 매칭 최적화0시간 동안 뛰었다는 사실을 다음날 알았을 때 나는 가슴이 아팠습니다. . . 너무 느리고 사용 요구 사항을 완전히 충족하지 못했습니다. 이때 이미 방법 변경을 고려하기 시작했습니다. 🎜🎜제품이 키워드 전략을 변경하고, 일부 키워드를 교체하고, 다시 실행해 달라고 요청하고, 계속해서 키워드 최적화를 하겠다고 했을 때 저는 기존 계획을 완전히 거부했습니다. 정보를 일치시키기 위해 키워드를 사용해서는 안 됩니다. 모든 키워드를 사용하여 하나씩 일치시키는 것은 정말 견딜 수 없습니다. 🎜🎜진화, 수요 그리고 실현🎜🎜Awakening – Word Splitting🎜🎜Design🎜🎜나는 마침내 정보를 키워드로 비교해야 한다는 것을 깨닫기 시작했습니다. 키워드를 키로 사용하여 해시 테이블을 만들고, 정보에 있는 단어를 사용하여 해시 테이블에서 검색하고, 발견되면 일치로 간주되므로 O(대량의 키워드 매칭 최적화) 효율성을 얻을 수 있지 않을까요? 🎜🎜그런데 짧은 메시지를 일치하도록 올바른 단어로 분할하려면 어떻게 해야 하나요? 단어 분할에도 시간이 걸리고, 내 키워드는 모두 의미 없는 단어입니다. 어휘를 구성하고 단어 분할 도구를 사용하는 것은 결국 🎜단어 분할🎜을 생각하게 되었습니다. 🎜

为什么叫拆词呢，我考虑以蛮力将一句话拆分为<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(&#39;/(?<!^)(?!$)/u&#39;, $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正则中的捕获组与非捕获组

由于没有真正实现，也不知道效率如何。估算每个短句长度约为 대량의 키워드 매칭 최적화0 字左右时，每条短消息约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树

1. 将关键词用上面介绍的preg_split()函数拆分为单个字符。如科学家就拆分为科、学、家三个字符。

2. 在最后一个字符后添加一个特殊字符`，此字符作为一个关键词的结尾（图中的粉红三角），以此字符来标识查到了一个关键词（不然，我们不知道匹配到科、学两个字符时算不算匹配成功）。

3. 检查根部是否有第一个字符(科)节点，如果有了此节点，到步骤4。 如果还没有，在根部添加值为科的节点。

4. 依次检查并添加学、家 两个节点。

5. 在结尾添加 ` 节点，并继续下一个关键词的插入。

匹配

然后我们以 <strong>这位科学家很了不起</strong>！为例来发起匹配。

• 首先我们将句子拆分为单个字符 这、位、...；

• 从根查询第一个字符这，并没有以这个字符开头的关键词，将字符“指针”向后移，直到找到根下有的字符节点科;

• 接着在节点科下寻找值为 学节点，找到时，结果子树的深度已经到了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'] + 대량의 키워드 매칭 최적화,
                '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;
        }
    }

结果

结果当然是喜人的，如此匹配，处理一千条数据只需要3秒左右。找了 Java 的同事试了下，Java 处理一千条数据只需要대량의 키워드 매칭 최적화秒。

这里来分析一下为什么这种方法这么快：

• 正则匹配：要用所有的关键词去信息里匹配匹配次数是 key_len * msg_len，当然正则会进行优化，但基础这样，再优化效率可想而知。

• 而 trie 树效率最差的时候是 msg_len * 9(最长关键词长度 + 대량의 키워드 매칭 최적화个特殊字符)次 hash 查找，即最长关键词类似 AAA，信息内容为 AAA...时，而这种情况的概率可想而知。

至此方法的优化到此结束，从每秒钟匹配 대량의 키워드 매칭 최적화0 个，到 300 个，30 倍的性能提升还是巨大的。

终级，却不一定是终极

他径 – 多进程

设计

匹配方法的优化结束了，开头说的优化到十分钟以内的目标还没有实现，这时候就要考虑一些其他方法了。

我们一提到高效，必然想到的是 并发，那么接下来的优化就要从并发说起。PHP 是单线程的（虽然也有不好用的多线程扩展），这没啥好的解决办法，并发方向只好从多进程进行了。

那么一个日志文件，用多个进程怎么读呢？这里当然也提供几个方案：

• 프로세스에 로그 라인 카운터를 추가합니다. 각 프로세스는 들어오는 매개변수 n을 지원합니다. 프로세스는 라인 수 % n = n % n = n 的日志，这种 hack 的反向分布式我已经用得很熟练了，哈哈。这种方法需要进程传参数，还需要每个进程都分配读取整个日志的的内存，而且也不够优雅。

• 使用 linux 的 split -l n file.log output_pre로 로그를 처리합니다. 이 해킹을 사용하는 데 매우 능숙해졌습니다. 하하. 이 방법은 프로세스가 매개변수를 전달해야 하며, 각 프로세스는 전체 로그를 읽기 위해 메모리를 할당해야 하므로 충분히 우아하지 않습니다.

• Linux의

  split -l n file.log output_pre

  명령을 사용하여 파일을 각각 n줄의 파일로 분할한 다음 여러 프로세스를 사용하여 여러 파일을 읽습니다. 이 방법의 단점은 유연성이 없다는 것입니다. 프로세스 수를 변경하려면 파일을 다시 분할해야 합니다.

Redis의 목록 대기열을 사용하여 로그를 임시로 저장하고 여러 프로세스 소비 대기열을 활성화합니다. 이 방법을 사용하려면 Redis에 추가 데이터 쓰기가 필요하며 이는 추가 단계이지만 확장이 유연하고 코드가 간단하고 우아합니다.

드디어 세 번째 방법을 사용해 진행했습니다.

Results

이 방법에도 병목 현상이 있지만 결국 Redis의 네트워크 IO에 영향을 미치게 됩니다. 회사 Redis의 성능에 도전하기 위해 굳이 n개의 프로세스를 오픈하지 않고 3~4분 안에 대량의 키워드 매칭 최적화0개의 프로세스를 실행한 후 통계를 완성했습니다. Redis에 쓰는 데 걸리는 시간을 더해도 대량의 키워드 매칭 최적화0분 이내여야 한다.

처음에는 제품이 이미 매칭 속도를 시간 단위로 설정해 두었는데, 대량의 키워드 매칭 최적화0분 만에 새로운 로그 매칭 결과를 꺼내보니, 제품의 놀란 표정을 보고 조금 흐뭇한 기분이 들었어요 ㅎㅎ~

그 길은 더 나아가는 데에도 도움이 될 수 있어요

요약문제를 해결하는 방법은 여러 가지가 있습니다. 다양한 문제를 해결하기 전에 기능만 알더라도 다양한 종류의 지식을 이해해야 한다고 생각합니다. 도구 랙과 마찬가지로 문제가 발생했을 때 가장 적합한 도구를 선택하려면 최대한 많은 도구를 배치해야 합니다. 그렇다면 물론 이러한 도구를 능숙하게 사용하여 몇 가지 이상한 문제를 해결할 수 있어야 합니다. 🎜🎜일을 잘하고 싶다면 먼저 도구를 갈고 닦아야 합니다. 성능 문제를 해결하려면 시스템 수준의 방법을 익히는 것만으로는 충분하지 않습니다. 때로는 데이터 구조나 알고리즘을 변경하는 것이 더 나은 결과를 가져올 수도 있습니다. 아직은 제가 이 부분에 있어서 조금 약하다고 생각하기 때문에 점차 강화해나가고 모두가 저를 격려해 줄 것입니다. 🎜🎜🎜

위 내용은 대량의 키워드 매칭 최적화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!