Комментарии 78
Также можно разделить текст на (количество потоков cpu) кусков и гнать параллельно. Интересно, сколько это займёт времени?
что конкретно? Если вы про время, которое потребуется на обновление кода для поддержки многопоточности, то немного. Т.к. проще всего в каждый отдельный поток загонять поиск/замену по отдельному документу. Каждый поток будет работать только с одним документом. Остальные ему не нужны. Корпус ключевых слов можно шарить между потоками, так как он в процессе работы приложения не меняется.
А результаты работы поиска агрегировать,
А результат работы замены просто выгружать и сохранять в новый документ.
Сама задача довольно проста для распараллеливания.
А результаты работы поиска агрегировать,
А результат работы замены просто выгружать и сохранять в новый документ.
Сама задача довольно проста для распараллеливания.
а какой результат показал сложный префиксный регексп типа такого?
/\b(?:Python|Ruby|(?:J(?:ava|2ee)))/
arty К сожалению немного не понял вопрос. Если вы имеете ввиду на сколько подобный Regex будет медленней чем простой (описанный в статье), то таких сравнений тут не проводилось.
Проблема была в том, что даже простой Regex уже выполнялся неприемлемо долго.
Проблема была в том, что даже простой Regex уже выполнялся неприемлемо долго.
судя по коду на SO, вы каждый регексп прогоняли по отдельности по всему тексту. Конечно, это будет медленно. Я думаю, что если сделать сложный регексп типа приведённого мной в качестве примера, и прогнать его по тексту один раз, то это будет быстро. Заодно можно сохранить возможность находить спецсимволы и нечувствительность к регистру.
кстати, вполне может оказаться, что реализация регекспов в языке сама будет составлять префиксное дерево, и тогда можно будет обойтись банальным:
/\b(Ruby|Python|Java|J2ee)/
хммм… такой вариант не изучался. Стоит попробовать. На мой взгляд если Regex сам создает префиксное дерево, то это уже не оптимизация а low code development какой-то)) Когда раньше разбирался с принципом работы и выполнения Regex то всё было намного проще (рекурсия и всё). Хотя по тестам производительности, которые делал раньше у меня не было ощущения что там что-то большее
ну не знаю, если есть готовый и простой в использовании инструмент, то почему его не применить? зачем то же самое переписывать самостоятельно?
Если есть. Пока мы лишь предполагаем. Ваш вариант не опробовался. Тут ещё задача сгенерировать валидный Regex из 100k ключевых слов. Представляю как он будет выглядеть
ну простой вариант: new RegExp(`\\b(${replacements.join('|')})`)
если же я ошибаюсь в предположении, что реализация сама строит префиксное дерево, то всё равно не сильно сложно
если же я ошибаюсь в предположении, что реализация сама строит префиксное дерево, то всё равно не сильно сложно
На хабре когда-то публиковался готовый java-код для подобной оптимизации регулярок: habrahabr.ru/post/117177. Я его переписывал на javascript для себя codepen.io/DenVdmj/full/dmpAL
То, что вы предлагаете — это уж точно не «готовый и простой в использовании инструмент», так как построить регексп, соответствующий по структуре префиксному дереву — это даже чуточку сложнее, чем строить само префиксное дерево. Больше похоже на предложение забивать гвозди «простой в использовании» микроскопом :)
И это при том, что пока что нет гарантий, что такой регексп в конкретной реализации будет работать эффективно.
И это при том, что пока что нет гарантий, что такой регексп в конкретной реализации будет работать эффективно.
как я сказал выше, если реализация регулярных выражений сама строит префиксное дерево, то это готовый инструмент
предположим, она этого не делает. В таком случае у автора был выбор: написать с нуля свою библиотеку, или же взять готовую библиотеку построения префиксных деревьев и сконвертировать её выдачу в регексп. Второй вариант мне кажется правильнее.
сейчас, когда автор уже написал свою библиотеку, можно или использовать её ограниченные возможности, или же потрудиться чуть больше, но получить полные возможности регекспов.
В таком случае у автора был выбор: написать с нуля свою библиотеку, или же взять готовую библиотеку построения префиксных деревьев и сконвертировать её выдачу в регексп. Второй вариант мне кажется правильнее.Чем же вам не угодил самый логичный вариант — выполнить поиск с помощью этого самого префиксного дерева? Зачем префиксное дерево конвертировать в регексп, а потом из регекспа обратно в перфиксное дерево?
тем, что встроенная реализация языка наверняка оптимизирована гораздо лучше, чем то, что напишу я. А в случае питона она наверняка будет ещё и не на байткоде, а на си, что ускорит её ещё больше.
встроенная реализация языка наверняка оптимизирована гораздо лучше, чем то, что напишу яОчень распространенное заблуждение. «Если что-то есть в стандартной либе, то оно там жутко заоптимизировано под все случаи жизни». Если у вас более специализированное решение «заточенное» под конкретный сценарий, то очень часто можно получить огромную прибавку в производительности. Особенно если решение имеет лучшую оценку сложности.
А в случае питона она наверняка будет ещё и не на байткоде, а на си, что ускорит её ещё больше.В случае с питоном — может быть. Но на самом деле не обязательно: есть же всякие PyPy и прочие.
Очень распространенное заблуждение.
Иногда эта позиция бывает ошибочна, но это не повод называть её заблуждением :) Для большинства ситуаций она всё-таки справедлива.
решение имеет лучшую оценку сложности
в данном случае оценка сложности одинакова, потому что алгоритм один и тот же: сравнение строки с префиксным деревом — на регекспе или на питоне
не обязательно: есть же всякие PyPy и прочие
есть, но не всегда используются, поэтому в среднем ускорение всё равно будет
в данном случае оценка сложности одинаковаПочему вы уверены, что в случае с регекспом там будет такая же сложность? Ведь регекспу нужно уметь и с другими сценариями работать. Там почти наверняка будет не просто префиксное дерево (если вообще оно), а множество дополнительных проверок, которые в данном случае будут работать вхолостую.
как я сказал выше, если реализация регулярных выражений сама строит префиксное дерево, то это готовый инструмент
Может, но не обязана. В классическом понимании регулярки вообще должны быть детерменированными, соответственно реализации алгоритмов будут сильно плясать от языка к языку, и уж точно префиксное дерево вам никто гарантировать не может.
тем, что встроенная реализация языка наверняка оптимизирована гораздо лучше, чем то, что напишу я.
А вы попробуйте прокачать скилл и писать крутые штуки на уровне крутых прогеров, почему бы и нет ;)
в данном случае оценка сложности одинакова, потому что алгоритм один и тот же: сравнение строки с префиксным деревом — на регекспе или на питоне
Не уверен, что это верно. Насколько мне известно, Python использует рекурсивный backtracking, откуда растет экспоненциальная сложность.
Вот тут есть хороший материал по поводу регулярок.
Может, но не обязана.
ну так я и написал "если". Проверить этот вариант — дело нескольких минут, но это не было сделано.
А вы попробуйте прокачать скилл и писать крутые штуки на уровне крутых прогеров, почему бы и нет ;)
потому что малы шансы того, что я один напишу код лучше, чем группа программистов, работавшая над той же задачей в реализации языка. Кроме того, если я учусь программировать, решая какую-то задачу, я не буду предлагать учебный проект в качестве библиотеки. А отношусь я так к квалификации автора потому, что за одну минуту ускорил его регекспы в два раза банальным улучшением.
Не уверен, что это верно. Насколько мне известно, Python использует рекурсивный backtracking, откуда растет экспоненциальная сложность.
согласен, это может оказаться неверным. Но это решение было бы сделать (или взять ещё одно готовое) быстрее, чем городить самому. А вот если бы после проверки оно оказалось ещё недостаточно быстрым, то имело бы смысл делать своё.
Интересно, я бы тоже ожидал аналогичную оптимизацию внутри самого движка regex'ов стандартной библиотеки, но тем не менее regex вида \b(Ruby|Python|Java|J2ee)\b все равно сильно проигрывает FlashText (я использовал бенчмарк по ссылке из комментариев к оригинальной статье).
С другой стороны, если задача ограничивается поиском ключевых слов, не содержащих пробелов внутри себя, то простой regex \b\w+\b с заменой compiled_re.sub(lambda m: rep.get(m.group(0), m.group(0)), story) (заменять вообще все слова; те, что неинтересны, заменять на самих себя) ожидаемо уделывает эту библиотеку раза в 2-3:
python ./flashtext_regex_timing_keyword_replace.py
$ python ./flashtext_regex_timing_keyword_replace.py
Count | FlashText | Regex
-------------------------------
1 | 0.00968 | 0.00412 |
1001 | 0.01066 | 0.00425 |
2001 | 0.01156 | 0.00418 |
3001 | 0.01201 | 0.00436 |
4001 | 0.01136 | 0.00436 |
5001 | 0.01133 | 0.00439 |
6001 | 0.01215 | 0.00444 |
7001 | 0.01196 | 0.00442 |
8001 | 0.01209 | 0.00445 |
9001 | 0.01218 | 0.00446 |
10001 | 0.01218 | 0.00451 |
11001 | 0.01230 | 0.00446 |
12001 | 0.01239 | 0.00452 |
13001 | 0.01263 | 0.00457 |
14001 | 0.01265 | 0.00458 |
15001 | 0.01308 | 0.00457 |
16001 | 0.01283 | 0.00451 |
17001 | 0.01301 | 0.00455 |
18001 | 0.01296 | 0.00457 |
19001 | 0.01303 | 0.00458 |
20001 | 0.01318 | 0.00462 |В общем-то, можно даже извернуться и добавить поддержку замены слов с пробелами внутри. Но это не отменяет того, что отдельная библиотека, решающая эту задачу хорошо, имеет право на жизнь, конечно.
Вот! Тоже охренел, увидев это безобразие: у человека простая задача замены по словарю, а он деревья строит.
В смысле деревья строит? Для поиска множества подстрок в строке стандартный алгоритм — Ахо-Корасик. Можно еще юзать алгоритм Укконена, если вам скорость построения дерева важна.
Алгоритм Укконена нужно юзать когда набор паттернов не известен заранее. И наоборот, алгоритм Ахо-Корасик подходит когда весь текст не известен заранее.
Что же до скорости построения дерева — обычно в задачах текст намного длиннее набора паттернов. В таких условиях алгоритм Укконена проигрывает как по времени так и по памяти.
Что же до скорости построения дерева — обычно в задачах текст намного длиннее набора паттернов. В таких условиях алгоритм Укконена проигрывает как по времени так и по памяти.
У него замена целых слов. Ему не надо искать вхождения с произвольной точки текста — только от границы слова до границы слова, тут никакие Ахо-Корасики и т.п. не нужны: выделил очередное слово, нашёл в словаре (хэш-таблица), заменил (точнее, отправил в выходной буфер или исходное слово, или подстановку), пошёл дальше.
у него там в комментариях писали, что будто бы у Rust реализация регекспов крутая
впрочем, это неважно, всё равно я вначале предложил оптимизированный регексп на префиксном дереве
А как вы предлагаете это выяснить?
Реализовал данный пример на Perl — оказалось для простых регекспов с альтарнативами
/(Ruby|Python|Java|J2ee)/ используется алгоритм Ахо-Корасик (начиная с Perl 5.10.0)
/(Ruby|Python|Java|J2ee)/ используется алгоритм Ахо-Корасик (начиная с Perl 5.10.0)
Реализация на Perl
#!/usr/bin/env perl -w
use strict;
use warnings;
use feature 'say';
use DDP;
use String::Random;
use List::Util qw/shuffle uniq/;
use Time::HiRes qw/gettimeofday tv_interval/;
use Text::TabularDisplay;
use Storable;
my @columns = qw/Count PerlRegexp PythonFlashText PythonRegexp/;
my $table = Text::TabularDisplay->new(@columns);
# generate a random word of given length
my $string_gen = String::Random->new;
my @all_words = map { $string_gen->randpattern('c' x (3 .. 8)[int rand 6] ) } 1 .. 100_000;
my @rows;
for (my $keywords_length = 1; $keywords_length <= 20001; $keywords_length += 1000) {
# chose 5000 terms and create a string to search in.
my $story = join ' ', (shuffle(@all_words))[1 .. 5000];
# get unique keywords from the list of words generated.
my @unique_keywords_sublist = uniq((shuffle(@all_words))[1 .. $keywords_length]);
my ($t_start, $t_end);
if ($keywords_length <= 17_000) {
my %rep = map { $_ => '_keyword_' } @unique_keywords_sublist;
my $compiled_re = qr/(@{[join '|', keys %rep]})/;
$t_start = [gettimeofday];
$story =~ s/$compiled_re/$rep{$1}/g;
$t_end = [gettimeofday];
} else {
my @data;
while (my @uniq = splice @unique_keywords_sublist, 0, 17000) {
push @data, {
rep => { map { $_ => '_keyword_' } @uniq},
compiled_re => qr/(@{[join '|', @uniq]})/,
}
}
$t_start = [gettimeofday];
$story =~ s/$_->{compiled_re}/$_->{rep}{$1}/g for @data;
$t_end = [gettimeofday];
}
push @rows, [$keywords_length, sprintf("%.5f",tv_interval($t_start, $t_end))];
# say sprintf("%6d | %.5f |", $keywords_length, tv_interval($t_start, $t_end));
}
my %python_rows = (
1 => [0.01188, 0.0005 ],
1001 => [0.01347, 0.07646],
2001 => [0.01381, 0.19431],
3001 => [0.01370, 0.29055],
4001 => [0.01381, 0.37468],
5001 => [0.01407, 0.45641],
6001 => [0.01418, 0.54225],
7001 => [0.01425, 0.60971],
8001 => [0.01449, 0.68178],
9001 => [0.01484, 0.74831],
10001 => [0.01478, 0.81751],
11001 => [0.01497, 0.88625],
12001 => [0.01496, 0.94201],
13001 => [0.01512, 0.98292],
14001 => [0.01520, 1.04620],
15001 => [0.01551, 1.07280],
16001 => [0.01553, 1.16832],
17001 => [0.01611, 1.25071],
18001 => [0.01581, 1.37876],
19001 => [0.01585, 2.60501],
20001 => [0.01600, 2.94057],
);
push @$_, @{$python_rows{$_->[0]}} for @rows;
$table->add(@$_) for @rows;
say $table->render;
Результат
+-------+------------+-----------------+--------------+
| Count | PerlRegexp | PythonFlashText | PythonRegexp |
+-------+------------+-----------------+--------------+
| 1 | 0.00004 | 0.01188 | 0.0005 |
| 1001 | 0.00131 | 0.01347 | 0.07646 |
| 2001 | 0.00183 | 0.01381 | 0.19431 |
| 3001 | 0.00231 | 0.0137 | 0.29055 |
| 4001 | 0.00303 | 0.01381 | 0.37468 |
| 5001 | 0.00338 | 0.01407 | 0.45641 |
| 6001 | 0.00403 | 0.01418 | 0.54225 |
| 7001 | 0.00462 | 0.01425 | 0.60971 |
| 8001 | 0.00456 | 0.01449 | 0.68178 |
| 9001 | 0.00492 | 0.01484 | 0.74831 |
| 10001 | 0.00495 | 0.01478 | 0.81751 |
| 11001 | 0.00542 | 0.01497 | 0.88625 |
| 12001 | 0.00546 | 0.01496 | 0.94201 |
| 13001 | 0.00571 | 0.01512 | 0.98292 |
| 14001 | 0.00549 | 0.0152 | 1.0462 |
| 15001 | 0.00600 | 0.01551 | 1.0728 |
| 16001 | 0.00624 | 0.01553 | 1.16832 |
| 17001 | 0.01046 | 0.01611 | 1.25071 |
| 18001 | 0.00846 | 0.01581 | 1.37876 |
| 19001 | 0.00864 | 0.01585 | 2.60501 |
| 20001 | 0.00907 | 0.016 | 2.94057 |
+-------+------------+-----------------+--------------+Графики
Теперь понял ваш вопрос! Вариант интересный, но не забывайте, что у нас 20k-100k ключевых слов. Подобный Regex будет весьма сложным. Насколько я помню принцип работы регулярных выражений из примеров в томике Страуструпа, то в их работе лежит рекурсивный принцип (могу ошибаться). А любая рекурсия это увеличенный расход памяти. При сложном Regex да и на большом объеме документа (а он большой) могла банально закончиться память.
P.S. Прогонял всё-таки не я, а автор. Обращаю внимание что это перевод. Я не могу присваивать себе заслуги автора :) Кстати автор оригинала (Vikash) очень коммуникабельный человек, если у вас будут интересовать более глубокие детали, то можете и его смело спрашивать. Мне он отвечал в течении нескольких часов.
P.S. Прогонял всё-таки не я, а автор. Обращаю внимание что это перевод. Я не могу присваивать себе заслуги автора :) Кстати автор оригинала (Vikash) очень коммуникабельный человек, если у вас будут интересовать более глубокие детали, то можете и его смело спрашивать. Мне он отвечал в течении нескольких часов.
100k слов даже по 100 символов это 10 мегабайт памяти, без учёта более коротких слов и «повторного использования» префиксов
посмотрю, что автору в исходной записи накомментировали
посмотрю, что автору в исходной записи накомментировали
Рекурсивные алгоритмы разбора используются в качестве обучающих и для небольших объёмов данных, насколько мне известно, нормальные реализации всё-таки используют конечные автоматы.
Поправлю. Есть два разных разновидности языка регулярок: с возвратными ссылками и без них. По регулярке второго типа можно построить конечный автомат. По регулярке первого типа в общем случае автомат построить нельзя — а потому библиотеки которые поддерживают обратные ссылки обычно КА строить не умеют.
Поправлю. Есть такой тип конечных автоматов — ДКА с магазинной памятью (ДМПА), которые позволяют разбирать даже контекстно-свободные грамматики. Думаю, с регулярками с обратными ссылками такие автоматы тоже могут справиться.
Что-то мне кажется, что регулярка с обратными ссылками контекстно-зависима. По крайней мере, я не вижу способа представить (a*)(b*)c\1+\2+ в виде КС-грамматики.
PS ДМПА — это расширение КА а не их тип
Не хочу спорить о терминологии, как и разводить лишнюю полемику. См. Реализации
регулярных выражений.
Цитата:
регулярных выражений.
Цитата:
NFA (англ. nondeterministic finite-state automata — недетерминированные конечные автоматы) используют жадный алгоритм отката, проверяя все возможные расширения регулярного выражения в определённом порядке и выбирая первое подходящее значение. NFA может обрабатывать подвыражения и обратные ссылки. Но из-за алгоритма отката традиционный NFA может проверять одно и то же место несколько раз, что отрицательно сказывается на скорости работы. Поскольку традиционный NFA принимает первое найденное соответствие, он может и не найти самое длинное из вхождений (этого требует стандарт POSIX, и существуют модификации NFA выполняющие это требование — GNU sed). Именно такой механизм регулярных выражений используется, например, в Perl, Tcl и .NET.
(комментарий был удален)
Как скажете.
Хочу, правда, отметить, что
Рекомендую ещё посмотреть, что пишет Microsoft про реализацию регулярных выражений.
А именно:
Хочу, правда, отметить, что
Но из-за алгоритма отката традиционный NFA может проверять одно и то же место несколько раз, что отрицательно сказывается на скорости работы., так что одного суждения по времени работы будет недостаточно. А ещё рекурсивный поиск обычно не используется не столько из-за времени работы, сколько из-за потребляемой памяти, так что замерьте ещё потребление памяти, раз уж берётесь за такое. Если оно тоже быстро растёт — тогда я с вами соглашусь.
Рекомендую ещё посмотреть, что пишет Microsoft про реализацию регулярных выражений.
А именно:
The .NET Framework regular expression engine is a backtracking regular expression matcher that incorporates a traditional Nondeterministic Finite Automaton (NFA) engine such as that used by Perl, Python, Emacs, and Tcl. This distinguishes it from faster, but more limited, pure regular expression Deterministic Finite Automaton (DFA) engines such as those found in awk, egrep, or lex. This also distinguishes it from standardized, but slower, POSIX NFAs.
Если слова заменяются целиком, возможно hash словарь замен будет быстрее.
is 'Python' in sentence?
is 'Java' in sentence?
...
Но регексы работают не так.
Вообще, без результатов профилировки решения на регексах статья бесполезна чуть менее чем полностью. Может он там на каждую операцию поиска компилирует регекс, вот и получил O(n) от количества термов.
Регексы, может, работают и не так — но автор, видимо, их использовал именно так.
Я теряюсь в догадках, как использовать регексы так чтобы был O(n)? Сделать по регексу на каждый из термов и ручками их перебирать? Тогда начерта вообще регексы, цикл из strstr по каждому из термов и даст O(n) от количества термов. Но регекс вида (term1|term2|term3|...term4) работает не так.
Сделать по регексу на каждый из термов и ручками их перебирать?
Если посмотреть вопрос автора на SO — будет видно что именно так он и сделал.
Короче, автор просто не умеет пользоваться регексами. На фигню в его вопросе на SO вы уже указали, а в Код для получения бенчмарков, используемых для графиков, представленных выше можно найти здесь он таки действительно компилирует регекс на каждый из документов.
Статью закопать, автора отправить читать документацию.
Статью закопать, автора отправить читать документацию.
Это зависит от алгоритма. В Perl, Python, Ruby, Java и т.д. регекс вида (term1|term2|term3|...term4) работает как раз за O(N) от количества термов, т.к. там NFA строится. Чтоб это работало за O(1) от количества термов, нужно строить DFA — например, это делает библиотека re2 (можно и из питона использовать), и дефолтные движки регэкспов в Go и Rust.
В основе FlashText лежит второй подход. В его реализации так же использованы алгоритм Ахо-Корасик и префиксное дерево.
Впервые вижу, чтобы классический алгоритм «из учебника» рекламировали с таким пиететом, мемасиками, графиками и приведениями цитат из твитера.
«Как я начал использовать индексы и сократил алгоритмическую сложность задачи с O(N) до O(1)». Нам это на первом курсе преподавали.
А лексер на основе ANTLR не пробовали использовать? По идее он тоже должен быстро отрабатывать, правда придется вводить кучу ключевых слов в него и генерировать.
Интересно, что же автор статьи hyperscan не взял?
pyahocorasick — и не нужно изобретать велосипед.
Кстати, в статье описано простое префиксное дерево, которое построит движок регулярных выражений, если добавить в него все альтернативы через ИЛИ. А Ахо-Корасик работает несколько сложнее: у него есть переходы между ветками, благодаря чему не нужно перезапускать поиск на каждом символе (или делать возвраты в переборе).
Кстати, в статье описано простое префиксное дерево, которое построит движок регулярных выражений, если добавить в него все альтернативы через ИЛИ. А Ахо-Корасик работает несколько сложнее: у него есть переходы между ветками, благодаря чему не нужно перезапускать поиск на каждом символе (или делать возвраты в переборе).
В комментариях автор пишет что пробовал, но не смог настроить поиск по целым словам. Если это таки возможно, автору бы точно пригодилось. Специализированная библиотека большей частью написанная на C явно будет быстрее.
Они выражают это в танце в коде.
высокая коммуникабельность является стимулирующим фактором роста коммюнити
или, как говорили в древней Японии «для сегуна ценнее тысяча простых солдат, чем один искусный самурай»
или, как говорили в древней Японии «для сегуна ценнее тысяча простых солдат, чем один искусный самурай»
Индус даже статью по этому поводу выпустил: https://arxiv.org/abs/1711.00046
Где это используют? Для дорвеев?
возможно будет интересен этот проект: github.com/noprompt/frak, как раз про ваши тысячи слов.
Я сделяль тест на регулярах (правда в жаве, как жава кодер) с одинаковым кол-вом параметров (7 ключевых слов на входной док в 300 мегабайт)
flashtext 22 секунды
java регулярка: 5.2 секунды
Ну хоть результат один и тот же. По крайней мере работает правильно…
flashtext 22 секунды
java регулярка: 5.2 секунды
Ну хоть результат один и тот же. По крайней мере работает правильно…
так… библиотека хорошая но…
ведь можно было просто написать StringTokenizer (https://docs.oracle.com/javase/7/docs/api/java/util/StringTokenizer.html) и за (практически) O(N) время найти/заменить все слава… никак?
ведь можно было просто написать StringTokenizer (https://docs.oracle.com/javase/7/docs/api/java/util/StringTokenizer.html) и за (практически) O(N) время найти/заменить все слава… никак?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я написал приложение, которое за 15 минут делало то же самое, что и регулярное выражение за 5 дней