8. Rozpoznávání vzorů a regulární výrazy

Obsah

Strukturální rozpoznávání vzorů
Regulární výrazy

Strukturální rozpoznávání vzorů

Tzv. structural pattern matching (v Pythonu od verze 3.10) je způsob, jak porovnávat datové struktury na základě jejich vzorů a provádět různé akce podle toho, čemu daná struktura odpovídá. Tento přístup se v některých ohledech podobá tomu, co známe například ze switch-case příkazu v jiných programovacích jazycích, ale v Pythonu je díky tomu možné provádět mnohem komplexnější kontrolu a zpracování dat. Více naleznete zde a zde.

Syntaxe pro strukturální pattern matching používá klíčové slovo match, za kterým následuje výraz, který chceme zkontrolovat, a poté několik case bloků s různými vzory.

## testování struktury slovínku

def test_shape(data):
    match data:
        case {"type": "circle", "radius": r}:
            print(f"Circle with radius {r}")
        case {"type": "rectangle", "width": w, "height": h}:
            print(f"Rectangle with width {w} a height {h}")
        case _:
            print("Unknown type")


test_shape({"type": "circle", "color": "red", "radius": 5, "x": 10, "y": 20})
# Circle with radius 5
test_shape({"width": 100, "type": "rectangle", "color": "blue", "height": 50, "x": 30, "y": 90})
# Rectangle with width 100 a height 50

Jednotlivé vzory pak mohou kontrolovat nejen přítomnost samotné hodnoty, ale například i jejich datový typ nebo je kombinovat s podmínkama na konkrétní hodnoty. Zajimavé použití naleznete například v minimalistickém interpretu jazyla scheme, kde se používá strukturální rozpoznávání vzorů ve vyhodnocovacím procesu právě i pro extrakci hodnot a testování typů.

Základní konstrukce:

*_: wildcard, který rozpozná libovolný počet hodnot
*rest: rozpozná zbytek hodnot, které uloží do proměnné rest
|: logická spojka 'nebo'
str(...), float(...) atd.: test na základní datové typy
kombinace case a if pro složitější podmínky

## komplexní testování struktury seznamu

def test_shape(data):
    match data:
        # test na seznamy obsahující 'circle'
        # podmínka omezující hodnotu r
        case ["circle", r] if r < 5: 
            print(f"Small circle with radius {r} less than 5")
        case ["circle", r]:
            print(f"Circle with radius {r}")
        # seznam s circle a r obsahuje i další prvky, které se uloží do rest 
        case ["circle", r, *rest]:
            print(f"Circle with radius {r} and other values: {rest}")
        # circle a r mohou předcházet další hodnoty
        case [*_, "circle", r]:
            print(f"Circle with radius {r} at the end of data")

        # test na seznamy obsahující 'rectangle'
        # druhý a třetí prvek seznamu musí být int nebo float
        case ["rectangle", int(w) | float(w), int(h) | float(h)]:
            print(f"Rectangle with width {w} a height {h}")

        # test na seznamy obsahující 'picture'    
        # použití logické spojky or 
        case ["picture", "rectangle" | "circle"]: 
            print(f"Picture and either rectangle or circle")
        # test na existenci "circle" v items
        case ["picture", items] if "circle" in items:
            print(f"Picture with circle in items")

        # defaultní větev
        case _:
            print("Unknown type or invalid values")


test_shape(["circle", 1])
# Small circle with radius 1 less than 5

test_shape(["circle", 5])
# Circle with radius 5

test_shape(["circle", 5, 6, 7])
# Circle with radius 5 and other values: [6, 7]

test_shape([None, "circle", 5])
# Circle with radius 5 at the end of data

test_shape(["rectangle", None, None])
# Unknown type or invalid values

test_shape(["picture", "rectangle"])
# Picture and either rectangle or circle

test_shape(["picture", ["rectangle", "circle"]])
# Picture with circle in items

Mužeme testovat i jednotlivé atributy objektů.

## testování struktury objektu

class Circle:
    """Class that represents circle."""

    def __init__(self, radius):
        self.radius = radius


class Rectangle:
    """Class that represents rectangle."""

    def __init__(self, width, height):
        self.width = width
        self.height = height


