Re: Matching very large patterns, was Re: Inverse grep

Chris F Clark <cfc@shell01.theworld.com> wrote:
> Our moderator asked:
>> How serious is the explosion problem in practice, now that compilers
>> no longer have to fit into 64k? We use lex scanners with a thousand
>> tokens, and spamassassin feeds about 2000 patterns to re2c if you use
>> the compiled patterns feature. None of them seem to strain our storage
>> systems. -John


> For compilers on mainline chips this is generally not a problem.
> However, this is such a useful tool, it gets used in areas where the
> problems are much-much larger (or the device is smaller). The
> Aho-Corasick algorithm is one of the key algorithms in matching a set
> of strings to a large set of incoming data. The two places where I've
> seen it used and where size is a problem is networking and
> computational biology.


The favorite for computational biology for many years was dynamic
programming, though often it is too slow. The dynamic programming
algorithm used for diff originated in the one Needleman-Wunsch used
for protein sequences. (I believe that it is referenced in the diff
documentation.)


More recently, the Burrows-Wheeler transform, commonly used in
compression, has become popular for computational biology.


BLAST is based on a DFA similar to the first part of Aho-Corasick, but
dynamic programming is used instead of the usual second part.


-- glen

Return to the comp.compilers page.
Search the comp.compilers archives again.