From: Mathieu Bouchard <matju@...>
Date: 2005-03-21T17:32:34+09:00
Subject: Re: Iterating through a string and removing leading characters


On Sat, 19 Mar 2005, Christian Neukirchen wrote:

> This reminds me of my old idea for matching against multiple regexp by
> automatically combining them into larger, alternating regexps thereby
> reducing the number of matches from n to log2(n)... Anyone willing to
> code that? To match t against A, B, C, D, E, F, G and H, you first
> match t against A|B|C|D|E|F|G|H, then against A|B|C|D, then against
> A|B (or E|F), then against A, C, E or G.  Would be of great use for
> strscan, too.

Wow, cool idea!

I can contribute a slight improvement to the idea. You make a Huffman tree
using the number of times that a regexp has been matched yet, or any
better prediction of how often it will come up in the future, and you
tweak the associativity of your disjunction correspondingly, such that it
matches the structure of the tree.

If, in the sequence of actual matches, there is a finite upper bound on
the number of positive-recurrent states (that is, matches that do occur a
non-zero percentage of times in practice), then the order of my algorithm
is O(1), am I right?

Anyhow, it will accelerate the parsing, especially for a very redundant
text in a complex syntax, e.g. parsing something that could be any Ruby
code but which just happens to be a huuuuge array literal of hex fixnums.

Btw, anyone knows other algorithms that use Huffman to compress the *time*
instead of the *space* ?

_____________________________________________________________________
Mathieu Bouchard -=- Montr�al QC Canada -=- http://artengine.ca/matju