def test_shape(shape):
    match shape:
        case Circle(radius=int(r) | float(r)):
            print(f"Circle with radius {r}")
        case Rectangle(width=int(w) | float(w), height=int(h) | float(h)):
            print(f"Rectangle with width {w} a height {h}")
        case _:
            print("Unknown type or invalid values")
    

test_shape(Circle(5))
# Circle with radius 5

test_shape(Rectangle(20, 30.5))
# Rectangle with width 20 a height 30.5

test_shape(Rectangle("42", 30))
# Unknown type or invalid values

Příklad: zpracování logů

Testovanou strukturou můžeme procházet libovolně hluboko a tzv. ji destrukturalizovat. Všechny tyto testy lze samozřejmě i kombinovat.

## test zanořené struktury
  # převzato z real python: https://realpython.com/structural-pattern-matching/
import json


def log(event):
    match json.loads(event):
        case {"keyboard": {"key": {"code": code}}}:
            print(f"Key pressed: {code}")
        case {"mouse": {"cursor": {"screen": [x, y]}}}:
            print(f"Mouse cursor: {x=}, {y=}")
        case _:
            print("Unknown event type")


# Příklad vstupu, kdy bylo stisknuto tlačítko na klávesnici
event1 = '{"keyboard": {"key": {"code": "Enter"}}}'
log(event1)  
# Key pressed: Enter

# Příklad vstupu, kdy se kurzor myši nachází na určité pozici
event2 = '{"mouse": {"cursor": {"screen": [300, 400]}}}'
log(event2)  
# Mouse cursor: x=300, y=400

# Příklad vstupu s neznámým typem události
event3 = '{"unknown_event": {"details": "Some data"}}'
log(event3)  
# Unknown event type

Funkce se stejnou funkcionalitou jako v předchozím příkladu, ale bez použití strukturálního rozpoznávání vzrorů.

def log_without_match(event):
    parsed_event = json.loads(event)
    if (
        "keyboard" in parsed_event and
        "key" in parsed_event["keyboard"] and
        "code" in parsed_event["keyboard"]["key"]
    ):
        code = parsed_event["keyboard"]["key"]["code"]
        print(f"Key pressed: {code}")
    elif (
        "mouse" in parsed_event and
        "cursor" in parsed_event["mouse"] and
        "screen" in parsed_event["mouse"]["cursor"]
    ):
        screen = parsed_event["mouse"]["cursor"]["screen"]
        if isinstance(screen, list) and len(screen) == 2:
            x, y = screen
            print(f"Mouse cursor: x={x}, y={y}")
        else:
            print("Unknown event type")
    else:
        print("Unknown event type")

Regulární výrazy

Regulární výrazy (také známé jako regexy) jsou sekvence znaků, které definují vzory pro vyhledávání a manipulaci s textovými řetězci. Tyto vzory jsou používány pro vyhledávání a nahrazování textu v textových řetězcích nebo pro kontrolu formátu textu.

Regulární výrazy jsou v pythonu přístupné přes balíček re (je součástí standardní knihovny) a více o něm naleznete zde. Přehled základních speciální znaků a sekvencí najdete v tabulce (převzato z w3schools):

Znak	Popis	Příklad
[]	Sada znaků	"[a-m]"
\	Označuje speciální sekvenci (lze použít i k úniku speciálních znaků)	"\d"
.	Libovolný znak (kromě znaku nového řádku)	"he..o"
^	Začíná na	"^hello"
$	Končí na	"planet$"
*	Nula nebo více výskytů	"he.*o"
+	Jeden nebo více výskytů	"he.+o"
?	Nula nebo jediný výskyt	"he.?o"
{}	Přesný počet výskytů	"he.{2}o"
\|	Buď nebo	"falls\|stays"
()	Zachytit a seskupit
\A	Vrátí shodu, pokud jsou určené znaky na začátku celého řetězce	"\AThe"
\b	Vrátí shodu, pokud jsou určené znaky na začátku nebo na konci slova	r"\bain" r"ain\b"
\B	Vrátí shodu, pokud jsou určené znaky přítomny, ale NE na začátku (nebo na konci) slova	r"\Bain" r"ain\B"
\d	Vrátí shodu, pokud řetězec obsahuje číslice (čísla od 0-9)	"\d"
\D	Vrátí shodu, pokud řetězec NEobsahuje číslice	"\D"
\s	Vrátí shodu, pokud řetězec obsahuje bílý znak	"\s"
\S	Vrátí shodu, pokud řetězec NEobsahuje bílý znak	"\S"
\w	Vrátí shodu, pokud řetězec obsahuje jakékoli znaky slov (znaky od a do Z, číslice od 0-9 a podtržítko _)	"\w"
\W	Vrátí shodu, pokud řetězec NEobsahuje žádné znaky slov	"\W"
\Z	Vrátí shodu, pokud jsou určené znaky na konci celého řetězce	"Spain\Z"

