Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern

Ursprung des Problems

Ich bin vor ein paar Tagen bei der Arbeit auf ein Problem gestoßen:

Es gibt jeweils 600.000 Kurznachrichtenprotokolle davon 50 Wörter, 50.000 Schlüsselwörter, 2-8 Wörter lang, die meisten davon auf Chinesisch. Es ist erforderlich, alle in diesen 600.000 Datensätzen enthaltenen Schlüsselwörter zu extrahieren und die Anzahl der Treffer für jedes Schlüsselwort zu zählen.

Dieser Artikel gibt eine vollständige Einführung in meine Implementierung und zeigt, wie ich eine Aufgabe, deren Ausführung zehn Stunden dauert, innerhalb von zehn Minuten optimieren kann. Obwohl die Implementierungssprache PHP ist, sollten Ihnen weitere in diesem Artikel vorgestellte Ideen hilfreich sein.

Original – grep

Design

Als ich die Aufgabe zum ersten Mal erhielt, änderte sich meine kleine Meinung sofort, Protokoll + Schlüsselwörter + Statistiken, ich nicht Ich denke darüber nach, den Code selbst zu schreiben, dachte aber zuerst an den unter Linux häufig verwendeten Protokollstatistikbefehl grep. Die Verwendung des Befehls

grep wird nicht noch einmal erwähnt. Mit grep 'keyword' | wc -l kann die Anzahl der durch Schlüsselwörter und PHP erreichten Informationselemente leicht gezählt werden Mit der Funktion exec() können wir Linux-Shell-Befehle direkt aufrufen, allerdings bestehen Sicherheitsrisiken bei der Ausführung gefährlicher Befehle.

Code

Pseudocode:

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

Auf einer alten Maschine ausführen Die Effizienz der alten Maschine ist wirklich schlecht und die Ausführung dauerte 6 Stunden. Es wird geschätzt, dass die neueste Maschine 2-3 Stunden dauern wird. Alle nachfolgenden Optimierungen werden neue Maschinen verwenden, und die Anforderungen haben gerade erst begonnen.

Original, originell in Ideen und Methoden .

Evolution – Regulär

Design

Nach der Abgabe des Auftrags kam das Produkt am nächsten Tag mit neuen Ideen und sagte, dass es eine bestimmte Datenquelle integrieren wollte die Zukunft. Nachrichten werden als Datenstrom geliefert, nicht als Datei. Es erfordert auch den Echtzeitcharakter der Nachrichtenstatistik. Meine Idee, die Daten in eine Datei zu schreiben und sie dann zu zählen, wurde aus Gründen der Skalierbarkeit der Lösung aufgehoben Es wurde eine einzelne Nachricht berücksichtigt.

Zu diesem Zeitpunkt war ich etwas verwirrt und musste auf das traditionellste Werkzeug zurückgreifen – die Regelmäßigkeit. Die Implementierung regulärer Ausdrücke ist nicht schwierig und jede Sprache verfügt über gekapselte reguläre Matching-Funktionen. Der Schwerpunkt liegt auf der Konstruktion von Mustern.

Natürlich ist die Musterkonstruktion hier nicht schwierig, /keywordOptimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern|keword2|.../, verwenden Sie einfach |, um die Schlüsselwörter zu verbinden.

Regelmäßige Fallstricke

Hier sind zwei Fallstricke, die bei der Verwendung auftreten:

