Pokročilé regulární výrazy

17. 8. 2014 v kategorii code • 11 min. čtení

Mind the age! Most likely, its content is outdated. Especially if it’s technical.

Říká se, že pokud má člověk problém a rozhodne se ho vyřešit pomocí regulárních výrazů, má najednou problémy dva. S tím nesouhlasím. Teda částečně – regulární výrazy jsou mocná zbraň. Musí se však umět použít…

Kdysi mi kolega ukazoval, jak si udělal funkci „oddělovač tísíců“. Popravdě se mi to ani nechtělo louskat a přišel jsem s regulárním výrazem:

>>> def groupjoin(s, sep, groupby):
...     return re.sub(r'(?<=\d)(?=(?:\d{%d})+$)' % groupby, sep, s)
...
>>> groupjoin('123456789', ',', 2)
'1,23,45,67,89'
>>> groupjoin('123456789', ',', 3)
'123,456,789'

Mnohem lepší! Hned je to čitelnější. Bohužel ale ani tohle řešení moc lidí nedokáže přečíst. Jelikož je možné regulární výrazy využít téměř všude a s úspěchem je lze použít třeba i na hledání jehly v kupce sena (= slova v gigabajtových lozích), je škoda je neumět využít. S tím vám nyní trochu pomůžu. :-)

Základy

Předpokladem je, že už znáte základy. To jest tento seznam:

^ – začátek řetězce,
$ – konec řetězce,
. – jakýkoliv znak,
? – předchozí pravidlo se může a nemusí vyskytovat,
+ – předchozí pravidlo se musí vyskytovat minimálně jednou,
- – předchozí pravidlo se může vyskytovat kolikrát chce,
{m} – předchozí pravidlo se musí vyskytovat m-krát,
{m,n} – předchozí pravidlo se musí vyskytovat minimálně m-krát a maximálně n-krát,
[abc] – jeden z vypsaných znaků (zde konkrétně a, b nebo c),
[^abc] – opak předchozího (zde konkrétně cokoliv, kromě a, b nebo c),
a|b – logické nebo (zde konkrétně a nebo b),

Pokud tato pravidla nemáte v krvi, raději si uložte tuto stránku do záložek a vraťte se sem později. Mohlo by se totiž stát, že vás dalšími pravidly od regulárních výrazů odradím. :-)

Tak pojďme na to!

Budeme pracovat s tímto řádkem z logu nginxu:

127.42.256.512 - - [16/Aug/2014:11:35:39 +0200] "GET / HTTP/1.1" 200 9730 "-" "Mozilla/5.0 (X11; CrOS x86_64 5978.26.0) AppleWebKit/537.36 (KHTML, lik
e Gecko) Chrome/37.0.2062.29 Safari/537.36"

Regulár Nenažranec

Z daného řádku chceme získat IP adresu. Začnete psát například takovýto regulární výraz: „.*“ (na konci je mezera), tedy vše do mezery. Vypadá to dobře, spustíte a máte výsledek… až po poslední mezeru. Jak je to možné? Protože regulární výrazy jsou by default nenažrané, greedy. To znamená, že se pokusí najít co nejdelší výsledek, který je možný.

Sice uvedený regulární výraz by šel vylepšit tak, aby greedy vlastnost nevadila, ale to teď ponechme stranou. Hladovost lze totiž změnit jednoduše otazníkem. Pokud za znaky plus, hvězdička či otazník přidáte otazník, rázem dostanete co nejkratší výsledek. „.*?“.

Cvičení: co se stane, pokud předchozí regulární výraz provedete bez mezery?

Odpověď: nevrátí nic. Protože minimum opakování pro hvězdičku je nulakrát. Mezera na konci nám zajišťovala, že se musí najít něco a jedna mezera. Pokud by mezera byla na začátku řetězce, výsledek by byl pouze ta mezera.

Hledej, ale nežer

Z předchozí sekce jsme získali IP adresu, super. Co ale ta mezera na konci? Regulární výrazy vrací vše, co matchnou a my máme mezeru v našem výrazu, tak ji dostaneme. Existuje konstrukce, díky kterým můžeme vyhledávat a nic nevracet. Ukážeme si to rovnou na ukázce: „.*?(?= )“

