更快的 Aho-Corasick PHP 实现

Question

PHP 中是否有 Aho–Corasick 的有效实现？ PHP 中有一个 Aho-Corasick 字符串匹配< /a> 在维基百科文章中提到：

<?php

/* 

    This class performs a multiple pattern matching by using the Aho-Corasick algorythm, which scans text and matches all patterns "at once".

    This class can:
    - find if any of the patterns occours inside the text
    - find all occourrences of the patterns inside the text
    - substitute all occourrences of the patterns with a specified string (empty as well)

    Example of usage: 

    $words = array{ "ananas", "antani", "assassin" };
    $pm = new PatternsMatcher();    
    $pm->patterns_array = $words;   
    if ( $pm->multipattern_match( "banananassata" ) ) {
        echo "pattern found!!";         
    }


    This class is definitively open-source under no particular license.  
    If you use it, let me know what you think about it and how to improve it: 

        Marco Nobile (Università degli studi di Milano-Bicocca) - [email protected]

    The code wasn't deeply tested, use as your own risk.     

    P.S.: in order to use it as a bad words black-lister, I suggest you to wrap the words with two empty spaces (eg.: "ananas"-->" ananas ") 
    in order to avoid sub-patterns detection. Moreover, better delete the word by substituting it with an empty space instead of the empty string.

*/


class PatternsMatcher {

    var $patterns_array;
    var $text;
    var $finals;
    var $delta;
    var $phi;
    var $container; 
    var $M;
    var $ready;


    /* costruttore */
    function PatternsMatcher() {
        $this->finals = array();
        $this->phi = array();
        $this->container = array();
        $this->delta = array();
        $this->patterns_array = array();
        $this->ready = false;
    }


    /* import new pattern */
    function import_pattern( $p ) {
        $this->patterns_array[]=$p;
    }


    /* shortcuts */
    function deltafun( $indice, $carattere ) {
        return $this->delta[$indice][$carattere];
    }       
    function phifun( $indice ) {
        return $this->phi[$indice+1];
    }   


    /*  chiamata (ricorsiva) che controlla l'esistenza di prefissi uguali a questa stringa. 
        il parametro limita il numero di stati oltre il quale non verificare */
    function check_border( $string , $state ) {


        /* se la stringa è lunga 0 non ho trovato prefissi buoni    */
        if ( strlen($string)==0 )  
            return 0;   

        /* se la stringa è più lunga, controlliamo non sia contenuta in un prefisso
            ovvero in una delle stringhe identificate dagli stati precedenti (<state) */
        for ($j=0; $j<$state; $j++) {

            /* se questo suffisso è uguale ad un pattern, ritorna lo stato corrispondente */
            if ( $string == $this->container[ $j ] )
                return $j+1;
        }

        // trovato nulla, riprovo con la sottostringa
        return $this->check_border( substr( $string, 1 ) , $state );                
    }


    /* costruisce la tabella phi (failure) */
    function build_phi( ) {

        /* valore di partenza */
        $this->phi[0]=0;

        /* foreach stato */
        foreach ( $this->container as $index => $string )  {

            /*  controlla se il prefisso di questo pattern ha un suffisso che è... 
                prefisso di un pattern tra quelli identificati dagli stati 0..index */
            $this->phi[ $index ] = $this->check_border( $string , $index );

        }

        return $this->phi;

    }


    /* costruisce la tabella delta (next) */
    function build_delta( ) {

        /* somma delle lunghezze dei patterns */
        $this->M = 0;

        /* ultimo stato */
        $last_state = 0;

        /* contiamo i caratteri dei patterns */
        foreach( $this->patterns_array as $pattern ) {
            $lunghezza = strlen( $pattern );
            $this->M += $lunghezza;
        }

        /* for each pattern... */
        foreach( $this->patterns_array as $key => $pattern ) {

            /* convertiamo le stringhe in array di caratteri  */        
            $string = $pattern;
            $lun = strlen($pattern);

            /* stati iniziali */
            $asf_state = 0;
            $in_pattern_index = 0;

            /* tengo traccia dei prefissi, mi rende la vita più semplice dopo */
            $temp = "";

            /* finché il pattern non è esaurito e la delta è diversa da NIL... */
            while( ($in_pattern_index < $lun) & ( !is_null( $this->deltafun( $asf_state , $string[$in_pattern_index] ) ) ) ) {

                // segui un percorso pre-esistente 
                $asf_state = $this->deltafun( $asf_state , $string[ $in_pattern_index ] );

                // aggiorna il prefisso fin quì
                $temp.=$string[ $in_pattern_index ];

                // cambia carattere del pattern
                $in_pattern_index++;

            }


            /* crea gli eventuali nuovi stati */
            while( $in_pattern_index<$lun ) {

                // salva i prefissi aggiuntivi
                $temp.=$string[ $in_pattern_index ];                
                $this->container[] = $temp;

                // nuovo stato
                $last_state++;

                // salva in delta
                $this->delta[ $asf_state ][ $string[ $in_pattern_index ] ] = $last_state;

                // prossimo carattere (se c'è)
                $in_pattern_index++;
                $asf_state = $last_state;

            }

            /* è uno stato finale! */
            $this->finals[ $asf_state ] = true;

        }

        return $this->delta;

    }


    /* precalcola le tabelle phi e delta; se già calcolate, le ritorna direttamente */
    function generate() {

        /* cache: se abbiamo già precalcolato le tabelle, ritornale direttamente */
        if ($this->ready)   return;

        /* ordina lessicograficamente */
        sort( $this->patterns_array, SORT_STRING );

        /* precalcula le tabelle */         
        $this->build_delta( );      
        $this->build_phi( );

        /* abbiamo precalcolato */
        $this->ready = true;
    }