V Pythonu předpona r před řetězcem označuje, že se jedná o nezpracovaný řetězcový literál. To znamená, že zpětná lomítka v řetězci nejsou považována za escape znaky.

`re.match()`

Funkce re.match() hledá shodu s regulárním výrazem od začátku řetězce. V případě nalezení shody vrací match objekt, jinak vrací hodnotu None.

import re

txt1 = "Hello world!"

# shoda nalezena, výsledek je match object
result = re.match(r"Hello world!", txt1) 
# <re.Match object; span=(0, 12), match='Hello world!'>

# délka shody
result.span()
# (0, 12)

# rozpoznaný řetězec
result.group()
# 'Hello world!'

re.match(r"He..o", txt1) # match hledá od začátku řetězce
# <re.Match object; span=(0, 5), match='Hello'>

re.match(r"He\w\wo", txt1)  # \w je císlo 0-9 nebo písmeno a-Z a _ (podtržítko)
# <re.Match object; span=(0, 5), match='Hello'> 

re.match(r"wo..d", txt1) is None  # . je libovolný znak, pro tečku používáme \.
# True

`re.search()`

Funkce re.search() hledá shodu s regulárním výrazem na libovolném místě v řetězci. V případě nalezení shody vrací match objekt, jinak vrací hodnotu None.

import re

txt1 = "Hello world!"

re.search(r"wo..d", txt1) # search hledá kdekoliv v řetězci
# <re.Match object; span=(6, 11), match='world'>

re.search(r"^He..o", txt1) # ^ začátek řetězce
# <re.Match object; span=(0, 5), match='Hello'>

re.search(r"^wo..d", txt1) is None
# True

re.search(r"wo..d!$", txt1) # $ konec řerězce
# <re.Match object; span=(6, 12), match='world!'>

re.search(r"He.*o", txt1) # * libovolný počet výskytů
# <re.Match object; span=(0, 8), match='Hello wo'>

re.search(r"world!( Hello!)?",txt1) # ? nula výskytů nebo jeden výskyt
# <re.Match object; span=(6, 12), match='world!'>

re.search(r"He.*?o", txt1) # .*? vypne greedy přístup pro *
# <re.Match object; span=(0, 5), match='Hello'>

`re.findall()`

Funkce re.findall() vrací seznam všech podřetězců, které mají shodu s regulárním výrazem.

import re

txt2 = "Hello world! Halloween 2024!"

# findall najde všechny výskyty daného řetězce
re.findall(r"[aiueo]", txt2) # [] označuje množinu 
# ['e', 'o', 'o', 'a', 'o', 'e', 'e']

re.findall(r"\d", txt2) # \d označuje jeden znak
# ['2', '0', '2', '4']

re.findall(r"[aiueo]{2}", txt2) # {} počet výskytů
# ['ee']

re.findall(r"H[aiueo]{1}ll", txt2)
# ['Hell', 'Hall']

re.findall(r"l[^aiueo].", txt2)
#['llo', 'ld!', 'llo']

`re.sub()`

Funkce re.sub() nahrazuje všechny shody jiným podřetězcem. Řetězce nejsou mutovatelné, proto tato funkce vytvoří nový odpovídající řetězec.

import re

txt2 = "Hello world! Halloween 2024!"

# nahradíme každou samohlásku za znak *
re.sub(r"[aiueo]", "*", txt2) 
# H*llo w*rld! H*llow**n 2024!

# nahradíme každou dvojici znaků 'l' za řetězec '%dva znaky l%' 
re.sub(r"ll", "%dva znaky l%", txt2)
# He%dva znaky l%o world! Ha%dva znaky l%oween 2024!

`re.split()`

Funkce re.split() rozdělí řetězec podle každé nalezené shody.

import re

