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