Regular Expressions: large amount of or's

[André Søreng]

Hi!

Given a string, I want to find all ocurrences of
certain predefined words in that string. Problem is, the list of
words that should be detected can be in the order of thousands.

With the re module, this can be solved something like this:

import re

r = re.compile("wor d1|word2|word3| .......|wordN")
r.findall(some_ string)

Unfortunately, when having more than about 10 000 words in
the regexp, I get a regular expression runtime error when
trying to execute the findall function (compile works fine, but slow).

I don't know if using the re module is the right solution here, any
suggestions on alternative solutions or data structures which could
be used to solve the problem?

André

[Tim Peters]

Re: Regular Expressions: large amount of or's

[André Søreng][color=blue]
> Given a string, I want to find all ocurrences of
> certain predefined words in that string. Problem is, the list of
> words that should be detected can be in the order of thousands.
>
> With the re module, this can be solved something like this:
>
> import re
>
> r = re.compile("wor d1|word2|word3| .......|wordN")
> r.findall(some_ string)
>
> Unfortunately, when having more than about 10 000 words in
> the regexp, I get a regular expression runtime error when
> trying to execute the findall function (compile works fine, but slow).
>
> I don't know if using the re module is the right solution here, any
> suggestions on alternative solutions or data structures which could
> be used to solve the problem?[/color]

Put the words you're looking for into a set (or as the keys of a dict
in older Pythons; the values in the dict are irrelevant).

I don't know what you mean by "word", so write something that breaks
your string into what you mean by words. Then:

for word in something_that_ produces_words( the_string):
if word in set_of_words:
# found one

This takes expected-case time proportional to the number of words in
the string, + setup time proportional to the number of "interestin g"
words (the time needed to create a set or dict from them). 10,000
interesting words won't even start to strain it.

[Kent Johnson]

Re: Regular Expressions: large amount of or's

André Søreng wrote:[color=blue]
>
> Hi!
>
> Given a string, I want to find all ocurrences of
> certain predefined words in that string. Problem is, the list of
> words that should be detected can be in the order of thousands.
>
> With the re module, this can be solved something like this:
>
> import re
>
> r = re.compile("wor d1|word2|word3| .......|wordN")
> r.findall(some_ string)
>
> Unfortunately, when having more than about 10 000 words in
> the regexp, I get a regular expression runtime error when
> trying to execute the findall function (compile works fine, but slow).
>
> I don't know if using the re module is the right solution here, any
> suggestions on alternative solutions or data structures which could
> be used to solve the problem?[/color]

If you can split some_string into individual words, you could look them up in a set of known words:

known_words = set("word1 word2 word3 ....... wordN".split())
found_words = [ word for word in some_string.spl it() if word in known_words ]

Kent
[color=blue]
>
> André
>[/color]

[James Stroud]

Re: Regular Expressions: large amount of or's

This does not sound like a job for a single regex.

Using a list and listcomp (say your words are in a list called "mywordlist ")
you can make this quite terse. Of course I have a way of writing algorithms
that have very large exp when people tell me the O(N^exp).

try this:


myregexlist = [re.compile(awor d) for aword in mywordlist]
myoccurrences = [argx.findall(so me_string) for argx in myregexlist]


Now you should have a 1:1 mapping of the mywordlist and myoccurrences. Of
course you can fill mywordlist with real regular expressions instead of just
words. If you want to count the words, you may just want to use the string
count method:


myoccurrences = [some_string.cou nt(aword) for aword in mywordlist]


This may make more sense if you are not using true regexes.

James

On Tuesday 01 March 2005 11:46 am, André Søreng wrote:[color=blue]
> Hi!
>
> Given a string, I want to find all ocurrences of
> certain predefined words in that string. Problem is, the list of
> words that should be detected can be in the order of thousands.
>
> With the re module, this can be solved something like this:
>
> import re
>
> r = re.compile("wor d1|word2|word3| .......|wordN")
> r.findall(some_ string)
>
> Unfortunately, when having more than about 10 000 words in
> the regexp, I get a regular expression runtime error when
> trying to execute the findall function (compile works fine, but slow).
>
> I don't know if using the re module is the right solution here, any
> suggestions on alternative solutions or data structures which could
> be used to solve the problem?
>
> André[/color]

--
James Stroud, Ph.D.
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

[André Søreng]

Re: Regular Expressions: large amount of or's