    /* Aho-Corasick standard */ 
    function multipattern_match( $text ) {

        // generate tables
        $this->generate();

        // necessario per prendere anche le prime occorrenze della frase (es.: pattern = " ab " in "ab ac ").
        $text = " ".$text;

        $i=0;       
        $stato=0;

        while ( $i<strlen($text) ) {

            $n = $this->delta[ $stato ][ $text[$i] ];

            $stato = 
                is_null($n)?    $this->phi[ $stato ] : $n;

            if ( $this->finals[ $stato] ) {
                return $i;
            }

            $i++;
        }       
        return -1;
    }


    /* Aho-Corasick che trova tutte le occorrenze (ritorna un array di tuple {posizione,stringa} ) */
    function multipattern_match_array( $text ) {

        // generate tables
        $this->generate();

        // necessario per prendere anche le prime occorrenze della frase (es.: pattern = " ab " in "ab ac ").
        $text = " ".$text;

        $i=0;       
        $stato=0;
        $result = array();
        $temp = "";

        while ( $i<strlen($text) ) {

            $n = $this->deltafun( $stato , $text[$i] );

            $stato = 
                is_null($n)?    $this->phi[ $stato ] : $n;

            $temp = 
                $stato == 0?
                    "" : $temp.$text[$i];           

            if ( $this->finals[ $stato] ) {
                $result[] = array($temp,$i);
                // echo $temp;
            }           

            $i++;
        }       

        return $result;
    }


    /*  Aho-Corasick modificato per la cancellazione di pattern (blacklist). 
        Il parametro specifica con quale sequenza sostituire lo spazio vuoto */
    function remove_substrings( $text , $with = "" ) {

        // genera le tabelle
        $this->generate();

        // necessario per prendere anche le prime occorrenze della frase (es.: pattern = " ab " in "ab ac ").
        $text = " ".$text;

        // contatore sul T
        $i=0;

        // contatore sul T' (output)
        $j=0;

        // contatore su P
        $k=0;

        // stato sull'ASF
        $stato=0;

        // non ricalcolare la dimensione del testo tutte le volte!
        $luntext = strlen($text);

        // preallochiamo il testo in uscita T' (necessario per le idiosincrasie di PHP)
        $nuovo = str_repeat( " ", $luntext ) ;

        /* finché ci sono caratteri nel testo... */
        while ( $i<$luntext ) {

            // prox stato su ASF
            $n = $this->deltafun( $stato , $text[$i] );

            // è null? usiamo phi
            $stato = 
                is_null($n)?    $this->phifun( $stato ) : $n;

            // aggiorniamo la posizione nella sottostringa (utile per fare backtrack dopo la sostituzione)
            $k = 
                $stato == 0?
                    0 : $k+1;

            // piazza il nuovo carattere
            $nuovo[$j] = $text[$i];

            /* stato di accettazione! cancella all'indietro e riparti */            
            if ( $this->finals[ $stato] ) {

                // backtracking (equivale a cancellare i caratteri)
                $j -= $k;
                $k=0;

                // abbiamo cancellato della roba. dobbiamo riposizionarci sull'ASF!
                $n = $this->deltafun( $stato , substr($with,-1) );

                $stato = 
                    is_null($n)?    $this->phifun( $stato ) : $n;

                // ci posizioniamo sull'ultimo carattere della stringa con cui abbiamo sostituito il pattern
                $i--;
            }   

            // muoviamo i puntatori
            $j++; $i++;         
        }   

        // non ritorniamo l'intera stringa ma solo quella lunga quanto il risultato
        return substr( $nuovo , 0, $j );
    }

}

但是我很难使用它。它适用于婴儿示例，但如果我尝试加载数千个关键字，则脚本会超出 30 秒的加载限制。

对于其他脚本语言，有很好的实现，例如 http://metacpan.org/pod/Text::扫描 Perl 和http://pypi.python.org/pypi/ahocorasick/0.9 用于 Python。为什么不适合 PHP？

Answer 1

Aho-Corasick 有一个很棒的 C 库，请查看项目页面 http://sourceforge.net /projects/multifast/?source=dlp

我还需要 PHP 中的 Aho Corasick，因此我实现了 PHP 扩展 (.so) 作为该库的包装器。
查看我的 GitHub：https://github.com/ph4r05/php_aho_corasick

许可证：LGPL。

Answer 2

PHP 确实很慢，这是众所周知的。数字处理最好留给编译语言，对于 PHP，则最好留给扩展。您可以将此代码重写为扩展，但最好采用现有的 C 库并将其包装到扩展中，例如此库：

http://sourceforge.net/projects/multifast/

如果您正在寻找更快的解决方案，请使用 shell 来包装 perl / python 实现之一你表扬过。

Answer 3

Aho corasick 有两个阶段，第一个阶段是构建优化树，第二个阶段是使用该树来查找匹配项。随着字典中项目数量的增加，第一阶段变得越来越长。 PHP 存在一个问题，即每个请求都是无共享执行，这意味着每个请求都必须再次重建整个字典。

最简单的解决方案是将算法分为两部分，并使用一个加载程序来构建字典并将其放入 APC (APCU)、memcache 或其他快速共享数据存储中。然后使用预加载的字典与另一半执行搜索。

或者使用没有共享无请求限制的语言创建一个小型 REST 服务器，以便可以在全局范围内构建字典，并通过 REST 对其进行 pwrform 搜索。

Answer 4

如果您在 php 中使用 POSIX regexp 函数并使用交替“|”为了分隔单词，您将获得与 Aho-Corasick 基本相似的行为，因为正则表达式引擎可能会生成 DFA 来评估正则表达式。

例如 /stackoverflow|serverfault|php|python|c++|javascript/