Implementación PHP Aho-Corasick más rápida

¿Hay una implementación en funcionamiento de Aho-Corasick en PHP? Hay una coincidencia de cadena Aho-Corasick en PHP mencionada en el artículo de Wikipedia:

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; $jcontainer[ $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 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_indexcontainer[] = $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 ( $idelta[ $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 ( $ideltafun( $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 ( $ideltafun( $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 ); } } 

Sin embargo, tengo dificultades para usarlo. Funciona para un ejemplo de bebé, pero si bash cargar varias miles de palabras clave, la secuencia de comandos excede el límite de 30 segundos para cargar.

Para otros lenguajes de script hay una implementación maravillosa como http://metacpan.org/pod/Text::Scan para Perl y http://pypi.python.org/pypi/ahocorasick/0.9 para Python. ¿Por qué no para PHP?

Hay una gran biblioteca de C para Aho-Corasick, mira en la página del proyecto http://sourceforge.net/projects/multifast/?source=dlp

También necesitaba Aho Corasick en PHP, así que implementé PHP Extension (.so) como un contenedor para esta biblioteca. Mira mi GitHub: https://github.com/ph4r05/php_aho_corasick

Licencia: LGPL.

Casi quiero votar abajo porque ya hay una implementación. Puede titular la pregunta ‘Implementación PHP Aho-Corasick más rápida’ o algo así.

De todos modos, PHP es realmente lento y eso es conocido. Es mejor dejar números crujientes para los idiomas comstackdos y, en el caso de PHP, una extensión. Podría volver a escribir este código como una extensión, pero probablemente sería mejor tomar una biblioteca C existente y envolverla en una extensión, algo así como esta biblioteca, por ejemplo:

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

Si está buscando una solución más rápida, utilice el intérprete de comandos para ajustar una de las implementaciones de Perl / Python que ha elogiado.

Aho corasick tiene dos fases, una está construyendo un árbol optimizado, la segunda está usando ese árbol para encontrar una coincidencia. A medida que aumenta la cantidad de elementos en el diccionario, la primera fase se alarga cada vez más. PHP tiene un problema en el que cada solicitud es una ejecución de nada compartida, lo que significa que cada solicitud debería volver a generar todo el dictiinario.

La solución más fácil sería dividir el algoritmo en sus dos partes y tener un cargador que construya un diccionario y lo coloque en APC (APCU), Memcache u otro almacén de datos compartido rápido. Y luego use el diccionario precargado para realizar las búsquedas con la otra mitad.

Alternativamente, cree un pequeño servidor REST utilizando un idioma que no tenga la limitación de solicitud de nada compartido, de modo que se pueda construir un diccionario en el scope global, y pwrform serare mediante REST.

Si usa las funciones de expresión regular POSIX en php y usa la alternancia “|” para separar palabras, obtendrás un comportamiento esencialmente similar a Aho-Corasick ya que el motor de expresiones regulares probablemente generará un DFA para evaluar la expresión regular.

eg / stackoverflow | serverfault | php | python | c ++ | javascript /