txt3 = "Hello world!!! Halloween 2024. Christmas 2024?"

# rozdělíme řetězec podle každého znaku, který není písmeno
re.split(r"\W", txt3) 
# ['Hello', 'world', '', '', '', 'Halloween', '2024', '', 'Christmas', '2024', '']

# rozdělíme řetězec podle každé sekvence znaků neobsahujcící písmena
re.split(r"\W+", txt3) 
# ['Hello', 'world', 'Halloween', '2024', 'Christmas', '2024', '']

`re.escape()`

Funkce re.escape() každému metaznaku regulárních vyrazů přidá předponu \.

import re
import string

legal_chars = string.ascii_lowercase + string.digits + "!#$%&'*+-.^_`|~:"
re.escape(legal_chars)
# "abcdefghijklmnopqrstuvwxyz0123456789!\#\$%\&'\*\+\-\.\^_`\|\~:"

Argument `flags`

Všechny funkce modulu RE přijímají volitelný argument flags, který umožňuje různé unikátní funkce a varianty syntaxe.

Například přidáním vlajky re.IGNORECASE jako argumentu funkce search povolíte vyhledávání bez ohledu na velká a malá písmena. Dále vlajka re.MULTILINE mění chování kotvicích znaků ^ a $ tak, že tyto znaky odpovídají začátku a konci každého řádku, nikoli pouze začátku a konci celého textu (na rozdíl od \A a \Z, které se vztahují vždy jen k celému řetězci).

import re
  
text = "Contact us at info@example.com or Support@Example.org."
pattern = r"\b[a-z0-9._%+-]+@[a-z0-9.-]+\.[a-z]{2,}\b" #\b znaky, které bývají na začátku a konci slova
re.findall(pattern, text)
# ['info@example.com']

# nyní s použitím re.IGNORECASE
re.findall(pattern, text, flags=re.IGNORECASE)
# ['info@example.com', 'Support@Example.org']

Capture groups

Capture groups v regulárních výrazech jsou části výrazu, které jsou uzavřeny v závorkách (...). Slouží k dvěma hlavním účelům:

Seskupení: Umožňují vám zachycovat a označovat skupiny znaků jako jednotnou jednotku. To může být užitečné například pro vytváření komplexních regulárních výrazů použitím kvantifikátorů (jako je *, +, ?, nebo {...}) na celou skupinu nebo operátoru | pro sjednocení na více skupin.
Zachycení a uchování textu: Regulární výrazy mohou obsahovat více zachycených skupin. Když se shoda nalezená pomocí regulárního výrazu najde, text, který odpovídá každé zachycené skupině, je uložen pro pozdější použití.

import re

log_entry = """
2023-06-09 12:30:45 - IP: 192.168.1.1 - GET /home/index.html - Status: 200 OK
2023-08-09 12:31:10 - IP: 192.168.1.2 - POST /api/update - Status: 201 Created
2023-11-09 12:31:45 - IP: 192.168.1.3 - DELETE /api/remove - Status: 404 Not Found
2023-12-09 12:32:05 - IP: 192.168.1.4 - PUT /api/create - Status: 500 Internal Server Error
"""

# nalezneme všechny časové značky logů, které se staly v 11. a 12. měsíci
re.findall(r"(\d{4}-(11|12)-\d{2} \d{2}:\d{2}:\d{2})", log_entry)
# [('2023-11-09 12:31:45', '11'), ('2023-12-09 12:32:05', '12')]

# nahradíme všechny POST a PUT logy řetězcem "<log_removed>"
re.sub(r"^.*?(POST|PUT).*?$", "<log_removed>", log_entry, flags=re.MULTILINE)
# "2023-06-09 12:30:45 - IP: 192.168.1.1 - GET /home/index.html - Status: 200 OK
#  <log_removed>
#  2023-11-09 12:31:45 - IP: 192.168.1.3 - DELETE /api/remove - Status: 404 Not Found
#  <log_removed>"

Všechny zachycené skupiny jsou přístupné pomocí metody .groups().

import re

# část výstupu z příkazu 'top' na mac os
top = """Processes: 631 total, 2 running, 629 sleeping, 3400 threads          00:50:23
Load Avg: 1.35, 1.60, 2.52  CPU usage: 8.87% user, 5.52% sys, 85.59% idle
SharedLibs: 610M resident, 93M data, 26M linkedit.
...
"""

