[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: Google SoC Proposal Ideas
>> My own idea is to reimplement a GNU/GPL utility under a BSD license,
>> like grep or diff/diff3.
> Both grep and diff can be a bit ambigious in terms of algorithm
What exactly is ambigious in diff's complexity?
Its complexity is O(N1*N2) where N1 and N2 are a number of lines
in two files. I don't know how GNU and OpenBSD diffs are implemented,
but diff is one of the well know example for "dynamic programming".
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.
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
> grep for example is demanding if you want to implement
> multibyte support correctly and full GNU grep compatibility needs
> changes to the system regex library.
agc@ said it has utf-8 aware regexp engine.
> diff has some critical edge cases like a number of small changes for
> large files (think configure).
Best regards, Aleksey Cheusov.
Main Index |
Thread Index |