• Die reguläre Musterlänge ist zu lang, was zu Übereinstimmungsfehlern führt: PHPs Der reguläre Ausdruck hat ein Backtracking-Limit, um zu verhindern, dass der gesamte verfügbare Stack des Prozesses verbraucht wird, was schließlich zum Absturz von PHP führt. Zu lange Muster führen dazu, dass PHP zu viele Tracebacks erkennt und den Abgleich unterbricht. Nach dem Test beträgt die maximale Musterlänge in der Standardeinstellung etwa 32.000 Byte. Der Parameter pcre.backtrack_limit in php.ini ist die maximale Anzahl von Backtrackings. Der Standardwert ist Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern000000. Ändern Sie ihn oder verwenden Sie php.ini oder verwenden Sie ini_set(‘pcre.backtrack_limit’, n);< 🎜 am Anfang des Skripts > Wenn Sie den Wert auf eine größere Zahl festlegen, kann sich die maximale Musterlänge für einen einzelnen Treffer erhöhen. Natürlich können Sie Schlüsselwörter auch stapelweise zählen (ich habe dies =_= verwendet).

• Das Muster enthält Sonderzeichen, was zu einer großen Anzahl von Warnungen führt: Während des Abgleichvorgangs wurde festgestellt, dass PHP eine große Anzahl von Warnungen meldete:

  unknown Modifikator <span style="color: #ff0000;">Verstümmelte Zeichen<code>unknown modifier <strong>乱码</strong> , sorgfältige Prüfung ergab, dass die Schlüsselwörter / Zeichen enthalten. Sie können preg_quote() verwenden Funktion zum Filtern der Schlüsselwörter.

Code

Pseudocode:

$end = 0;
$step = Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern500;
$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);
}

Um die Aufgabe abzuschließen, lief der Prozess die ganze Nacht. Als ich am nächsten Tag erfuhr, dass ich fast zehn Stunden gelaufen war, war ich untröstlich. . . Es war zu langsam und erfüllte die Nutzungsanforderungen überhaupt nicht. Zu diesem Zeitpunkt hatte ich bereits begonnen, über eine Änderung der Methode nachzudenken.

Als das Produkt seine Keyword-Strategie änderte, einige Keywords ersetzte, darum bat, es erneut auszuführen, und sagte, dass es weiterhin Keywords optimieren würde, lehnte ich den bestehenden Plan komplett ab. Sie dürfen keine Schlüsselwörter zum Abgleichen von Informationen verwenden. Es ist wirklich unerträglich, alle Schlüsselwörter einzeln abzugleichen.

Evolution, Bedürfnisse und Umsetzung

Erwachen – Wortspaltung

Design

Endlich wurde mir klar, dass ich Informationen besorgen muss zu vergleichenden Schlüsselwörtern. Wenn ich Schlüsselwörter als Schlüssel verwende, um eine Hash-Tabelle zu erstellen, verwende ich die Wörter in den Informationen, um in der Hash-Tabelle zu suchen. Wenn sie gefunden werden, wird dies als Übereinstimmung betrachtet. Würde dies nicht eine O(Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern)-Effizienz erreichen?

Aber wie teile ich eine kurze Nachricht in genau die passenden Wörter auf? Auch die Wortsegmentierung braucht Zeit, und der Aufbau eines Wortschatzes und die Verwendung von Wortsegmentierungstools sind große Probleme.

为什么叫拆词呢，我考虑以蛮力将一句话拆分为<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(&#39;/(?<!^)(?!$)/u&#39;, $msg) 是通过正则匹配到两个字符之间的''来将两个字符拆散，而两个括号里的 (?<!^)(?!$) 是分别用来限定捕获组不是第一个，也不是最后一个（不使用这两个捕获组限定符也是可以的，直接使用//作为模式会导致拆分结果在前后各多出一个空字符串项）。 捕获组的概念和用法可见我之前的博客 PHP正则中的捕获组与非捕获组

由于没有真正实现，也不知道效率如何。估算每个短句长度约为 Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern0 字左右时，每条短消息约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'] + Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern,
                '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'] > Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern && isset($node['next'][$word]['next']['`'])) {
                return true;
            }
            return $this->query($node['next'][$word], $words, $matched);
        } else {
            $matched = array();
            return false;
        }
    }

结果

结果当然是喜人的，如此匹配，处理一千条数据只需要3秒左右。找了 Java 的同事试了下，Java 处理一千条数据只需要Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern秒。

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

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