top_re = re.match(r"^Processes: (\d+) total, (\d+) running, (\d+) sleeping, (\d+) threads", top)
# získáme hodnotu 1. capture grupy
top_re.group(1)
# '631'

# všechny grupy získáme pomocí .groups()
top_re.groups()
# ('631', '2', '629', '3400')

Příklad: parsování HTML

import re

# z daného řetězce chceme získat názvy přednášek
html = """<h3>Seznam přednášek</h3>
<ol>
    <li>Úvod, abeceda, řetězece, jazyk, konečný deterministický automat</li>
    <li>Vlastnosti regulárních jazyků a nedeterminismus</li>
    <li>Determinizace a regulární výrazy</li>
    <li>Další vlastnoti regulárních jazyků a pumping lemma</li>
    <li>Minimalizace</li>
    <li>Zápočtový test</li>
</ol>"""

# do 1. capture grupy uložíme řetězec bez tagů <ol> a </ol>
content = re.search(r"<ol>\s*(.*?)\s*</ol>", html, re.DOTALL) # flag DOTALL způsobí, že . rozpoznává i \n
# <re.Match object; span=(26, 338), match='<ol>\n    <li>Úvod, abeceda, řetězece, jazyk, kon>

content.group(1)
# '<li>Úvod, abeceda, řetězece, jazyk, konečný deterministický automat</li>\n    <li>Vlastnosti regulárních jazyků a nedeterminismus</li> ... <li>Zápočtový test</li>'

# subem odstraníme výskyt tagu <li> na začátku řetězce a </li> na konci řetězce
content_mod = re.sub(r"^<li>|</li>$", "", content.group(1))
# 'Úvod, abeceda, řetězece, jazyk, konečný deterministický automat</li> ... <li>Zápočtový test'

# splitem rozdělíme řetězec podle regulárního výrazu, který začíná tagem <li>, po něm 
# následuje libovolný počet bílých znaků a končí tagem a </li>
re.split(r"</li>\s*<li>", content_mod)
# ['Úvod, abeceda, řetězece, jazyk, konečný deterministický automat',
#  'Vlastnosti regulárních jazyků a nedeterminismus',
#  'Determinizace a regulární výrazy',
#  'Další vlastnoti regulárních jazyků a pumping lemma',
#  'Minimalizace',
#  'Zápočtový test']

# alternativně lze stejný proces udělat jednodušeji takto pomocí capture grup
re.findall("<li>(.*?)</li>", html)
# ['Úvod, abeceda, řetězece, jazyk, konečný deterministický automat',
#  'Vlastnosti regulárních jazyků a nedeterminismus',
#  'Determinizace a regulární výrazy',
#  'Další vlastnoti regulárních jazyků a pumping lemma',
#  'Minimalizace',
#  'Zápočtový test']

Zpětné reference

Při nahrazování funkcí re.submůžeme použít zpětné referencování capture group pomocí syntaxe \g<i> pro i-tou grupu.

import re

# chceme nahradít text odkazů 'pdf' za odpovídající název souboru, př. 'fj01.pdf' u první přednášky
html2 = """<h3>Seznam přednášek</h3>
<ol>
    <li>Úvod, abeceda, řetězece, jazyk, konečný deterministický automat (<a href="<?php echo BASE_DIR; ?>/slides/fj01.pdf">pdf</a>)</li>
    <li>Vlastnosti regulárních jazyků a nedeterminismus (<a href="<?php echo BASE_DIR; ?>/slides/fj02.pdf">pdf</a>)</li>
    <li>Determinizace a regulární výrazy (<a href="<?php echo BASE_DIR; ?>/slides/fj03.pdf">pdf</a>)</li>
    <li>Další vlastnoti regulárních jazyků a pumping lemma (<a href="<?php echo BASE_DIR; ?>/slides/fj04.pdf">pdf</a>)</li>
    <li>Minimalizace (<a href="<?php echo BASE_DIR; ?>/slides/fj05.pdf">pdf</a>)</li>
    <li>Zápočtový test</li>
</ol>"""

