GNU bug report logs - #16966
[PATCH] grep: optimization with the superset of DFA

Previous Next

Package: grep;

Reported by: Norihiro Tanaka <noritnk <at> kcn.ne.jp>

Date: Sat, 8 Mar 2014 05:43:01 UTC

Severity: normal

Tags: patch

Done: Paul Eggert <eggert <at> cs.ucla.edu>

Bug is archived. No further changes may be made.

Full log

View this message in rfc822 format

From: Paolo Bonzini <bonzini <at> gnu.org>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 16966 <at> debbugs.gnu.org
Subject: bug#16966: [PATCH] grep: optimization with the superset of DFA
Date: Wed, 02 Apr 2014 09:09:05 +0200

Il 02/04/2014 00:21, Norihiro Tanaka ha scritto:
> 1 accccccccccccccccccccccccccccccccccccccc
> 2 cccccccccccccccccccccccccccccccccccccccc
> 3 cccccccccccccccccccccccccccccccccccccccc
> 4 cccccccccccccccccccccccccccccccccccccccc
> 5 accccccccccccccccccccccccccccccccccccccb
>
> Then all lines are matched fast.  However, because matches multiple
> lines, retry from the last line (line 5).  It's accepted by the
> superset.  However, It's rejected by normal DFA.
>
> On the other hands, It can be constituted just three DFA states.  It's
> too simple.
>
>              /\
>             /  \
>             \  /
>              \/
>   1:a ---> 2:CSET ---> 3:b

Does anything change if there are a few million c's?

Paolo
This bug report was last modified 11 years and 107 days ago.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.