在 PHP中是否有Aho–Corasick的工作实现？Wikipedia 文章中提到的PHP 中有一个Aho-Corasick 字符串匹配：
<?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) - marco.nobile@unimib.it
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::Scan for Perl 和http://pypi.python.org/pypi/ahocorasick/0.9 for Python。为什么不用于 PHP？