# takto vypadají odkazy, ze kterých chceme vyčíst název pro nový odkaz 
re.findall(r"<a href=\"(.*?)\">", html2)
# ['<?php echo BASE_DIR; ?>/slides/fj01.pdf',
# '<?php echo BASE_DIR; ?>/slides/fj02.pdf',
# '<?php echo BASE_DIR; ?>/slides/fj03.pdf',
# '<?php echo BASE_DIR; ?>/slides/fj04.pdf',
# '<?php echo BASE_DIR; ?>/slides/fj05.pdf']

# capture grupy jsou přístupné i při nahrazování pomocí \g<i> 
# \g<1> obsahuje řetězec se shodou '(<a href=\".*?)', tj. například '<a href="<?php echo BASE_DIR; ?>/slides/'
# \g<2> obsahuje řetězec se shodou '(fj.*?\.pdf)', tj. například 'fj01.pdf'
re.sub(r"(<a href=\".*?)(fj.*?\.pdf)\">.*?</a>", "\g<1>\g<2>\">\g<2></a>", html2)
# <h3>Seznam přednášek</h3>\n<ol>
#    <li>Úvod, abeceda, řetězece, jazyk, konečný deterministický automat (<a href="<?php echo BASE_DIR; ?>/slides/fj01.pdf">fj01.pdf</a>)</li>
#    <li>Vlastnosti regulárních jazyků a nedeterminismus (<a href="<?php echo BASE_DIR; ?>/slides/fj02.pdf">fj02.pdf</a>)</li>
#    ...
#    <li>Minimalizace (<a href="<?php echo BASE_DIR; ?>/slides/fj05.pdf">fj05.pdf</a>)</li>
#    <li>Zápočtový test</li>
#</ol>'

`re.finditer`

Funkce re.finditer() vrací iterátor, který iteruje přes všechny shody se vzorem, a který k těmto shodám vrací přímo match objekty. Pro každou shodu tak máme k dispozici veškerou funkcionalitu regulárního výrazu, jako například odpovídající capture grupy.

import re

log_text = """
[2025-01-22 10:15:30] User: johndoe Action: LOGIN
[2025-01-22 10:20:00] User: janedoe Action: LOGOUT
[2025-01-22 10:30:45] User: johndoe Action: UPDATE
"""

pattern = r"\[(.*?)\] User: (\w+) Action: (\w+)"
matches = re.finditer(pattern, log_text)

# iterace přes nalezené shody
for match in matches:
    timestamp = match.group(1)
    username = match.group(2)
    action = match.group(3)
    print(f"Čas: {timestamp}, Uživatel: {username}, Akce: {action}")

# vypíše se:
# Čas: 2025-01-22 10:15:30, Uživatel: johndoe, Akce: LOGIN
# Čas: 2025-01-22 10:20:00, Uživatel: janedoe, Akce: LOGOUT
# Čas: 2025-01-22 10:30:45, Uživatel: johndoe, Akce: UPDATE

Pojmenované capture grupy

Pro lepší čitelnost regulárních výrazů lze použít pojmenované capture grupy. Pomocí syntaxe (?P<name>regex) se shoda výrazu regex uloží do grupy pojmenované name. Toho lze využít například společně s funkcí re.groupdict(), která vrací aktuální hodnoty všech catch grup ve formě slovníku.

import re

log_text = """
[2025-01-22 10:15:30] User: johndoe Action: LOGIN
[2025-01-22 10:20:00] User: janedoe Action: LOGOUT
"""

# regulární výraz s pojmenovaním capture grup
pattern = r"\[(?P<timestamp>.*?)\] User: (?P<username>\w+) Action: (?P<action>\w+)"

matches = re.finditer(pattern, log_text)

# iterace přes shody 
for match in matches:
    # výpis obsahu grupy 'username'
    print(f"User: {match.group('username')}")
    # vypíše všechny pojmenované grupy formou slovníku
    print(match.groupdict())


# vypíše se:
# User: johndoe
# {'timestamp': '2025-01-22 10:15:30', 'username': 'johndoe', 'action': 'LOGIN'}
# User: janedoe
# {'timestamp': '2025-01-22 10:20:00', 'username': 'janedoe', 'action': 'LOGOUT'}

8. Rozpoznávání vzorů a regulární výrazy

Obsah

Strukturální rozpoznávání vzorů

Příklad: zpracování logů

Regulární výrazy

re.match()

re.search()

re.findall()

re.sub()

re.split()

re.escape()

Argument flags