Re: Speeding up multiple regex matches
Talin <[EMAIL PROTECTED]> wrote: ... > 1) Combine all of the regular expressions into one massive regex, and > let the regex state machine do all the discriminating. The problem with > this is that it gives you no way to determine which regex was the > matching one. Place each regex into a parenthesized group, and check which groups have matched on the resulting matchobject: >>> x=re.compile('(aa)|(bb)') >>> mo=x.search('zaap!') >>> mo.groups() ('aa', None) There's a limit of 99 groups, so if you have unbounded number of regexes to start with you'll have to split them up 99-or-fewer at a time, but that shouldn't be impossibly hard. Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Speeding up multiple regex matches
OK that worked really well. In particular, the "lastindex" property of the match object can be used to tell exactly which group matched, without having to sequentially search the list of groups. In fact, I was able to use your idea to cobble together a poor man's lexer which I am calling "reflex" (Regular Expressions For Lexing). Here's an example of how it's used: # Define the states using an enumeration State = Enum( 'Default', 'Comment', 'String' ) # Create a scanner scanner = reflex.scanner( State.Default ) scanner.rule( "\s+" ) scanner.rule( "/\*", reflex.set_state( State.Comment ) ) scanner.rule( "[a-zA-Z_][\w_]*", KeywordOrIdent ) scanner.rule( "0x[\da-fA-F]+|\d+", token=TokenType.Integer ) scanner.rule( "(?:\d+\.\d*|\.\d+)(?:[eE]?[+-]?\d+)|\d+[eE]?[+-]?\d+", token=TokenType.Real ) # Multi-line comment state scanner.state( State.Comment ) scanner.rule( "\*/", reflex.set_state( State.Default ) ) scanner.rule( "(?:[^*]|\*(?!/))+" ) # Now, create an instance of the scanner token_stream = scanner( input_file_iter ) for token in token_stream: print token Internally, it creates an array of patterns and actions for each state. Then when you ask it to create a scanner instance, it combines all of the patterns into a large regular expression. Input lines are marched vs. this regex, and if a match succeeds, then the match object's 'lastindenx' property is used to look up the actions to perform in the array. -- http://mail.python.org/mailman/listinfo/python-list
Re: Speeding up multiple regex matches
"Talin" wrote: > I've run in to this problem a couple of times. Say I have a piece of > text that I want to test against a large number of regular expressions, > where a different action is taken based on which regex successfully > matched. The naive approach is to loop through each regex, and stop > when one succeeds. However, I am finding this to be too slow for my > application -- currently 30% of the run time is being taken up in the > regex matching. > > I thought of a couple of approaches, but I am not sure how to make them > work: > > 1) Combine all of the regular expressions into one massive regex, and > let the regex state machine do all the discriminating. The problem with > this is that it gives you no way to determine which regex was the > matching one. use a capturing group for each alternative, and use lastindex to quickly find the match: http://docs.python.org/lib/match-objects.html lastindex The integer index of the last matched capturing group, or None if no group was matched at all. also see: http://effbot.org/zone/xml-scanner.htm -- http://mail.python.org/mailman/listinfo/python-list