[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: Google SoC Proposal Ideas
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.
> >> 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.
Main Index |
Thread Index |