Optimiser la correspondance d'un grand nombre de mots-clés

Origine du problème

J'ai rencontré un problème au travail il y a quelques jours :

Il y a 600 000 journaux de messages courts, chacun dont 50 mots, 50 000 mots-clés, de 2 à 8 mots, la plupart en chinois. Il faut extraire tous les mots-clés contenus dans ces 600 000 enregistrements et compter le nombre de hits pour chaque mot-clé.

Cet article donne une introduction complète à ma mise en œuvre et montre comment je peux optimiser une tâche qui prend dix heures pour s'exécuter en dix minutes. Bien que le langage d’implémentation soit PHP, d’autres idées présentées dans cet article devraient pouvoir vous aider.

Original – grep

Design

Quand j'ai reçu la tâche pour la première fois, mon petit esprit a immédiatement changé, Journal + Mots-clés + Statistiques, je ne l'ai pas fait pensez à écrire le code moi-même, mais j'ai d'abord pensé à la commande log stats couramment utilisée sous Linux grep. Je ne mentionnerai plus l'utilisation de la commande

grep L'utilisation de grep 'keyword' | wc -l permet de compter facilement le nombre d'éléments d'information touchés par des mots-clés, et php La fonction exec() nous permet d'appeler directement des commandes du shell Linux, bien que cela puisse entraîner des risques de sécurité lors de l'exécution de commandes dangereuses.

Code

Pseudo code :

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

Fonctionner sur une vieille machine L'efficacité de l'ancienne machine est vraiment médiocre, et il a fallu 6 heures pour fonctionner. On estime que la dernière machine prendra 2 à 3 heures. Toutes les optimisations ultérieures utiliseront de nouvelles machines et les exigences ont changé. Le texte principal vient de commencer.

Original, original dans les idées et les méthodes .

Evolution – Regular

Design

Après avoir remis le travail, le produit a proposé de nouvelles idées le lendemain, affirmant qu'il souhaitait intégrer une certaine source de données dans l'avenir, l'actualité Livré sous forme de flux de données et non de fichier. Cela nécessite également la nature en temps réel des statistiques des messages. Mon idée d'écrire les données dans un fichier puis de les compter a été renversée. Pour l'évolutivité de la solution, l'objet statistique actuel n'est plus un tout, mais doit le faire. être pris en compte. Un seul message a été mis en correspondance.

À cette époque, j'étais un peu confus et j'ai dû recourir à l'outil le plus traditionnel : la régularité. La mise en œuvre d'expressions régulières n'est pas difficile et chaque langage a encapsulé des fonctions de correspondance régulières. L'accent est mis sur la construction de modèles.

Bien sûr, la construction du motif ici n'est pas difficile, /keywordOptimiser la correspondance dun grand nombre de mots-clés|keword2|.../, utilisez simplement | pour relier les mots-clés.

Pièges réguliers

Voici deux pièges rencontrés lors de l'utilisation :

• La longueur du motif régulier est trop longue, provoquant un échec de correspondance : PHP's L'expression régulière a une limite de retour en arrière pour éviter de consommer toute la pile disponible du processus, provoquant éventuellement le crash de PHP. Les modèles trop longs amèneront PHP à détecter trop de traces et à interrompre la correspondance. Après le test, la longueur maximale du modèle est d'environ 32 000 octets dans le paramètre par défaut. Le paramètre pcre.backtrack_limit dans php.ini est le nombre maximum de retours en arrière. La valeur par défaut est Optimiser la correspondance dun grand nombre de mots-clés000000. Modifiez-le ou utilisez php.ini ou utilisez ini_set(‘pcre.backtrack_limit’, n);<. au d du script.> Le définir sur un nombre plus grand peut augmenter la longueur maximale du motif pour une seule correspondance. Bien sûr, vous pouvez également compter les mots-clés par lots (j'ai utilisé ceci =_=).

• Le modèle contient des caractères spéciaux, ce qui entraîne un grand nombre d'avertissements : Au cours du processus de correspondance, il a été constaté que PHP signalait un grand nombre d'avertissements :

  inconnu modificateur <span style="color: #ff0000;">Caractères tronqués<code>unknown modifier <strong>乱码</strong> , une inspection minutieuse a révélé qu'il y avait des caractères / dans les mots-clés. Vous pouvez utiliser le preg_quote(). fonction pour filtrer les mots-clés.

Code

Pseudo code :

$end = 0;
$step = Optimiser la correspondance dun grand nombre de mots-clés500;
$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);
}

Afin de terminer la tâche, le processus a duré toute la nuit. Quand j’ai appris le lendemain que j’avais couru pendant près de dix heures, j’ai eu le cœur brisé. . . C'était trop lent et ne répondait absolument pas aux exigences d'utilisation. À cette époque, j'avais déjà commencé à envisager de changer de méthode.

Lorsque le produit a modifié sa stratégie de mots-clés, remplacé certains mots-clés, demandé de l'exécuter à nouveau et déclaré qu'il continuerait à optimiser les mots-clés, j'ai complètement rejeté le plan existant. Vous ne devez pas utiliser de mots-clés pour faire correspondre les informations. Utiliser tous les mots-clés pour les faire correspondre un par un est vraiment insupportable.

