From: Saynatkari <ruby-ml@...>
Date: 2005-04-03T22:36:54+09:00
Subject: Re: Iterating through a string and removing leading characters


Le 3/4/2005, "Mathieu Bouchard" <matju@sympatico.ca> a �crit:
>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.

This is a worthy idea, certainly! I should not expect it to cause
any confusion so long as the notation is standardised, particularly
through the standard ? extension switch. Perhaps the inner braces
would not be allowed for clarity? Unfortunately the rubyish ?!
(in-place method) and ?# (string interpolation) are already taken :)

/(?-> 'match' 'replacement')/

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

E

No-one expects the Solaris POSIX implementation!