Greedy versus lazy

Perilaku backtracking pada kuantifier greedy dan cara mengendalikannya dengan kuantifier lazy.

Daftar isi

Kuantifier membuat pola menjadi fleksibel, tetapi fleksibilitas itu membawa perilaku yang mengejutkan. Topik ini membedah kuantifier greedy yang mengambil sebanyak mungkin, kuantifier lazy yang berhenti pada kecocokan terpendek, serta backtracking (mundur bertahap) yang menjadi penyebab keduanya. Bagian akhir mengulas pola bertingkat yang membuat mundur itu meledak secara eksponensial beserta alat untuk menahannya.

Kuantifier greedy: mengambil sebanyak mungkin#

Kuantifier greedy mengambil sebanyak mungkin karakter yang masih memungkinkan keseluruhan pola cocok. Pada pola <.*>, elemen .* memakan seluruh sisa string terlebih dahulu, lalu mundur sejauh yang diperlukan agar tanda > penutup ditemukan. Hasilnya adalah kecocokan terpanjang yang mungkin, bukan kecocokan pertama yang ditemui.

Kejutannya muncul pada teks berisi lebih dari satu tag. Kutipan HTML tebal dan miring membentang dari < pertama sampai > terakhir, sehingga satu kecocokan menelan kedua tag beserta teks di antaranya. Yang diharapkan adalah empat kecocokan pendek, satu untuk setiap tag.

python Contoh: kuantifier greedy pada dua tag HTML

import re

html = "<b>tebal</b> dan <i>miring</i>"

# kuantifier greedy: memakan sebanyak mungkin sebelum mundur
print(re.findall(r"<.*>", html))

# kelas karakter yang meniadakan > : batas kecocokan yang eksplisit
print(re.findall(r"<[^>]+>", html))

text Keluaran

['<b>tebal</b> dan <i>miring</i>']
['<b>', '</b>', '<i>', '</i>']

Keluaran baris pertama memperlihatkan satu kecocokan panjang, sedangkan baris kedua memberikan empat tag terpisah. Pola <[^>]+> pada baris kedua tidak bergantung pada arah mundur kuantifier, karena kelas [^>]+ melarang melewati tanda > sehingga setiap kecocokan berhenti tepat pada penutup tag. Kedua pendekatan sah dipakai, dan yang penting adalah memilih perilaku yang sesuai dengan data.

Cara kerja backtracking secara mekanis#

Backtracking adalah mekanisme mundur satu langkah yang dijalankan mesin regex ketika jalur yang sedang dicoba macet. Pada pencocokan <.*> terhadap tebal, mesin pertama-tama memakan seluruh sisa string dengan .* sampai mencapai akhir. Uji tanda > gagal karena tidak ada karakter lagi, sehingga mesin mengembalikan satu karakter, menguji > kembali, dan mengulangi siklus ini sampai > terakhir berhasil. Satu kecocokan yang tampak sekejap itu sesungguhnya melewati belasan percobaan mundur.

Mekanisme yang sama menjelaskan keanehan pada string berisi dua kutipan. Pola "(.*)" memulai kecocokan pada kutip pembuka pertama, lalu mundur hanya sampai kutip penutup yang terakhir, sehingga isi dua kutipan yang berbeda ikut menyatu dalam satu kecocokan. Versi lazy pada bagian berikutnya menghentikan mundur pada kutip penutup yang terdekat.

python Contoh: pola kutipan greedy pada dua kalimat

import re

baris = 'Ali mencatat "suhu 27" dan Budi mencatat "suhu 24".'

# greedy: kutip pembuka pertama sampai kutip penutup terakhir
print(re.findall(r'"(.*)"', baris))

# lazy: berhenti pada kutip penutup terdekat
print(re.findall(r'"(.*?)"', baris))

text Keluaran

['suhu 27" dan Budi mencatat "suhu 24']
['suhu 27', 'suhu 24']

Keluaran pertama menyatukan dua kutipan menjadi satu kecocokan panjang, sedangkan keluaran kedua memisahkannya menjadi dua kecocokan utuh. Selisih kedua pola hanya satu tanda tanya, tetapi semantiknya berubah sama sekali karena arah mundurnya berbeda.

