Wiedza fundamentalna› 1. Wyrażenia regularne›Lekcja 1.6 FUND-06

Regex pod spodem: automaty i backtracking

Po tej lekcji wiesz, dlaczego większość wzorców grep dopasowuje szybko, a odwołania wsteczne potrafią go mocno spowolnić. Poznasz dwa mechanizmy: automaty i backtracking.

~4 min czytania2 pojęcia1 schemat4 pytaniasprawdzone ze źródłami 3 lis 2026

Źródła (1)

Nowe pojęcia Automat Backtracking

W jednej minucie

Definicja

Automat to maszyna stanów, na której grep opiera szybkie dopasowanie wzorców.1

Ważne

Zwykłe wzorce obsługują automaty. Odwołanie wsteczne włącza wolniejszy algorytm z cofaniem, który w najgorszym razie rosną wykładniczo.1

Zapamiętaj

Wzorzec bez \1 i bez ogromnych liczników powtórzeń jest bezpieczny dla wydajności.

Dwa dopasowywacze w jednym grepie

Do tej pory pytaliśmy, co wzorzec znaczy. Teraz pytamy, jak grep go wykonuje.

Podręcznik GNU grep opisuje to tak: część pracy robi zestaw automatów zaprojektowanych dla szybkości, a gdy wzorzec ma nietypową cechę, np. odwołanie wsteczne, przejmuje wolniejszy dopasowywacz.1

Wzorzec	Kto dopasowuje	Szybkość
bez odwołań wstecznych	automaty	szybko
z odwołaniem, np. `\1`	wolniejszy dopasowywacz	ryzyko

Według podręcznika GNU grep 3.12. Dokładny algorytm to szczegół implementacji i może się zmienić między wydaniami.

Sam podręcznik zastrzega, że algorytm to szczegół implementacji, który może się zmienić w kolejnym wydaniu.1

Automat: czytanie tekstu raz

Automat to maszyna z kilkoma stanami. Czyta tekst znak po znaku i po każdym znaku przechodzi do następnego stanu.

stateDiagram-v2
  [*] --> S0
  S0 --> S1: a
  S1 --> S1: b
  S1 --> S2: c
  S2 --> [*]

Automat dla wzorca ab*c: po a można czytać dowolnie wiele b, a po c dopasowanie kończy się.

Zacznij w stanie S0 i przeczytaj a: przechodzisz do S1.
Czytaj kolejne b: zostajesz w S1.
Przeczytaj c: przechodzisz do S2, czyli stanu końcowego.

Z praktyki

To nasz model myślowy. Podręcznik mówi tylko, że automaty są szybkie. Ta wersja jest uproszczona: nie pokazuje, jak grep buduje automat z wzorca.

Backtracking: próbuj i wracaj

Odwołanie wsteczne wymaga pamiętania, co dopasowała grupa. Automat o stałej liczbie stanów tego nie potrafi, więc grep uruchamia inny algorytm.1

Definicja

Backtracking to algorytm, który sprawdza kolejne możliwe dopasowania i wraca do wcześniejszego wyboru, gdy dalszy ciąg nie pasuje.1

W najgorszym razie sprawdza on wszystkie możliwe dopasowania, a czas rośnie wykładniczo.1 Poniższy pomiar to pokazuje.

Linia z liter a	Wzorzec	Czas
24 znaki	z odwołaniami	ok. 0,02 s
28 znaków	z odwołaniami	ok. 0,5 s
30 znaków	z odwołaniami	ok. 1,3 s
32 znaki	z odwołaniami	ok. 6,6 s
33 znaki	z odwołaniami	ok. 15,6 s
33 znaki	bez odwołań	ok. 0,005 s

Nasz pomiar w GNU grep 3.11 na jednej maszynie, wartości orientacyjne. Wzorzec z odwołaniami: ^(.*)\1{14}(.*)\2{13}$ z podręcznika. Bez odwołań: ^(.*)(.*)$.

Od około 30 znaków każdy kolejny znak mniej więcej podwaja czas. Ten sam tekst z wzorcem bez odwołań przechodzi w ułamku sekundy.

Na co uważać w wzorcach

Nie każdy wolny wzorzec ma odwołanie wsteczne. Podręcznik wymienia jeszcze kilka pułapek.

Konstrukcja	Ryzyko
odwołanie wsteczne `\1`	wolne, wykładnicze
bardzo duży licznik powtórzeń	pamięć i czas
zakres `[a-z]` poza ustawieniem `C`	bywa wolne

Według podręcznika GNU grep 3.12.

Duży licznik powtórzeń może wyczerpać pamięć albo bardzo spowolnić dopasowanie.1 Wyszukiwanie z zakresami typu [a-z] poza ustawieniem C bywa zaskakująco nieefektywne.1

Z praktyki

Nasza rada: odwołania wsteczne zostaw na przypadki, gdy naprawdę szukasz powtórzenia. Do zwykłego wyszukiwania wystarczą wzorce bez nich.

Częste błędy

Trzy przekonania najczęściej mylą przy ocenie wydajności wzorca.

Przekonanie	Rzeczywistość	Co zrobić
Każdy wzorzec jest szybki	odwołania mogą spowolnić grep	Ogranicz użycie `\1`
Czas rośnie liniowo z długością	przy backtrackingu rośnie wykładniczo	Mierz na długich liniach
Opis algorytmu to gwarancja	to szczegół implementacji	Nie opieraj się na nim

Kolumna „Co zrobić” to nasza rekomendacja, nie cytat z podręcznika.

Uwaga — pomiary są orientacyjne

Czasy z tabeli zależą od maszyny i wersji grep. Ważny jest kształt wzrostu, nie same sekundy.

Pytania sprawdzające

Dlaczego odwołanie wsteczne spowalnia grep?

Odwołania nie da się w ogólnym przypadku obsłużyć automatem skończonym, więc grep uruchamia algorytm z cofaniem, który może być bardzo niewydajny.

Co robi algorytm z cofaniem, gdy dalszy ciąg dopasowania nie pasuje?

Wraca do wcześniejszego wyboru i próbuje innej możliwości. W najgorszym razie sprawdza wszystkie dopasowania.

Co pokazuje tabela czasów?

Że dla wzorca z odwołaniami czas od około 30 znaków mniej więcej podwaja się przy każdym kolejnym znaku, a dla wzorca bez odwołań pozostaje znikomy.

Czy można zakładać, że grep zawsze dopasowuje tym samym algorytmem?

Nie. Podręcznik mówi, że algorytm to szczegół implementacji i może się zmienić między wydaniami.

Podsumowanie

Grep dopasowuje częściowo automatami, a częściowo wolniejszym dopasowywaczem.
Automat czyta tekst znak po znaku i zmienia stan.
Odwołanie wsteczne włącza algorytm z cofaniem (backtracking).
W najgorszym razie backtracking rośnie wykładniczo.
Duże liczniki powtórzeń też mogą spowolnić dopasowanie lub wyczerpać pamięć.
Algorytm grep to szczegół implementacji, który może się zmienić.

Źródła

GNU Grep 3.12 — GNU Projectsprawdzone 2026-11-03