Re: Google SoC Proposal Ideas

[Karlan Mitchell <karlanmitchell%gmail.com@localhost>]

Relevant link http://wiki.freebsd.org/G%C3%A1borSoC2008

On Tue, Mar 24, 2009 at 10:46 AM, Aleksey Cheusov <vle%gmx.net@localhost> wrote:
>
>  >> Using the fact that diff(1) should not ALWAYS work 100% correctly (100%
>  >> correctness is when diff generates MINIMAL difference) you
>  >> can implement heuristic even with O(N1+N2) algorithm that can work much
>  >> faster in practice for huge files.
>
>> ...and such heuristics can easily fall apart rather badly.
> Then implement correct algorithm with O(N1*N2) complexity.
>
>> Look at the history of diff(1) in OpenBSD for the mentioned case.
> URL?
>
>  >> The same for grep. nfa2dfa has O(I^N) complexity where I is a number of
>  >> elements in input alphabet and N is a number of terminals in input nfa.
>  >> Matching is O(N) or O(N^2) depending on implementation (I'm not about
>  >> submatching).
>
>> Pure DFAs are known to be rather suboptimal for many critical cases due
>> to the space complexity.
> nfa vs. dfa is a well known problem for several decades.
>
>> Any implementation that is not O(n) for
>> backreference-free regular expression is broken.
> Strictly speaking backreferencing is not Regular Expressions at all.
> It is also not required for grep/egrep/sed/awk/POSIX ERE/BRE.
>
>> Look at the extensive research before correcting me, please.
> :-)
>
> --
> Best regards, Aleksey Cheusov.
>