Této konstrukci se říká lookahead (dopředné vyhledávání) a volně si ji můžete přeložit jako „matchni, pokud následuje mezera, ale nevracej mi to do odpovědi“. Samozřejmě existují další tři varianty:

(?!...) – negative lookahead (dopředné negativní vyhledávání)
(?<=...) – lookbehind (zpětné vyhledávání)
(?<!--...) – negative lookbehind (zpětné negativní vyhledávání)

Abyste tomu lépe rozuměli, představte si kurzor, který se pohybuje textem. .* bude postupně zaznamenávat pro výsledek a posouvat se textem dál. Jakmile se narazí na lookahaed či lookbehind, kurzor zůstává na svém místě a jen se nahlíží, zda je dál, co má být. Tím, že se nahlíží a kurzor stojí na místě, pokud by následovalo další požírání, vzalo by se to, na co se nahlíželo. Například re.findall("a(?=bcd).", "abcd") vrátí ab.

Cvičení: najděte v našem řádku verzi Chrome prohlížeče, pokud je na architektuře x86_64.

Odpověď: to byla ode mne podpásovka. Není možné vyřešit pomocí lookbehind či lookahead. Lákalo by napsat něco takového: (?<=x86_64.*)Chrome/.*?(?= ), jenže lookbehind nesmí mít různou délku. Délka hledaného řetězce musí být jasná. Jinými slovy nelze v lookbehind využít +, * či {m,n}. Škoda.

Skupiny

Předchozí cvičení není neřešitelné. Lze vyřešit pomocí skupin. Než to složitě popisovat, rovnou ukázka:

x86_64.*(?P<chrome_version-->Chrome/.*?)[ ]

Například v Pythonu lze pak použít takto:

>>> re.search(r'x86_64.*(?P<chrome_version>Chrome/.*?)[ ]', line).group('chrome_version')
'Chrome/37.0.2062.29'

Takových skupin si můžete udělat kolik potřebujete. Příklad pro parsování hodin z našeho logu: (?P<hour>\d{1,2}):(?P<minutes>\d{2}):(?P<seconds>\d{2}) (všimněte si, že jsem nespecifikoval nic dalšího; prostě hledám formát hodin v daném textu).

Skupiny si nemusíte pojmenovávat. Už jen použití závorek vytvoří novou skupinu a ve výsledku jsou pak nepojmenované skupiny v seznamu za sebou číslované od jedné (nula je vyhrazena pro celou odpověď). Je však lepší si skupiny pojmenovat, tím je čitelnější regulární výraz a hlavně pozdější využití dat.

Samozřejmostí je možnost využít skupiny (ať pojmenované či nikoliv) při nahrazování textu. Vhodné pro převedení ISO data na český atp.

Žádné skupiny

Upravme nyní náš výraz, aby nevyužíval pojmenované skupiny. Jen na chvíli pro demonstraci další důležité vlastnosti. A přidejme podmínku, že nás zajímá Chrome nebo Safari. Podíváme se, co jsme získali za skupiny:

>>> re.search(r'x86_64.*((Chrome|Safari)/.*?)[ ]', line).groups()
('Chrome/37.0.2062.29', 'Chrome')

Jak je vidět, opravdu jakékoliv použití závorek znamená automaticky další skupinu. Lze to nějak eliminovat, aby ve výsledku nebyl bordel? Jasně, že lze. Konstrukcí (?:...).

Áá, už dost…

Vrátíme se k lookahead a zkombinujeme to se skupinami. V regulárních výrazech lze vyhledávat podle předchozích skupin. Může se to hodit například pro vyhledávání v HTML. Naleznete otevírací tag a musíte najít stejný uzavírací tag. Konstrukce vypadá nějak takto: (?P=group).

Jednoduché. Použití na HTML nechám jako cvičení. My tu uděláme něco zajímavějšího – nalezneme v daném řádku logu všechna čísla, která se vyskytují více, než jednou. Půjdeme na to postupně:

