From: Ken Bloom <kbloom@...>
Date: 2006-11-13T04:30:08+09:00
Subject: Re: regular expression too big

On Sun, 12 Nov 2006 19:15:12 +0000, Ken Bloom wrote:

> On Sun, 12 Nov 2006 15:25:49 +0100, Peter Schrammel wrote:
> 
>> Hi,
>> 
>> got  problem with big regexes:
>> I have a regex of about 70000+ words concated with '|' that I'd like to
>> match as a regex. /bla|blub|foo|bar|.....(70000)/
>> 
>> But unfortunately ruby gives me a 'regular expression too big' if I'm
>> trying to build such a thing.
>> I had a look at the regex.c code and saw the limit of 1 << 16 bytes for
>> regexes. Is there a way around this (without going down to 2000 words) ?
>> 
>> Thanks for any hint
>> 
>> Peter
> 
> Maybe a trie would be useful?
> http://rubyforge.org/projects/trie/
> (or there's another trie at http://kzk9.net/software/miscprograms/ruby/)

On one more thing: to implement substring search using a trie, when
adding words to the trie, you should generate appropriate back links so
that you can implement =~ use the Knuth-Morris-Pratt algorithm for matching.

--Ken

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/