Kuantifier lazy: berhenti pada kecocokan terpendek#

Kuantifier lazy mengambil sesedikit mungkin karakter dan meluas hanya bila sisa pola tidak berhasil cocok. Bentuknya sama dengan versi greedy yang ditambah tanda tanya, dan tabel berikut memasangkannya satu per satu.

Greedy	Lazy
`*`	`*?`
`+`	`+?`
`?`	`??`
`{m,n}`	`{m,n}?`

Pada pola <.*?>, elemen .*? berhenti segera setelah tanda > pertama berhasil dicocokkan, sehingga kecocokan berhenti pada penutup tag yang terdekat. Pola <\w+?> lebih khusus lagi karena +? pada kelas \w memperluas nama tag sesedikit mungkin sebelum tanda > dicocokkan. Aturan praktisnya, pakai lazy apabila tanda penutup terdekat adalah batas yang dimaksudkan, dan pakai kelas negasi seperti [^>]+ apabila batasnya didefinisikan oleh karakter yang dilarang.

python Contoh: kuantifier lazy pada dua tag HTML

import re

html = "<b>tebal</b> dan <i>miring</i>"

# kuantifier lazy: berhenti pada kecocokan terpendek yang mungkin
print(re.findall(r"<.*?>", html))

# lazy pada kuantifier lain, contohnya +?
print(re.findall(r"<\w+?>", html))

text Keluaran

['<b>', '</b>', '<i>', '</i>']
['<b>', '<i>']

Dengan .*?, keempat tag dikembalikan satu per satu sesuai urutannya pada teks. Pola <\w+?> hanya menemukan  dan  karena nama tag pada contoh ini satu huruf, sedangkan tag penutup tidak diminta oleh pola tersebut.

Demo interaktif greedy versus lazy#

Demo berikut dapat dicoba langsung. Tekan tombol preset greedy atau lazy, jalankan pencarian, lalu amati perubahan jumlah dan panjang kecocokan pada teks yang sama. Mesin regex pada JavaScript berjalan dengan mekanisme mundur yang sama dengan contoh Python di atas, sehingga keluaran keduanya dapat dibandingkan satu banding satu. Kotak daftar di bawah pratinjau juga menampilkan posisi setiap kecocokan, sehingga perbedaan lebar kecocokan terbaca angka demi angka.

Kode sumber demo

