更快的阿霍Corasick PHP实现 [英] Faster Aho-Corasick PHP implementation
本文介绍了更快的阿霍Corasick PHP实现的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
有阿霍Corasick ？有一个阿霍Corasick字符串匹配在PHP 在维基百科的文章中提到：
Is there a working implementation of Aho–Corasick in PHP? There is one Aho-Corasick string matching in PHP mentioned on the Wikipedia article:
<?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秒极限载荷。
However I have hard time using it. It works for a baby example but if I try to load several thousands keywords then the script exceeds the 30 seconds limit for loading.
有关其他脚本语言也有精彩的实施，如 http://metacpan.org/pod/文字::扫描以Perl和 http://pypi.python.org/pypi/ ahocorasick / 0.9 为Python。为什么不为PHP？
For other script languages there are wonderful implementation such as http://metacpan.org/pod/Text::Scan for Perl and http://pypi.python.org/pypi/ahocorasick/0.9 for Python. Why not for PHP?
推荐答案
没有为阿霍Corasick一个伟大的C库，对项目页面的 http://sourceforge.net/projects/multifast/?source=dlp
There is a great C library for Aho-Corasick, look on project page http://sourceforge.net/projects/multifast/?source=dlp
我还需要阿霍Corasick在PHP让我实现了PHP扩展（。所以）作为包装这个库。 看看我的GitHub： https://github.com/ph4r05/php_aho_corasick
I also needed Aho Corasick in PHP so I implemented PHP Extension (.so) as a wrapper for this library. Check out my GitHub: https://github.com/ph4r05/php_aho_corasick
许可证：LGPL
这篇关于更快的阿霍Corasick PHP实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