Nejprve část hledající čísla: \d+
Číslo si zapamatujeme: (?P<number>...)
Dále to musíme obalit koncem čísla, abychom nevraceli jen část čísla: (?<!--\d)...(?!\d)
A tuto novou skupinu využijeme ke konci k nalezení toho samého čísla: .*(?P=number)
Druhé číslo však musíme taky hledat celé, takže aplikujeme znovu třetí krok.
Výsledky se bohužel vracejí nepřekrývající se. To znamená, že momentálně by nám nula znemožnila nalézt číslo 537 a to zase 36. Protože zatím se nám kurzor hýbe i při hledaní druhého čísla. Napravíme dalším použitím lookahead, protože jich tu máme málo. :-)

Výsledek:

-->>> re.findall(r'(?<!--\d)(?P<number-->\d+)(?!\d)(?=.*(?<!--\d)(?P=number)(?!\d))', line)
['11', '1', '0', '0', '537', '36']

Dobré, což?

Může vzniknout otázka, proč se ohraničení čísla nedá také do skupiny, aby se to ve výrazu nemuselo opakovat. Jde o to, že chci vyhledat stejné číslo, ale co je kolem čísla může být pokaždé jiné. Popravdě lookahead a lookbehing fungují tak, že při znovupoužití skupiny matche i když se jedná o jiné ohraničení čísla, ale bohužel to vyhledá i části čísel. Což jsem úplně nepochopil a tak je lepší se tomu vyhnout. :-)

Mimochodem pokud bude potřeba konkrétně v Pythonu někdy hledat překrývající se výsledky, lze případně využít modul regex, který obsahuje parametr overlapped.

Optimalizace

Ještě než se pustíme do vysvětlení úvodního regulárního výrazu, dovolím si nakousnout něco o optimalizaci. Osobně neznám detailně všechny možné implementace regulárních výrazů a tak jsem nikdy neřešil víc, než základní optimalizaci. Zatím jsem si s tím však vystačil. Pokud vám stačit nebude, toto rozhodně není vše, jen špička ledovce.

Jako základ je používat nezachytávající se závorky. Tím ušetříte dost zbytečné režie. Tedy pokud je to možné, použijte (?:...) místo pouze závorek.

Další rada se týká greedy a non-greedy vyhledávání. Mějme na paměti, že u greedy verze se nejprve zkusí pohltit vše, co lze, a pokud nelze najít, ubere se znak a zkusí se pokračovat znovu. A pak znovu. A znovu… I když je výsledek stejný pro greedy i non-greedy verzi, neznamená to, že je to stejné výkonově. Mějme příklad, že chci z našeho řádku vše do prvních dvou pomlček. Jelikož dvě pomlčky jsou na začátku, rychleji se k výsledku dobere non-greedy verze:

-->>> timeit.timeit("re.search(r'.* - -', s)", setup)
1.4329700469970703
>>> timeit.timeit("re.search(r'.*? - -', s)", setup)
1.0607848167419434

Pokud tedy víte, jak běžně vypadá text, ve kterém vyhledáváte, použijte tuto znalost při tvoření regulárního výrazu. Vyplatí se to.

Vysvětlení výrazu ze začátku

Nyní byste měli bez problému přečíst regulár ze začátku.

>>> def groupjoin(s, sep, groupby):
...     return re.sub(r'(?<=\d)(?=(?:\d{%d})+$)' % groupby, sep, s)

Část (?:\d{3})+ vyhledává skupiny čísel. Nezachytávání jsme použili čistě kvůli optimalizaci (s timeit 3.2 versus 3.6 sekundy). Tyto bloky hledá tak dlouho, dokud nenarazí na konec řetězce. Jelikož je to ale celé v lookahead, nikam se kurzor neposune, ani nic nepožere. Nalezne to pouze místo, kam přidat oddělovač. Funkce sub sice provádí náhradu, v tomto případě ale vlastně děláme vložení (nahrazujeme místo v řetězci). Lookbehind na začátku je proto, aby se nevložil oddělovač úplně na začátek, viz druhé ukázkové volání funkce.

Nic složitého, že? :-)

A pro vás, kteří jste stále greedy, mám doporučení v podobě knihy Mastering Regular Expressions.