Évolution, besoins et mise en œuvre

Éveil – fractionnement des mots

Design

J'ai enfin commencé à comprendre que pour obtenir des informations, allez aux mots-clés à comparer. Si j'utilise des mots-clés comme clés pour créer une table de hachage, j'utilise les mots contenus dans les informations pour rechercher dans la table de hachage, et s'ils sont trouvés, cela sera considéré comme une correspondance. Cela n'atteindra-t-il pas l'efficacité O(Optimiser la correspondance dun grand nombre de mots-clés) ?

Mais pour un message court, comment puis-je le diviser en mots adaptés à la segmentation des mots ? La segmentation des mots prend également du temps, et mes mots-clés sont tous des mots dénués de sens. Construire un vocabulaire et utiliser des outils de segmentation de mots sont de gros problèmes. Finalement, j'ai trouvé 拆词.

为什么叫拆词呢，我考虑以蛮力将一句话拆分为<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正则中的捕获组与非捕获组

由于没有真正实现，也不知道效率如何。估算每个短句长度约为 Optimiser la correspondance dun grand nombre de mots-clés0 字左右时，每条短消息约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'] + Optimiser la correspondance dun grand nombre de mots-clés,
                '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'] > Optimiser la correspondance dun grand nombre de mots-clés && isset($node['next'][$word]['next']['`'])) {
                return true;
            }
            return $this->query($node['next'][$word], $words, $matched);
        } else {
            $matched = array();
            return false;
        }
    }

结果

结果当然是喜人的，如此匹配，处理一千条数据只需要3秒左右。找了 Java 的同事试了下，Java 处理一千条数据只需要Optimiser la correspondance dun grand nombre de mots-clés秒。

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

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

• 而 trie 树效率最差的时候是 msg_len * 9(最长关键词长度 + Optimiser la correspondance dun grand nombre de mots-clés个特殊字符)次 hash 查找，即最长关键词类似 AAA，信息内容为 AAA...时，而这种情况的概率可想而知。

至此方法的优化到此结束，从每秒钟匹配 Optimiser la correspondance dun grand nombre de mots-clés0 个，到 300 个，30 倍的性能提升还是巨大的。

终级，却不一定是终极

他径 – 多进程

设计

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

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

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

• Ajoutez un compteur de lignes de journal dans le processus. Chaque processus prend en charge la transmission du paramètre n. Le processus traite uniquement le journal avec le nombre de lignes  % n = n. distribution inversée de ce hack, je suis devenu très compétent dans l'utilisation de ce style, haha. Cette méthode nécessite que le processus transmette des paramètres, et chaque processus doit allouer de la mémoire pour lire l'intégralité du journal, et ce n'est pas assez élégant.

• Utilisez la commande Linux split -l n file.log output_pre pour diviser le fichier en fichiers de n lignes chacun, puis utilisez plusieurs processus pour lire plusieurs fichiers. L'inconvénient de cette méthode est qu'elle est peu flexible. Si vous souhaitez modifier le nombre de processus, vous devez re-diviser le fichier.

• Utilisez la file d'attente de liste de Redis pour stocker temporairement les journaux et activer plusieurs files d'attente de consommation de processus. Cette méthode nécessite une écriture supplémentaire de données dans Redis, ce qui constitue une étape supplémentaire, mais son extension est flexible et le code est simple et élégant.

J'ai finalement utilisé la troisième voie.

Résultats

Bien que cette méthode présente des goulots d'étranglement, elle devrait éventuellement tomber sur les IO du réseau de Redis. Je n'ai pas pris la peine d'ouvrir n processus pour contester les performances du Redis de l'entreprise. J'ai complété les statistiques après avoir exécuté Optimiser la correspondance dun grand nombre de mots-clés0 processus en trois ou quatre minutes. Même si vous ajoutez le temps nécessaire pour écrire sur Redis, cela devrait être dans les Optimiser la correspondance dun grand nombre de mots-clés0 minutes.

Au début, le produit avait déjà positionné la vitesse de correspondance au niveau horaire. Quand j'ai sorti le nouveau journal des résultats de correspondance en Optimiser la correspondance dun grand nombre de mots-clés0 minutes, je me suis senti un peu heureux quand j'ai vu l'expression surprise du produit, haha. ~

D'autres voies peuvent également vous aider à aller plus loin

Résumé

Il existe de nombreuses façons de résoudre des problèmes, je pense qu'en résolvant diverses Avant de demander. questions, vous devez comprendre de nombreux types de connaissances, même si vous ne connaissez que leur fonction. Tout comme un porte-outils, vous devez mettre autant d'outils que possible avant de pouvoir choisir celui qui convient le mieux lorsque vous rencontrez un problème. Ensuite, bien sûr, vous devez maîtriser l’utilisation de ces outils, afin de pouvoir les utiliser pour résoudre des problèmes étranges.

Si vous voulez bien faire votre travail, vous devez d'abord affiner vos outils. Si vous souhaitez résoudre des problèmes de performances, maîtriser les méthodes au niveau du système ne suffit pas. Parfois, modifier une structure de données ou un algorithme peut être préférable. résultats. Je sens que je suis encore un peu faible sur cet aspect, donc je vais le renforcer petit à petit, et tout le monde m'encouragera.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!