Kent Johnson wrote:[color=blue]
> André Søreng wrote:
>[color=green]
>>
>> Hi!
>>
>> Given a string, I want to find all ocurrences of
>> certain predefined words in that string. Problem is, the list of
>> words that should be detected can be in the order of thousands.
>>
>> With the re module, this can be solved something like this:
>>
>> import re
>>
>> r = re.compile("wor d1|word2|word3| .......|wordN")
>> r.findall(some_ string)
>>
>> Unfortunately, when having more than about 10 000 words in
>> the regexp, I get a regular expression runtime error when
>> trying to execute the findall function (compile works fine, but slow).
>>
>> I don't know if using the re module is the right solution here, any
>> suggestions on alternative solutions or data structures which could
>> be used to solve the problem?[/color]
>
>
> If you can split some_string into individual words, you could look them
> up in a set of known words:
>
> known_words = set("word1 word2 word3 ....... wordN".split())
> found_words = [ word for word in some_string.spl it() if word in
> known_words ]
>
> Kent
>[color=green]
>>
>> André
>>[/color][/color]

That is not exactly what I want. It should discover if some of
the predefined words appear as substrings, not only as equal
words. For instance, after matching "word2sgjoisejf isaword1yguyg", word2
and word1 should be detected.

[Francis Girard]

Re: Regular Expressions: large amount of or's

Le mardi 1 Mars 2005 22:04, André Søreng a écrit :[color=blue]
> That is not exactly what I want. It should discover if some of
> the predefined words appear as substrings, not only as equal
> words. For instance, after matching "word2sgjoisejf isaword1yguyg", word2
> and word1 should be detected.[/color]

Hi,

