RE2: wyrażenia regularne na automatach komórkowych od Google'a

Wyrażenia regularne to jedno z podstawowych narzędzi każdego programisty, lubiane zresztą chyba przez wszystkich zaawansowanych użytkownikow komputerów. Towarzyszą nam od lat siedemdziesiątych, kiedy to Ken Thompson wprowadził w edytorze tekstowym QED. Jednak korzystanie ze złożonych regexpów oznacza często kłopoty – niekontrolowane zużycie stosu i wykładniczo rosnący czas realizacji. Problem tkwi w algorytmie znanym jako backtracking.

Backtracking to ogólny sposób rozwiązywania niektórych problemów informatycznych, w którym stopniowo buduje się kandydatów na rozwiązania, a następnie porzuca każdego częściowego kandydata, zaraz jak tylko ustalone zostanie, że nie może on przynieść kompletnego rozwiązania.

Metoda ta jest stosowana w praktycznie wszystkich implementacjach wyrażeń regularnych, korzystają z niej takie klasyczne narzędzia jak sed, grep czy awk, trafiła też do popularnych języków skryptowych, takich jak Perl, JavaScript czy Python. Jak pisze Russ Cox, inżynier z Google'a, w Mountain View korzysta się z regexpów jako interfejsu do wielu zewnętrznych i wewnętrznych systemów – w tym Code Search, Sawzall i BigTable. Systemy te przetwarzają wielkie ilości danych, więc realizacja operacji przy wykładniczo rosnącym czasie jest nie do przyjęcia.

Na szczęście istnieje inne podejście do wyrażeń regularnych – wykorzystuje ono teorię automatów komórkowych i gwarantuje realizację operacji w liniowym czasie, przy ustalonym rozmiarze stosu. Korzystając z tego podejścia Google stworzyło bibliotekę RE2, która stanowi zamiennik dla znanych powiązań PCRE dla C++.

Teraz biblioteka RE2 została wydana na wolnej licencji BSD – każdy programista może zastosować ją w swoich projektach. Dokumentacja oraz kod źródłowy dostępne są na stronie code.google.com/p/re2/. Osoby zainteresowane matematycznymi szczegółami implementacji wyrażeń regularnych za pomocą automatów komórkowych powinny zerknąć na stronę swtch.com/~rsc/regexp/regexp1.html.

Źródło: google-opensource.blogspot.com

Podoba Ci się ten tekst? Powiedz o tym innym na Fb: lub na G+:

publikuj:

wydrukuj

2 skomentuj »

Komentarze

#1 Jan Koprowski^® 2010-03-15 09:02:38 0
Te wykresy przypominają mi trochę funkcję logarytmiczną. Jestem ciekaw czy ta funkcja ma jakąś asymptotę, czy jej granica w nieskończoności wynosi nieskończoność. Ciekawe wnioski można byłoby też wysnuć gdyby narysować ją na skali logarytmicznej - ciekawa sprawa :]
IP: 192.198.151.[...] Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US) AppleWebKit/532.5 (KHTML, like Gecko) Chrome/4.0.249.89 Safari/532.5
#2 gość przypadkowy 2011-03-07 10:30:00 0
Ciekawa rzecz, ale ...autorowi chyba pozajączkowały się automaty? Algorytm opiera się na niedeterministycznym automacie skończonym, nie automacie komórkowym.
IP: 62.233.147.[...] Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; WOW64; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; .NET4.0C; .NET4.0E)

Aby dodać komentarz, musisz podać swój nick, treść komentarza oraz poprawnie przepisać oba słowa z obrazka (słowa muszą być rozdzielone spacją).
W treści komentarza można używać języka formatowania BBcode.