Do any of your regexps break DFA compatibility? Doesn't look like it in your examples. You can use a Python wrapper around a C/C++ DFA implementation like re2, which is a drop in replacement for re
. re2
will also fall back to using re
if the regex is incompatible with the re2
syntax, so it will optimize all possible cases, and not fail on incompatible cases.
Note that re2
does support the (?P<name>regex)
capture syntax, but it doesn't support the (?P=<name>)
backref sytnax.
try:
import re2 as re
re.set_fallback_notification(re.FALLBACK_WARNING)
except ImportError:
# latest version was for Python 2.6
else:
import re
If you have regexps with backrefs, you can still use re2
with a few special considerations: you'll need to replace the backrefs in your regexps with .*?
, and you may find false matches which you can filter out with re
. In real world data, the false matches will probably be uncommon.
Here is an illustrative example:
import re
try:
import re2
re2.set_fallback_notification(re2.FALLBACK_WARNING)
except ImportError:
# latest version was for Python 2.6
REGEXES = [
'^New York(?P<grp1>\d+/\d+): (?P<grp2>.+)$',
'^Ohio (?P<grp1>\d+/\d+/\d+): (?P<grp2>.+)$',
'(?P<year>\d{4}-\d{1,2}-\d{1,2})$',
'^(?P<year>\d{1,2}/\d{1,2}/\d{2,4})$',
'^(?P<title>.+?)[- ]+E(?P<epi>\d+)$',
]
COMPILED_REGEXES = [re.compile(r, flags=re.I) for r in REGEXES]
# replace all backrefs with .*? for re2 compatibility
# is there other unsupported syntax in REGEXES?
COMPILED_REGEXES_DFA = [re2.compile(re2.sub(r'\\d|\\g\\d|\\g\<\d+\>|\\g\<\w+\>', '.*?', r), flags=re2.I) for r in REGEXES]
def find_match(string):
for regex, regex_dfa in zip(COMPILED_REGEXES, COMPILED_REGEXES_DFA):
match_dfa = regex_dfa.search(string)
if not match_dfa:
continue
match = regex.search(string)
# most likely branch comes first for better branch prediction
if match:
return match
If this isn't fast enough, you can employ a variety of techniques to feed the DFA hits to re
as they are processed, instead of storing them in a file or in memory and handing them off once they're all collected.
You can also combine all your regexps into one big DFA regexp of alternating groups (r1)|(r2)|(r3)| ... |(rN)
and iterate through your group matches on the resulting match object to try to match only the corresponding original regexps. The match result object will have the same state as with OP's original solution.
# rename group names in regexeps to avoid name collisions
REGEXES_PREFIXED = [re2.sub(r'\(\?P\<(\w+)\>', r'(P<re{}_\1>'.format(idx), r) for idx, r in enumerate(REGEXES)]
# wrap and fold regexps (?P<hit0>pattern)| ... |(?P<hitN>pattern)
REGEX_BIG = ''
for idx, r in enumerate(REGEXES_PREFIXED):
REGEX_BIG += '(?P<hit{}>{})|'.format(idx, r)
else:
REGEX_BIG = REGEX_BIG[0:-1]
regex_dfa_big = re2.compile(REGEX_BIG, flags = re2.I)
def find_match(string):
match_dfa = regex_dfa_big.search(string)
if match_dfa:
# only interested in hit# match groups
hits = [n for n, _ in match_dfa.groupdict().iteritems() if re2.match(r'hit\d+', n)]
# check for false positives
for idx in [int(h.replace('hit', '')) for h in hits]
match = COMPILED_REGEXES[idx].search(string)
if match:
return match
You can also look at pyre which is a better maintained wrapper for the same C++ library, but not a drop in replacement for re
. There's also a Python Wrapper for RuRe, which is the fastest regex engine I know of.
|
.re
scanner
function to handle each match separately. See youtube.com/watch?v=D1twn9kLmYg . The only problem is that you also use named groups--perhaps you could have a two-step approach, first match the overall patern, than break each match into the parts you want. Or have a separate mapping from groups to names.r'^New York(?P<grp1>\d+/\d+): (?P<grp2>.+)$'