Разовая работа по реализации на PHP алгоритма Ахо-Корасик (с доработками)

[sedan]

Здравствуйте, уважаемые форумчане!

Ищу специалиста на фриланс, способного релизовать алгоритм Ахо-Корасик (нахождение набора ключевых слов в тексте за один проход). Желателен опыт в успешном решении подобных сложных задач.

Суть - поиск и замена множества ключевых слов в тексте с HTML тегами (список ключевых слов может быть большим - до нескольких тысяч, нужен учет морфологии) с использованием вышеуказанного алгоритма.

Ссылка на полное ТЗ: https://docs.google.com/document/d/1qGlDAUQV641vjh8_jlZ7xyIJAz3D8ONtEfT_cosPyYE/edit?usp=sharing

Связь: почта sedan7668687[собака]gmail.com, скайп sedan7668687

По оплате - не знаю сколько такая задача может занять по времени - предлагайте ваши сроки по указанным контактам. Думаю за такой скрипт вполне приемлемая цена $100-200.

Заранее большое спасибо откликнувшимся.

 

[Redjik]

PCRE регулярки так же работают на автоматах и суффиксных деревьях, не надо городить это на php.

 

[sedan]

PCRE регулярки так же работают на автоматах и суффиксных деревьях, не надо городить это на php.

а как насчет скорости регулярки вида /key|anotherkey|yetanotherkey|.../ в случае тысяч ключевых слов и текста в несколько килобайт?

 

[WMix]

я отчистил бы от тэгов, от символов, от предлогов превратил бы слова в простую форму запомнив предыдущее, дистинкт, это кешировал бы.
далее по кешу найти пересечение с ключевыми словами, str_replace ну или регулярки или или в зависимости от флажков..
задачка прикольненькая

 

[hell0w0rd]

а как насчет скорости регулярки вида /key|anotherkey|yetanotherkey|.../ в случае тысяч ключевых слов и текста в несколько килобайт?

этож проверить 10 минут времени?)

 

[sedan]

я отчистил бы от тэгов, от символов, от предлогов превратил бы слова в простую форму запомнив предыдущее, дистинкт, это кешировал бы.
далее по кешу найти пересечение с ключевыми словами, str_replace ну или регулярки или или в зависимости от флажков..
задачка прикольненькая

в том то и дело, что текст нужно вернуть в первозданном виде, с найденными ключевыми словами, замененными на ссылки. Грубо говоря это - скрипт перелинковки. Самая большая сложность - замены по правилам (морфология, замена максимум K уникальных кл. слов, замена не более N раз каждого слова)

 

[sedan]

этож проверить 10 минут времени?)

с регуляркой я уже столкнулся с проблемой замены слов целиком. Т.е. ключевое слово "парк" находится в словах "паркур", "запарка" итд - модификатор "/\bслово\b/" не работает с русским языком в preg_replace. Вот такая нетривиальная задача

 

[fixxxer]

sedan, если кириллица в utf-8, нужен модификатор /u - и все заработает.

 

[Redjik]

Самая большая сложность - замены по правилам (морфология, замена максимум K уникальных кл. слов, замена не более N раз каждого слова)

Предложенный алгоритм таки не решает эту проблему =)

с регуляркой я уже столкнулся с проблемой замены слов целиком. Т.е. ключевое слово "парк" находится в словах "паркур", "запарка" итд - модификатор "/\bслово\b/" не работает с русским языком в preg_replace. Вот такая нетривиальная задача

Предложенный алгоритм таки так же не решает эту проблему =)
В ТЗ задача поменять не парк, а парк+название или слово... добавь в регулярку пробельные символы и инварианты с морфологией

ЗЫ. оверхеды пыха с лихвой покроют профит от алгоритма как по времени, так и по памяти, если сравнить с регуляркой...

на С еще может быть это и имело бы смысл, но алгоритм сам по себе прожорливый кстати

 

[WMix]

в том то и дело, что текст нужно вернуть в первозданном виде, с найденными ключевыми словами, замененными на ссылки. Грубо говоря это - скрипт перелинковки. Самая большая сложность - замены по правилам (морфология, замена максимум K уникальных кл. слов, замена не более N раз каждого слова)

sedan, менять я буду в оригинале, а процедура только чтоб быстро понимать, что менять. как раз из за морфологии.

кста, 100% в википедии эта задачка решена

 

[grigori]

регуляркой морфологию не селать, все-равно по циклу каждое слово перебирать, приводить, проверять по базе, оборачивать ссылкой, регулярка тут не очень ,
а вообще, такое чаще пишется на питоне

 

[Redjik]

