tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: Google SoC Proposal Ideas

Relevant link

On Tue, Mar 24, 2009 at 10:46 AM, Aleksey Cheusov <> 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.

Home | Main Index | Thread Index | Old Index