Glad to see this patch hasn't been totally forgotten. Being able to use indexes for regular expressions would be really cool!
Back in January, I asked for some high-level description of how the algorithm works (http://archives.postgresql.org/message-id/4F187D5C.30701@enterprisedb.com). That's still sorely needed. Googling around, I found the slides for your presentation on this from PGConf.EU - it would be great to have the information from that presentation included in the patch.
New version of patch is attached. The changes are following:
1) A big comment with high-level description of what is going on.
