Re: Google SoC Proposal Ideas

[Aleksey Cheusov <vle%gmx.net@localhost>]

 >> 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.