From: Christian Neukirchen Date: 2005-03-21T21:52:44+09:00 Subject: Re: Iterating through a string and removing leading characters Mathieu Bouchard writes: > 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. A kind of self-optimizing regular expression. Will rock if done properly. :-) > 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? > 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* ? I wonder if maybe a PATRICIA (crit-bit) tree could help too, but then, Ruby regexp cannot match on bit-level. > Mathieu Bouchard -=- Montr�al QC Canada -=- http://artengine.ca/matju -- Christian Neukirchen http://chneukirchen.org