How to avoid catastrophic backtracking with this specific pattern

user_10844028 0
Viewed 112

I run into a catastrophic backtracking problem with this big reg pattern my predecessor wrote. We basically just want to filter out salaries out of job descriptions.

This is the pattern:

(?:(?:(?:\bEURO|\bEuro|\beuro|\bEUR|\bEur|\beur|€)[[:punct:]]?\W*(?:(?<!\d)(?:(\d{1,3}(?:[,.\'\s])\d{3})|([12]?\d{3,5}))(?!\d)(?:[,.](?:\d\d|-|--))?))|(?:(?:(?<!\d)(?:(\d{1,3}(?:[,.\'\s])\d{3})|([12]?\d{3,5}))(?!\d)(?:[,.](?:\d\d|-|--))?)(?:\W*(?:\bEURO|\bEuro|\beuro|\bEUR|\bEur|\beur|€))))|(?:(?:(?:gehalt|lohn|entgelt|netto|brutto|überzahlung|kollektivvertrag|wage\W|salary)\w*\W+(?:[a-zA-Z[:punct:]]+\W+){0,6}(?:(?<!\d)(?:(\d{1,3}(?:[,.\'\s])\d{3})|([12]?\d{3,5}))(?!\d)(?:[,.](?:\d\d|-|--))?))|(?:(?:(?<!\d)(?:(\d{1,3}(?:[,.\'\s])\d{3})|([12]?\d{3,5}))(?!\d)(?:[,.](?:\d\d|-|--))?)(?:\w*\W+){0,6}\w*(?:gehalt|lohn|entgelt|netto|brutto|überzahlung|kollektivvertrag|wage\W|salary)))

It basically does what it is intended to do, but inside my Java application it causes a freeze on some Job strings. That must not happen.

I am almost certain that this can be done much easier and a hundred times better, I just don't have the time to learn regex on an advanced level. Maybe some pros have a quick, first glance idea how to prevent the catastrophic backtracking problem and help me out.

It should recognize the patterns like

Eur 40.000

<some random text>gehalt: 2000-3000

(both numeric values so I can further process for min/max determination)

2000 - 50.000 euro

etc.

Examples:

Input:

We offer a salary of 40.000 - 50.000.

Matches:

40.000 , 50.000

Input:

date: 12.10.2020 - We offer eur 3000 - 20.000.

Matches:

3000 , 20.000

Input:

Hello world ! Today is: 12.10.2020 - We offer a Gehalt of eur3000-20.000

Matches:

3000 , 20.000

The problem occurs with crazy strings like Crazy String that unfortunately can occur during a web crawl

backtracking regex
1 Answers

The [:punct:] expression matches punctuation that can be also matches by \W, so \W+(?:[a-zA-Z[:punct:]]+\W+){0,6} must be replaced with \W+(?:[a-zA-Z]+\W+){0,6}. The (?:\w*\W+){0,6} is also catastrophic backtracking prone, since \w* matches 0 or more word characters and as such the pattern is of the (A+)+ type. Replace with \w*(?:\W+\w+){0,6}\W+.

--|- must be shrunk to --? to use as few alternatives with the same first characters as possible.

A ton of redundant non-capturing groups, some redundant lookbehinds are removed.

The rest of changes are just enhancing

Use

(?:(?:\bEURO?|€)\W*(\d{1,3}[,.\'\s]\d{3}|[12]?\d{3,5})(?!\d)(?:[,.](?:\d\d|--?))?|(?<!\d)(\d{1,3}[,.\'\s]\d{3}|[12]?\d{3,5})(?!\d)(?:[,.](?:\d\d|--?))?\W*(?:\bEURO?|€))|(?:(?:gehalt|lohn|entgelt|netto|brutto|überzahlung|kollektivvertrag|wage\b|salary)\w*\W+(?:[a-zA-Z]+\W+){0,6}(\d{1,3}[,.\'\s]\d{3}|[12]?\d{3,5})(?!\d)(?:[,.](?:\d\d|--?))?|(?<!\d)(\d{1,3}[,.\'\s]\d{3}|[12]?\d{3,5})(?!\d)(?:[,.](?:\d\d|--?))?\w*(?:\W+\w+){0,6}\W+(?:gehalt|lohn|entgelt|netto|brutto|überzahlung|kollektivvertrag|wage\b|salary))

See proof

user_113298900
Related