regexkompleksitet

Regexkompleksitet refererer til hvor mye beregningsressurser som kreves for å avgjøre om en strengmatcher et regulært uttrykk. Ofte måles kompleksiteten i forhold til lengden av inputstrengen (n) og lengden på mønsteret (m), og den avhenger av hvilken regex-motor som brukes. Begrepet dekker både kjøretid og minnebruk under matching, og hvordan tilstanden til kjøringen vokser med lengden på input og kompleksiteten i mønsteret.

Det finnes to hovedtyper regex-motorer: backtracking/NFA-baserte motorer og DFA-baserte motorer. Backtracking-motorer (som mange PCRE-varianter) kan i verste fall ha eksponent tidskompleksitet på grunn av tilbakeføring mellom alternativer og kvantifikatorer. DFA-baserte motorer gir ofte lineær kjøretid i lengden av input for et fast mønster, men å konvertere mønsteret til en full DFA kan være eksponentielt i mønsterlengden, og minnebruken kan bli betydelig under byggingen.

Visse konstruksjoner påvirker også kompleksiteten kraftig. Backreferences og avanserte lookarounds gjør regex til et ikke-regulært språk og kan medføre uforutsigbar eller betydelig høyere kjøretid, avhengig av input. Mange moderne motorer tilbyr tiltak som possessive quantifiers og atomiske grupper for å redusere unødvendig tilbakekobling og forbedre ytelsen.

Praktisk sett betyr regexkompleksitet at man bør være oppmerksom på potensielt langsom behandling ved dårlige mønstre og store input, spesielt ved backtracking-motorer. Anbefalte praksiser inkluderer å unngå nested quantifiers, bruke mer spesifikke mønstre, benytte possessive quantifiers eller atomiske grupper, og ved strenge ytelseskrav vurdere DFA-baserte verktøy eller tidsgrenser for kjøring.