Быстрая реализация PHP-кода Aho-Corasick

Есть ли работа над реализацией Aho-Corasick в PHP? В 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. PS: 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 для Python. Почему не для PHP?