A lexer producing a DFA like the one in pyggy (see
http://www.lava.net/~newsham/pyggy/) might be what you're looking for.

Regards,

Francis Girard

[Bill Mill]

Re: Regular Expressions: large amount of or's

On Tue, 01 Mar 2005 22:04:15 +0100, André Søreng <wsoereng@tisca li.no> wrote:[color=blue]
> Kent Johnson wrote:[color=green]
> > André Søreng wrote:
> >[color=darkred]
> >>
> >> Hi!
> >>
> >> Given a string, I want to find all ocurrences of
> >> certain predefined words in that string. Problem is, the list of
> >> words that should be detected can be in the order of thousands.
> >>
> >> With the re module, this can be solved something like this:
> >>
> >> import re
> >>
> >> r = re.compile("wor d1|word2|word3| .......|wordN")
> >> r.findall(some_ string)
> >>
> >> Unfortunately, when having more than about 10 000 words in
> >> the regexp, I get a regular expression runtime error when
> >> trying to execute the findall function (compile works fine, but slow).
> >>
> >> I don't know if using the re module is the right solution here, any
> >> suggestions on alternative solutions or data structures which could
> >> be used to solve the problem?[/color]
> >
> >
> > If you can split some_string into individual words, you could look them
> > up in a set of known words:
> >
> > known_words = set("word1 word2 word3 ....... wordN".split())
> > found_words = [ word for word in some_string.spl it() if word in
> > known_words ]
> >
> > Kent
> >[color=darkred]
> >>
> >> André
> >>[/color][/color]
>
> That is not exactly what I want. It should discover if some of
> the predefined words appear as substrings, not only as equal
> words. For instance, after matching "word2sgjoisejf isaword1yguyg", word2
> and word1 should be detected.[/color]

Show some initiative, man!
[color=blue][color=green][color=darkred]
>>> known_words = set(["word1", "word2"])
>>> found_words = [word for word in known_words if word in "word2sgjoisejf isawo[/color][/color][/color]
rd1yguyg"][color=blue][color=green][color=darkred]
>>> found_words[/color][/color][/color]
['word1', 'word2']

Peace
Bill Mill
bill.mill at gmail.com

[Kent Johnson]

Re: Regular Expressions: large amount of or's

André Søreng wrote:[color=blue]
>
> Hi!
>
> Given a string, I want to find all ocurrences of
> certain predefined words in that string. Problem is, the list of
> words that should be detected can be in the order of thousands.
>
> With the re module, this can be solved something like this:
>
> import re
>
> r = re.compile("wor d1|word2|word3| .......|wordN")
> r.findall(some_ string)
>
> Unfortunately, when having more than about 10 000 words in
> the regexp, I get a regular expression runtime error when
> trying to execute the findall function (compile works fine, but slow).[/color]

What error do you get? What version of Python are you using? re was changed in Python 2.4 to avoid
recursion, so if you are getting a stack overflow in Python 2.3 you should try 2.4.

Kent

[Nick Craig-Wood]

Re: Regular Expressions: large amount of or's

André Søreng <wsoereng@tisca li.no> wrote:[color=blue]
> Given a string, I want to find all ocurrences of
> certain predefined words in that string. Problem is, the list of
> words that should be detected can be in the order of thousands.
>
> With the re module, this can be solved something like this:
>
> import re
>
> r = re.compile("wor d1|word2|word3| .......|wordN")
> r.findall(some_ string)
>
> Unfortunately, when having more than about 10 000 words in
> the regexp, I get a regular expression runtime error when
> trying to execute the findall function (compile works fine, but
> slow).[/color]

I wrote a regexp optimiser for exactly this case.

Eg a regexp for all 5 letter words starting with re

$ grep -c '^re' /usr/share/dict/words
2727

$ grep '^re' /usr/share/dict/words | ./words-to-regexp.pl 5

re|re's|reac[ht]|rea(?:d|d[sy]|l|lm|m|ms|p|ps |r|r[ms])|reb(?:el|u[st])|rec(?:ap|ta|u r)|red|red's|re d(?:id|o|s)|ree (?:d|ds|dy|f|fs |k|ks|l|ls|ve)| ref|ref's|refe[dr]|ref(?:it|s)|re (?:gal|hab|(?:i g|i)n|ins|lax|l ay|lic|ly|mit|n al|nd|nds|new|n t|nts|p)|rep's| rep(?:ay|el|ly| s)|rer(?:an|un) |res(?:et|in|t| ts)|ret(?:ch|ry )|re(?:use|v)|r ev's|rev(?:el|s |ue)

As you can see its not perfect.

Find it in http://www.craig-wood.com/nick/pub/words-to-regexp.pl

Yes its perl and rather cludgy but may give you ideas!

--
Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick

[Daniel Yoo]

Re: Regular Expressions: large amount of or's

Kent Johnson <kent37@tds.net > wrote:

:> Given a string, I want to find all ocurrences of
:> certain predefined words in that string. Problem is, the list of
:> words that should be detected can be in the order of thousands.
:>
:> With the re module, this can be solved something like this:
:>
:> import re
:>
:> r = re.compile("wor d1|word2|word3| .......|wordN")
:> r.findall(some_ string)

The internal data structure that encodes that set of keywords is
probably humongous. An alternative approach to this problem is to
tokenize your string into words, and then check to see if each word is
in a defined list of "keywords". This works if your keywords are
single words:

###
keywords = set([word1, word2, ...])
matchingWords = set(re.findall( r'\w+')).inters ection(keywords )
###

Would this approach work for you?



Otherwise, you may want to look at a specialized data structure for
doing mutiple keyword matching; I had an older module that wrapped
around a suffix tree:

http://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/

It looks like other folks, thankfully, have written other
implementations of suffix trees:

http://cs.haifa.ac.il/~shlomo/suffix_tree/

Another approach is something called the Aho-Corasick algorithm:

http://portal.acm.org/citation.cfm?doid=360825.360855

though I haven't been able to find a nice Python module for this yet.


Best of wishes to you!

[André Søreng]

Re: Regular Expressions: large amount of or's

Bill Mill wrote:[color=blue]
> On Tue, 01 Mar 2005 22:04:15 +0100, André Søreng <wsoereng@tisca li.no> wrote:
>[color=green]
>>Kent Johnson wrote:
>>[color=darkred]
>>>André Søreng wrote:
>>>
>>>
>>>>Hi!
>>>>
>>>>Given a string, I want to find all ocurrences of
>>>>certain predefined words in that string. Problem is, the list of
>>>>words that should be detected can be in the order of thousands.
>>>>
>>>>With the re module, this can be solved something like this:
>>>>
>>>>import re
>>>>
>>>>r = re.compile("wor d1|word2|word3| .......|wordN")
>>>>r.findall(s ome_string)
>>>>
>>>>Unfortunate ly, when having more than about 10 000 words in
>>>>the regexp, I get a regular expression runtime error when
>>>>trying to execute the findall function (compile works fine, but slow).
>>>>
>>>>I don't know if using the re module is the right solution here, any
>>>>suggestio ns on alternative solutions or data structures which could
>>>>be used to solve the problem?
>>>
>>>
>>>If you can split some_string into individual words, you could look them
>>>up in a set of known words:
>>>
>>>known_word s = set("word1 word2 word3 ....... wordN".split())
>>>found_word s = [ word for word in some_string.spl it() if word in
>>>known_word s ]
>>>
>>>Kent
>>>
>>>
>>>>André
>>>>[/color]
>>
>>That is not exactly what I want. It should discover if some of
>>the predefined words appear as substrings, not only as equal
>>words. For instance, after matching "word2sgjoisejf isaword1yguyg", word2
>>and word1 should be detected.[/color]
>
>
> Show some initiative, man!
>
>[color=green][color=darkred]
>>>>known_wor ds = set(["word1", "word2"])
>>>>found_wor ds = [word for word in known_words if word in "word2sgjoisejf isawo[/color][/color]
>
> rd1yguyg"]
>[color=green][color=darkred]
>>>>found_wor ds[/color][/color]
>
> ['word1', 'word2']
>
> Peace
> Bill Mill
> bill.mill at gmail.com[/color]

Yes, but I was looking for a solution which would scale. Searching
through the same string 10000+++ times does not seem like a suitable
solution.

André

[André Søreng]

Re: Regular Expressions: large amount of or's

Daniel Yoo wrote:[color=blue]
> Kent Johnson <kent37@tds.net > wrote:
>
> :> Given a string, I want to find all ocurrences of
> :> certain predefined words in that string. Problem is, the list of
> :> words that should be detected can be in the order of thousands.
> :>
> :> With the re module, this can be solved something like this:
> :>
> :> import re
> :>
> :> r = re.compile("wor d1|word2|word3| .......|wordN")
> :> r.findall(some_ string)
>
> The internal data structure that encodes that set of keywords is
> probably humongous. An alternative approach to this problem is to
> tokenize your string into words, and then check to see if each word is
> in a defined list of "keywords". This works if your keywords are
> single words:
>
> ###
> keywords = set([word1, word2, ...])
> matchingWords = set(re.findall( r'\w+')).inters ection(keywords )
> ###
>
> Would this approach work for you?
>
>
>
> Otherwise, you may want to look at a specialized data structure for
> doing mutiple keyword matching; I had an older module that wrapped
> around a suffix tree:
>
> http://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/
>
> It looks like other folks, thankfully, have written other
> implementations of suffix trees:
>
> http://cs.haifa.ac.il/~shlomo/suffix_tree/
>
> Another approach is something called the Aho-Corasick algorithm:
>
> http://portal.acm.org/citation.cfm?doid=360825.360855
>
> though I haven't been able to find a nice Python module for this yet.
>
>
> Best of wishes to you![/color]

Thanks, seems like the Aho-Corasick algorithm is along the lines of
what I was looking for, but have not read the article completely yet.

Also:

http://alexandria.tue.nl/extra1/wskrap/publichtml/200407.pdf

provided several alternative algorithms.

André

[Ola Natvig]

Re: Regular Expressions: large amount of or's

André Søreng wrote:[color=blue]
>
>
> Yes, but I was looking for a solution which would scale. Searching
> through the same string 10000+++ times does not seem like a suitable
> solution.
>
> André[/color]

Just for curiosity, what would a regexp do? Perhaps it's a clue in how
you could do this in the way regexp's are executed.

ola

--
--------------------------------------
Ola Natvig <ola.natvig@inf osense.no>
infoSense AS / development

[André Søreng]

Re: Regular Expressions: large amount of or's

Ola Natvig wrote:[color=blue]
> André Søreng wrote:
>[color=green]
>>
>>
>> Yes, but I was looking for a solution which would scale. Searching
>> through the same string 10000+++ times does not seem like a suitable
>> solution.
>>
>> André[/color]
>
>
> Just for curiosity, what would a regexp do? Perhaps it's a clue in how
> you could do this in the way regexp's are executed.
>
> ola
>[/color]

I think this article provides me with what I was looking for:

http://alexandria.tue.nl/extra1/wskrap/publichtml/200407.pdf

Enough info there to keep me going for some while.

[Gurpreet Sachdeva]

Re: Regular Expressions: large amount of or's

Can divide the regex on the bases of alphabets they are starting with
or can iterate on the list.

Regards,
Garry

http://garrythegambler.blogspot.com/

On Wed, 02 Mar 2005 12:50:01 +0100, André Søreng <andreis@stud.c s.uit.no> wrote:[color=blue]
> Ola Natvig wrote:[color=green]
> > André Søreng wrote:
> >[color=darkred]
> >>
> >>
> >> Yes, but I was looking for a solution which would scale. Searching
> >> through the same string 10000+++ times does not seem like a suitable
> >> solution.
> >>
> >> André[/color]
> >
> >
> > Just for curiosity, what would a regexp do? Perhaps it's a clue in how
> > you could do this in the way regexp's are executed.
> >
> > ola
> >[/color]
>
> I think this article provides me with what I was looking for:
>
> http://alexandria.tue.nl/extra1/wskr...tml/200407.pdf
>
> Enough info there to keep me going for some while.
> --
> http://mail.python.org/mailman/listinfo/python-list
> [/color]


--
Thanks and Regards,
GSS