4
Aho–Corasickの実装はPHPで動作していますか？ Wikipediaの記事に言及した1 Aho-Corasick string matching in PHPがあります：速いAho-Corasick PHPの実装
<?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秒の制限を超えます。
その他のスクリプト言語では、Perlの場合はhttp://metacpan.org/pod/Text::Scan、Pythonの場合はhttp://pypi.python.org/pypi/ahocorasick/0.9など素晴らしい実装があります。なぜPHPはありませんか？
これまでに何を試みましたか？また、私はPHPにリンクしている**のように*あなたが既にPHPのために*なぜですか？あなたはたぶん計算上の限界にぶつかっているかもしれませんし、有益ではない方法でクラスを使用しているかもしれませんが、あなたはコードを投稿していません！ – hakre
あなたはより小さいテキストとそれほど頻繁でないパターンを使ってみましたか？ – c69
@hakre確かに、オートマトンを構築しようとすると、スクリプトは30秒の制限を超えます。自分のローカルサーバーでオートマトンを構築してホスティングにアップロードすることができれば、ドキュメントを見つけることができません。とにかく、推奨されるように拡張としてcライブラリを使う方が良いです。 –