From: brabuhr@...
Date: 2006-11-18T07:02:35+09:00
Subject: Re: regular expression too big

> In a little bit of testing here, it goes to long after about 8,000
> words.
>
> > require 'makeregex'
> >
> > 20.times do |n|
> >   words = IO.readlines("/usr/share/dict/words")[0..(2 ** n)]

Of course, that isn't the best sample of words to test with.

Here is a revised version (fails with a smaller word count):

> require 'makeregex'
>
> class Array
>   def sample n
>     a = []; s = self.size
>     n.times do
>       a << self[rand(s)].chomp
>     end
>     a
>   end
> end
>
> words = IO.readlines("/usr/share/dict/words")
>
> 20.times do |n|
>   w = words.sample(2 ** n)
>
>   start = Time.now
>
>   r = Regexp.make(w)
>
>   finish = Time.now
>
>   puts "Took #{finish - start} seconds to convert #{w.size} words into a regex #{r.size} bytes long."
>
>   "FOO".match(r)
> end

Took 9.9e-05 seconds to convert 1 words into a regex 9 bytes long.
Took 0.000163 seconds to convert 2 words into a regex 18 bytes long.
Took 0.000169 seconds to convert 4 words into a regex 42 bytes long.
Took 0.000299 seconds to convert 8 words into a regex 80 bytes long.
Took 0.000618 seconds to convert 16 words into a regex 176 bytes long.
Took 0.001366 seconds to convert 32 words into a regex 324 bytes long.
Took 0.003021 seconds to convert 64 words into a regex 689 bytes long.
Took 0.007129 seconds to convert 128 words into a regex 1391 bytes long.
Took 0.019143 seconds to convert 256 words into a regex 2740 bytes long.
Took 0.149488 seconds to convert 512 words into a regex 5295 bytes long.
Took 0.304324 seconds to convert 1024 words into a regex 10236 bytes long.
Took 0.307832 seconds to convert 2048 words into a regex 19755 bytes long.
Took 0.404071 seconds to convert 4096 words into a regex 37308 bytes long.
foo:26:in `match': regular expression too big:
/(?:A(?:ME|c(?:arapis|kley|mispon)|...