Intereting Posts
Обнаружение типа изображения из строки base64 в PHP Сбор значений столбцов в массив Композитный шаблон в PHP, как создавать классы для работы вокруг необходимости расширения двух классов Как ограничить количество результатов в Magento? Как обновить часовой пояс для временных меток (created_at и updated_at), которыми управляет Laravel Eloquent? Почему файл может быть частично загружен? Проблема с использованием даты и времени MSSQL в PHP (через SQLSRV) Класс Workbench класса Laravel 4 не найден Лучший способ получить размер файла, превышающий 2 ГБ в php? проблема с конкретной конфигурацией модуля zend Передать переменную скрипту php, запущенному из командной строки Скобки, изменяющие семантику результата вызова функции Выполнение скрипта PHP с использованием объектно-c google-api-php-client: Неверный клиентский секретный файл JSON Сохранение изображения в Google Chart в файл с помощью PHP

Быстрая реализация 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?

Существует большая библиотека C для Aho-Corasick, посмотрите на странице проекта http://sourceforge.net/projects/multifast/?source=dlp

Мне также нужен был Aho Corasick в PHP, поэтому я внедрил PHP Extension (.so) в качестве обертки для этой библиотеки. Проверьте мой GitHub: https://github.com/ph4r05/php_aho_corasick

Лицензия: LGPL.

Я почти хочу проголосовать за это, поскольку уже есть реализация. Вы можете назвать вопрос «Быстрая реализация PHP-кода Aho-Corasick» или что-то еще.

В любом случае, PHP – это действительно slooow, и это известно. Хрустящие числа лучше оставить компилируемым языкам, а в случае PHP – расширению. Вы можете переписать этот код как расширение, но, вероятно, лучше взять существующую библиотеку C и перенести ее в расширение, например, такую, как эта библиотека:

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

Если вы ищете более быстрое решение, используйте оболочку, чтобы обернуть одну из реализаций perl / python, которую вы похвалили.

У Aho corasick есть две фазы: одна создает оптимизированное дерево, второе использует это дерево, чтобы найти совпадение. По мере увеличения количества элементов в словаре первая фаза становится длиннее и длиннее. У PHP есть проблема, когда каждый запрос – это совместное исполнение ничего, что означает, что каждый запрос должен будет снова перестроить всю диктатуру.

Самым простым решением было бы разделить алгоритм на две его части и иметь загрузчик, который создает словарь и помещает его в APCU (APCU), в memcache или в другое быстрое хранилище данных общего доступа. И затем используйте предварительно загруженный словарь для выполнения поисков с другой половиной.

В качестве альтернативы создайте небольшой сервер REST с использованием языка, на котором нет ограничения на доступ к совместному нишу, поэтому словарь может быть создан в глобальной области действия и иметь его pwrform serachs через REST.

Если вы используете функции PREIX regexp в php и используете чередование «|» чтобы разделить слова, вы получите по существу аналогичное поведение как Aho-Corasick, так как механизм regexp, вероятно, сгенерирует DFA для оценки регулярного выражения.

например / stackoverflow | serverfault | php | python | c ++ | javascript /