Dotaz: multi regexp

[Zaboj Campula]

Zdravim vsechny,

Vstup

• Mam mnozinu regularnich vyrazu (radove tisice).
• a mam jeden textovy retezec.

Problem

• Najit alespon jeden regularni vyraz ktery s shoduje s retezcem nebo vratit chybu.

Jazyk

• idealne c/c++

Sekvencni prochazeni vsech regularnich vyrazu a test na shodu je pomale.

Ma nekdo nejaky napad na chytry algoritmus?

Odpovědi

[Kit]

Spojit těch 1000 regulárních výrazů do jednoho?

[extremni lama]

pokud potrebuje vedet i ktery z nich matchuje tak to nebude tak jednoduchy.

Napada me treba:

- nejdriv udelas jeden velky RE, ktery vrati match pokud libovolny z tech 1000 RE by vratil match

- vyzkousis a pokud najde match, tak:

- vytvoris si 2 novy RE. Jeden bude spojovat puvodni RE 1 .. 500, ten druhy bude spojovat puvodni RE 501 .. 1000

- vyzkousis match s kazdym z tech dvou

- ten ktery vrati shodu znovu rozdelis, atd...

Ty spojovaci RE by sis mohl predpocitat a umistnit do binarniho stromu, ktery bys potom prochazel od korene k listum...

Takze bys vzdycky zkousel log2(N) RE.

[extremni lama]

jeste bych doplnil ze tohle by melo fungovat dobre pokud pouzivas regex engine ktery si to vnitrne prevadi na FA.

Pokud vnitrne pouziva backtracking tak to asi nepomuze...

[Zaboj Campula]

To jako kdybych mel dejme tomu regularni vyrazy

• A.*B
• A[AB]C
• D$

Tak udlat jeden \(A.*B\|A[AB]C\|D$\) To by mozna slo, ale nejsem si jisty jestly by to bylo o moc rychlejsi nez sekvencni prohledavani. Zmerim a dam vedet.

[Kit]

Přesně tak. Záleží na kvalitě kompilátoru regulárního výrazu, ale předpokládám řádové zrychlení oproti sekvenčnímu prohledávání.

Některé jazyky (např. PHP) umožňují zadat regulární výrazy do pole. Netuším, jak je to s rychlostí.

[wamba]

No v Perl-u jsem to zkoušel a dokážu najít případy, kdy to bude rychlejší i o dost pomalejší

#!/usr/bin/perl
use 5.010;
use warnings;
use strict;
use List::Util qw{first};
use Benchmark;
our $VERSION = 0.001;

my $string =
'234781802319q8019810328103982104398021483049823094830498023982094823028340932840923830483201223';

my @multiregexp = ( qr{ \A \d+ . \z }msx, qr{ \$ }msx, );

timethese(
    1000000,
    {
        more => sub {
            my $trueregexp = first { $string ~~ $_ } @multiregexp;
        },
        one => sub { my $tt = $string ~~ m{\A \d+ . \z|\$}msx ? 1 : 0; },
        one_better =>
          sub { my $tt = $string ~~ m{\A \d+ . \z|\A .* \$ .* \z}msx ? 1 : 0; },
    }
);

mi vypíše

Benchmark: timing 1000000 iterations of more, one, one_better...
      more:  3 wallclock secs ( 2.72 usr +  0.00 sys =  2.72 CPU) @ 367647.06/s (n=1000000)
       one: 14 wallclock secs (13.69 usr +  0.01 sys = 13.70 CPU) @ 72992.70/s (n=1000000)
one_better: 12 wallclock secs (12.06 usr +  0.00 sys = 12.06 CPU) @ 82918.74/s (n=1000000)

když $string upravím a přidám na konec $, tak

      more:  3 wallclock secs ( 3.21 usr +  0.00 sys =  3.21 CPU) @ 311526.48/s (n=1000000)
       one: 12 wallclock secs (13.74 usr +  0.00 sys = 13.74 CPU) @ 72780.20/s (n=1000000)
one_better:  1 wallclock secs ( 2.04 usr +  0.00 sys =  2.04 CPU) @ 490196.08/s (n=1000000)

a když smažu q z takto upraveného $string

      more:  3 wallclock secs ( 2.18 usr +  0.00 sys =  2.18 CPU) @ 458715.60/s (n=1000000)
       one:  1 wallclock secs ( 1.39 usr +  0.00 sys =  1.39 CPU) @ 719424.46/s (n=1000000)
one_better:  0 wallclock secs ( 1.36 usr +  0.00 sys =  1.36 CPU) @ 735294.12/s (n=1000000)

atp.

[wamba]

a to first ještě dá na výstup, který ten regexp bude true ještě se to dá otestovat jako

 more_better => sub {
            my $tt = $string ~~ @multiregexp ? 1 : 0;
          }

které je nejrychlejší ve všech předešlých případech

[Mr.S1lent.cz]

Nebo taky muzes zaindexovat hledany retezec a napsat custom regexp nastroj pro vyhledavani v indexu :)

[Zaboj Campula]

Omlovam se, ale nechapu. Slo by ten napad nejak rozvest, abych ho pochopil i ja?

[Mr.S1lent.cz]

Zalezi na povaze vstupu, z toho musis vychazet.

1) je to nahodny retezec vsech pismen nebo jen velkych a malych, cisel, specialnich znaku? 2) regexpy jsou generovany obecne na nejake mnoziny znaku nebo primo na nejaky konkretni retezce?

To zaindexovani ti odhalim, az ty mi zodpovis tyto dva body, jinak to nema smysl :)

[wamba]

tak abych odpověděl navrhuji použít Perl

use 5.010;
use warnings;
use strict;
use List::Util qw{first};
our $VERSION = 0.001;

my $string =
'23478180231x98019810328103982104398021483049823094830498023982094823028340932840923830483201223$';

my @multiregexp = ( qr{ \A \d+ . \z }msx, qr{ \$ }msx, );
my $trueregexp = first { $string ~~ $_ } @multiregexp;

say 'tento regexp vyhovuje ', $trueregexp;

a když to nebude dostatečně rychlé, tak to chce vědět více o těch regexp-ech popř. o tom řetězci, aby se dalo navrhnout něco efektivnějšího

[Zaboj Campula]

Takze dekuji vsem za kometare.

Spojeni do jednoho velkeho regexpu jak je navrzeno vyse by snad splnilo podminku na rychle vyhledavani, nicmene jsem skoncil na tom ze je potreba i pomerne rychla reakce na to kdyz uzivatel nejaky regulani vyraz prida/ubere/zmeni a konstrukce toho dloooouheho regularniho vyrazu a jeho kompilace je prilis pomala.

Vysledne reseni je nakonec zalozene na tom, ze ty regularni vyrazy - tedy alespon vetsinaz nich ma v sobe nejaky pevny retezec, napriklad "[0-9]ABC[0-9]" a pomoci techto retezcu lze udelat index a v tom indexu najit podmnozinu regexu ktere se pak matchuji sekvencne. Vetsinou jsou to regexy slozitejsi nez v tom prikladu, ale obvykle to jde a tech par stovek regexu, ze kterych se neda nejaky rozumny retezec vyextraovat se bude prochazet sekvencne az kdyz se nenajde jinde.