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


On Mon, 21 Mar 2005, Christian Neukirchen wrote:
> Mathieu Bouchard <matju@sympatico.ca> writes:
> > 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?
> But for a possibly large constant runtime, no?

Depends on how seldom the Huffman tree is updated. I see it like this: you
update the frequency counts at every iteration (every use of the
regexp). This is essentially a kind of profiler. Then later on you
reparent Huffman subtrees all in one shot. Suppose that this reparenting
task is O(n)-time. Then to get an amortised O(1)-time you will need to
perform it O(1/n)-often, because O(n)*O(1/n)=O(1). Then the constants of
the O(1/n) can be lowered to inversely match the constants of the O(n) so
that the constants of the O(1) are kept as low as desired.

> > Btw, anyone knows other algorithms that use Huffman to compress the *time*
> > instead of the *space* ?
> I wonder if maybe a PATRICIA (crit-bit) tree could help too, but then,
> Ruby regexp cannot match on bit-level.

I don't really know that one.

However if I were to solve the problem of finding which sub-regexp has
been matched in (A|B|C|...), I'd edit re.c and add a (?)-feature for
filling a $-slot with a value that doesn't come from the string, e.g.

/((?"Aah"(A))|(?"Bay"(B))|(?"Say"(C))|(?"Day"(D)))/

Would put one of "Aah", "Bay", "Say", "Day" strings in $2...

But this doesn't make sense yet, as one would expect it to instead be put
in one of $2, $4, $6, $8, ... to be consistent with current regexp
semantics; and looking up possibly all of those looking for a nonnil
$-slot is a O(n)-time thing. There ought to be a better way, that is,
something both fast and consistent with current semantics, but I can't
think of any as of now. Do you have any ideas? If you have something good
then I think it should be a RCR.

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