<!DOCTYPE html>
<html lang="id">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Demo greedy versus lazy</title>
<style>
  body { font-family: system-ui, sans-serif; margin: 14px; font-size: 14px; color: #1f2937; }
  label { display: block; margin: 8px 0 2px; font-weight: 600; }
  input[type="text"] { width: 100%; box-sizing: border-box; padding: 6px 8px; font-family: ui-monospace, Menlo, Consolas, monospace; }
  .tombol { margin-top: 8px; }
  button { padding: 6px 10px; margin: 0 6px 6px 0; cursor: pointer; }
  .pratinjau { margin-top: 10px; padding: 8px; background: #f9fafb; border: 1px solid #e5e7eb; font-family: ui-monospace, Menlo, Consolas, monospace; word-break: break-all; }
  mark { background: #fde68a; padding: 0 1px; }
  ol { margin: 8px 0 0; padding-left: 22px; }
  .peringatan { color: #b91c1c; }
</style>
</head>
<body>
  <label for="teks">Teks masukan</label>
  <input type="text" id="teks" value="<b>tebal</b> dan <i>miring</i>">
  <label for="pola">Pola regex</label>
  <input type="text" id="pola" value="<.*>">
  <div class="tombol">
    <button id="preset-greedy" type="button">Preset greedy: &lt;.*&gt;</button>
    <button id="preset-lazy" type="button">Preset lazy: &lt;.*?&gt;</button>
    <button id="cari" type="button">Cari kecocokan</button>
  </div>
  <div id="keluaran"></div>
  <script>
    function escapeHtml(s) {
      return s.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;");
    }

    function kumpulkan(teks, pola) {
      var regex = new RegExp(pola, "g");
      var hasil = [];
      var m;
      while ((m = regex.exec(teks)) !== null) {
        hasil.push(m);
        if (m.index === regex.lastIndex) regex.lastIndex += 1;
      }
      return hasil;
    }

    function render() {
      var teks = document.getElementById("teks").value;
      var pola = document.getElementById("pola").value;
      var keluaran = document.getElementById("keluaran");
      var kecocokan;
      try {
        kecocokan = kumpulkan(teks, pola);
      } catch (e) {
        keluaran.innerHTML = '<p class="peringatan">Pola tidak valid: ' + escapeHtml(e.message) + "</p>";
        return;
      }
      var pratinjau = "", akhir = 0, i;
      for (i = 0; i < kecocokan.length; i += 1) {
        pratinjau += escapeHtml(teks.slice(akhir, kecocokan[i].index)) + "<mark>" + escapeHtml(kecocokan[i][0]) + "</mark>";
        akhir = kecocokan[i].index + kecocokan[i][0].length;
      }
      pratinjau += escapeHtml(teks.slice(akhir));
      var daftar = "";
      for (i = 0; i < kecocokan.length; i += 1) {
        daftar += "<li>posisi " + kecocokan[i].index + ": " + escapeHtml(kecocokan[i][0]) + "</li>";
      }
      keluaran.innerHTML =
        '<div class="pratinjau">' + (pratinjau || "&nbsp;") + "</div>" +
        "<p>" + kecocokan.length + " kecocokan ditemukan</p>" +
        (daftar ? "<ol>" + daftar + "</ol>" : "");
    }

    document.getElementById("cari").addEventListener("click", render);
    document.getElementById("preset-greedy").addEventListener("click", function () {
      document.getElementById("pola").value = "<.*>";
      render();
    });
    document.getElementById("preset-lazy").addEventListener("click", function () {
      document.getElementById("pola").value = "<.*?>";
      render();
    });
    render();
  </script>
</body>
</html>

Pada pola greedy, seluruh kutipan menjadi satu kecocokan dan pratinjau menandainya sebagai satu blok. Pada pola lazy, penanda terpisah muncul pada setiap tag, sama seperti keluaran Python pada bagian sebelumnya. Mengganti teks masukan sendiri, misalnya menambah tag ketiga, memperjelas bahwa panjang kecocokan ditentukan oleh arah mundur kuantifier.

Ketika mundur meledak: backtracking katastropik#

Backtracking katastropik (catastrophic backtracking) terjadi ketika kuantifier bersarang memaksa mesin menguji jumlah jalur yang tumbuh eksponensial terhadap panjang masukan. Pola (a+)+ adalah contoh klasiknya, yaitu kuantifier luar mengulang grup, kuantifier dalam mengulang a di dalam grup, sehingga deretan empat huruf a dapat dipilah menjadi beberapa kombinasi a, aa, dan aaa yang berbeda. Pada masukan yang pada akhirnya cocok, kombinasi pertama biasanya berhasil dan mundurnya singkat. Bahaya sesungguhnya ada pada masukan yang gagal cocok, karena seluruh kombinasi harus diuji sampai tuntas sebelum kecocokan dinyatakan gagal.

Potongan berikut membandingkan pola bertingkat (a+)+ dengan pola pipih a+ yang setara untuk kasus ini. Keluaran keduanya identik pada masukan pendek, sehingga bahayanya tidak terlihat pada hasil, melainkan pada jumlah jalur yang diuji di belakang layar.

python Contoh: pola bertingkat versus pola pipih

import re

# pola bertingkat (a+)+ dan pola pipih a+ yang setara pada kasus ini
bertingkat = re.compile(r"^(a+)+b$")
pipih = re.compile(r"^a+b$")

for target in ("ab", "aab", "aaab", "aaaaab"):
    print(target, bertingkat.search(target) is not None, pipih.search(target) is not None)

# masukan yang gagal cocok memaksa seluruh kombinasi diuji habis-habisan
print(bertingkat.search("aaac"))

text Keluaran

ab True True
aab True True
aaab True True
aaaaab True True
None

python

# tidak-dijalankan: masukan gagal berisi 30 huruf a membuat pola bertingkat
# berjalan sekitar satu menit, jauh melebihi batas waktu eksekusi sandbox
import re
import time

pola = re.compile(r"^(a+)+b$")
mulai = time.perf_counter()
pola.search("a" * 30)
print(f"durasi: {time.perf_counter() - mulai:.2f} detik")

Python 3.11 menyediakan dua alat penahan mundur. Kuantifier posesif (possessive quantifier) seperti a++ menolak mengembalikan karakter yang sudah dimakannya, dan grup atomik (atomic group) (?>...) memberi perilaku yang sama untuk isi satu grup. Karena mundur dimatikan, percobaan yang macet berhenti cepat alih-alih menjelajahi semua kombinasi.

python Contoh: kuantifier posesif dan grup atomik

import re

# tanpa posesif: a+ mundur sehingga a berikutnya masih bisa dicocokkan
print(re.search(r"a+a", "aaa").group(0))

# kuantifier posesif a++ menolak mundur, sehingga kecocokan gagal
print(re.search(r"a++a", "aaa"))

# grup atomik memberi perilaku yang sama untuk satu kesatuan pola
print(re.search(r"(?>a+)a", "aaa"))

text Keluaran

aaa
None
None

Versi tanpa posesif menemukan aaa dengan mundur satu langkah, sedangkan dua pola terakhir langsung gagal karena karakter yang dimakan tidak akan dikembalikan. Penahan mundur memang mengubah hasil pada pola tertentu, sehingga alat ini dipasang dengan sengaja pada pola yang kerentanannya sudah diketahui, bukan dilekatkan pada semua kuantifier.

Kesalahan umum#

Menganggap . mencocokkan segalanya. Titik tidak mencocokkan baris baru kecuali pola dipasang bersama re.DOTALL. Penguraian teks banyak baris dengan <.*> akan berhenti pada baris pertama tanpa penanda tersebut, dan kecocokan yang hilang sulit dilacak. Tambahkan re.DOTALL, atau gunakan kelas negasi seperti [^>] yang memang mengizinkan baris baru.

Menguraikan HTML bersarang dengan kuantifier. HTML yang tag-nya saling menyusun bukan pola berulang yang datar, sehingga versi greedy maupun lazy sama-sama tidak memahami struktur dokumen. Penguraian yang benar memakai parser, misalnya modul html.parser bawaan Python, yang menangkap hierarki tag secara utuh. Regex tetap berguna untuk potongan kecil yang bentuknya datar.

Mengira lazy selalu lebih lambat. Kuantifier lazy tidak otomatis lebih mahal daripada greedy, karena keduanya berjalan di atas mekanisme mundur yang sama. Pada teks dengan banyak tanda penutup, versi lazy kadang berhenti lebih cepat karena jarang perlu mundur jauh. Pilih berdasarkan batas kecocokan yang dimaksudkan, bukan berdasarkan dugaan kecepatan.

Ringkasan#

Kuantifier greedy mengambil sebanyak mungkin lalu mundur seperlunya, sedangkan kuantifier lazy (*?, +?, ??, {m,n}?) berhenti pada kecocokan terpendek yang berhasil.
Backtracking adalah mekanisme mundur satu langkah yang menjelaskan perilaku keduanya sekaligus biaya pencocokan di belakang layar.
Kuantifier bersarang pada masukan yang gagal cocok memicu backtracking katastropik yang tumbuh eksponensial, dan kuantifier posesif atau grup atomik menahannya.
Kelas negasi seperti [^>]+ sering kali lebih tepat daripada kuantifier rakus karena batas kecocokannya dinyatakan secara eksplisit.

Referensi#

Regular expression operations — Python documentation — Dokumentasi resmi perilaku greedy, lazy, posesif, dan grup atomik pada modul re.
Speech and Language Processing, draf edisi ke-3 — Jurafsky & Martin, Stanford — Bab regular expression menguraikan kuantifier dan perilaku pencocokannya terhadap teks.