регуляркой морфологию не селать, все-равно по циклу каждое слово перебирать, приводить, проверять по базе, оборачивать ссылкой, регулярка тут не очень ,
а вообще, такое чаще пишется на питоне

Для начала формируем список слов, потом добавляем в список слов инварианты с морфологией.
Имполдим список слов через |.
Получаем pattern.

Далее прогоняем через регулярку и делаем замену колбэком.

Ахо-корасик работает с DFA и строит суфиксные деревья.
Регулярки в пхп по дефолту юзают NFA и так же строит суфиксные деревья.
В принципе это не проблема и есть два выхода.

1) Забить - оверхед не критичен для объемов данных ТС.
2) exec('pcre - dfa');

Вот пример с просто match.

<?php
//первый том 1.27mb
$longStr = file_get_contents('warNpeace.txt');

$formattedStr = preg_replace('#[^а-яA-Za-zA-Z0-9\s]#u','',$longStr);

$words = explode(' ',$formattedStr);

foreach ($words as $key=>$word)
{
    $word = trim($word);
    if (empty($word)){
        unset($words[$key]);
    }else{
        $words[$key] = htmlspecialchars(trim($word));
    }
}

//ограничение на длину регулярки =(
$chunked = array_chunk($words,3500);
$words = $chunked[0];

$pattern = implode('|',$words);
$start = microtime(true);
preg_match_all('#'.$pattern.'#u',$longStr,$matches);

var_dump(count($words),mb_strlen($longStr),mb_strlen($pattern),count($matches[0]),microtime(true)-$start,memory_get_peak_usage(true));

//int(3500) int(1341087) int(37121) int(292563) float(18.016248941422) int(90963968)

 

[WMix]

а где морфология? где ключевые слова?

include "vendor/phpmorphy-0.3.7/src/common.php";

$in = 'file.html';
$out = 'out.htm';

$out_text = $in_text = file_get_contents($in);

$morphy = new phpMorphy(
    '/var/www/vendor/phpmorphy-0.3.7/dicts', 'ru_RU',
    array('storage' => PHPMORPHY_STORAGE_FILE,)
);

$words = preg_split( '/[\s\.;&\(\),-\?]+/',
    strip_tags(
        preg_replace( '#<script(.*?)>(.*?)</script>#is', '', $in_text )
    )
);

$dic = array();
foreach( $words as $word ){
    $lemas = $morphy->lemmatize(mb_strtoupper($word, 'UTF-8'));
    if($lemas){
        if(!isset($dic[$lemas[0]])){
            $dic[$lemas[0]] = array();
        }
        if( !in_array($word, $dic[$lemas[0]])){
            $dic[$lemas[0]][] = $word;
        }
    }
};
//print_r($dic);
$keywords = array('РЕГУЛЯРКА' => '[>>%s<<]', 'ИСКАТЬ' => '[***%s***]');
foreach($keywords as $keyword => $tpl){
    if(isset($dic[$keyword])){
        foreach($dic[$keyword] as $word){
            $out_text = str_replace($word, sprintf($tpl, $word), $out_text);
        }
    }
}
file_put_contents($out, $out_text);

я такой набросок делал, пытаясь прикинуть затраты..

 

[Redjik]

какая морфология еще? какие нафиг ключевые слова???

Для начала формируем список слов, потом добавляем в список слов инварианты с морфологией.

а как насчет скорости регулярки вида /key|anotherkey|yetanotherkey|.../ в случае тысяч ключевых слов и текста в несколько килобайт?

Я лишь показал, что происходит при поиске 3,5к слов в 1,25mb текста, где куча этих слов.

 

[Redjik]

Вот, заменил одну строчку... надо всего то в добавить логики для формирования ссылки и добавить морфрологию.
ВСЕ!

<?php
//первый том
$longStr = file_get_contents('warNpeace.txt');

$formattedStr = preg_replace('#[^а-яA-Za-zA-Z0-9\s]#u','',$longStr);

$words = explode(' ',$formattedStr);

foreach ($words as $key=>$word)
{
    $word = trim($word);
    if (empty($word)){
        unset($words[$key]);
    }else{
        $words[$key] = htmlspecialchars(trim($word));
    }
}

$chunked = array_chunk($words,3000);
$words = $chunked[0];


$pattern = implode(' | ',$words);
$start = microtime(true);
$strResult = preg_replace_callback('#'.$pattern.'#u',function($matches){return '<a href="ссылку вставть">'.$matches[0].'</a>';},$longStr);

var_dump(count($words),mb_strlen($longStr),mb_strlen($pattern),$strResult,microtime(true)-$start,memory_get_peak_usage(true));

//int(3500) int(1341087) int(37121) int(292563) float(18.016248941422) int(90963968)