• 而 trie 树效率最差的时候是 msg_len * 9(最长关键词长度 + Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern个特殊字符)次 hash 查找，即最长关键词类似 AAA，信息内容为 AAA...时，而这种情况的概率可想而知。

至此方法的优化到此结束，从每秒钟匹配 Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern0 个，到 300 个，30 倍的性能提升还是巨大的。

终级，却不一定是终极

他径 – 多进程

设计

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

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

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

• Fügen Sie im Prozess einen Protokollzeilenzähler hinzu. Der Prozess unterstützt nur die Übergabe des Protokolls mit der Anzahl der Zeilen  % n = n Reverse Distribution dieses Hacks. Ich bin sehr geübt in der Verwendung dieses Stils, haha. Diese Methode erfordert, dass der Prozess Parameter übergibt und dass jeder Prozess Speicher zum Lesen des gesamten Protokolls zuweist, was nicht elegant genug ist.

• Verwenden Sie den Linux-Befehl split -l n file.log output_pre, um die Datei in Dateien mit jeweils n Zeilen aufzuteilen, und verwenden Sie dann mehrere Prozesse, um mehrere Dateien zu lesen. Der Nachteil dieser Methode besteht darin, dass sie unflexibel ist. Wenn Sie die Anzahl der Prozesse ändern möchten, müssen Sie die Datei erneut aufteilen.

• Verwenden Sie die Listenwarteschlange von Redis, um Protokolle vorübergehend zu speichern und mehrere Prozessverbrauchswarteschlangen zu aktivieren. Diese Methode erfordert das zusätzliche Schreiben von Daten in Redis, was ein zusätzlicher Schritt ist, aber flexibel erweiterbar ist und der Code einfach und elegant ist.

Am Ende wurde die dritte Methode verwendet.

Ergebnisse

Obwohl diese Methode Engpässe aufweisen wird, sollte sie letztendlich auf Redis‘ Netzwerk-IO fallen. Ich habe mir nicht die Mühe gemacht, n Prozesse zu öffnen, um die Leistung des Redis des Unternehmens zu testen. Ich habe die Statistiken abgeschlossen, nachdem ich Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern0 Prozesse in drei oder vier Minuten ausgeführt hatte. Selbst wenn man die Zeit hinzurechnet, die zum Schreiben in Redis benötigt wird, sollte es innerhalb von Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern0 Minuten sein.

Zu Beginn hatte das Produkt die Matching-Geschwindigkeit bereits auf Stundenniveau eingestellt. Als ich die neuen Log-Matching-Ergebnisse in Optimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern0 Minuten herausnahm, war ich ein wenig glücklich, als ich den überraschten Gesichtsausdruck des Produkts sah, haha ~

Andere Wege können Ihnen auch weiterhelfen

Zusammenfassung

Es gibt viele Möglichkeiten, Probleme zu lösen, bevor Sie fragen Wenn Sie Fragen stellen, müssen Sie viele Arten von Wissen verstehen, auch wenn Sie nur seine Funktion kennen. Genau wie bei einem Werkzeugregal müssen Sie so viele Werkzeuge wie möglich unterbringen, bevor Sie bei einem Problem das am besten geeignete auswählen können. Dann müssen Sie sich natürlich im Umgang mit diesen Tools auskennen, damit Sie damit einige seltsame Probleme lösen können.

Wenn Sie Ihre Arbeit gut machen wollen, müssen Sie zuerst Ihre Werkzeuge schärfen. Wenn Sie Leistungsprobleme lösen möchten, reicht es manchmal nicht aus, eine Datenstruktur oder einen Algorithmus zu ändern Ergebnisse. Ich habe das Gefühl, dass ich in dieser Hinsicht noch etwas schwach bin, also werde ich es nach und nach stärken und alle werden mich ermutigen.

Das obige ist der detaillierte Inhalt vonOptimieren Sie die Übereinstimmung großer Mengen von Schlüsselwörtern. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!