Re: Complexity of BWT, PPM, LZ77/LZ78


<digital.parasite@xxxxxxxxx> wrote in message
news:1140211217.727301.71790@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I'm trying to determine the complexity in Big-Oh notation of BWT, PPM,
and LZ77/LZ78. I realize that there are several implementation of
these algorithms, so I'm not sure the best way to go about choosing.

If you are trying to describe the complexity of a class of algorithms
in general, should one pick the current best in the class, or possibly
the most popular/used one? Or mention that the best implementation has
O(X) complexity with O(Y) is average, etc...?

Are there any papers that describe the O() of say bzip2's
implementation of BWT? Or the LZ77 implementation used in gzip since
those are two very popular compressors.

What is the state of the art for PPM these days and what are the most
popular compressors using PPM?

Thanks.


errm, I may be wrong, but I don't think compressors can really be compared
via O(...) concept.


for a sufficiently large file, the complexity of nearly any common algo will
end up being O(n).

there may be local variations, but these will generally even out.

now, algos will typically run faster or slower, but it is a linear scale,
and one typically does not say an algo is O(2.31776n) or O(0.25398n). so,
imo, comparisson of this sort is effectively useless.


.

Relevant Pages

  • Re: complexity of LP
    ... one must discern between the complexity in regards of step numbers ... An algorithm for solving linear programming problems in $O$ operations. ... On the worst case complexity of potential reduction algorithms for linear programming. ...
    (sci.math.num-analysis)
  • Re: Intro to Programming w/ Machine Language
    ... )> If n is sufficiently large, the Ocomplexity obviously matters. ... You only stated that big-oh complexity ... Not if the algorithms were carefully chosen in the first place. ... Or, much more prevalent, the choice of datatypes for search lists, ...
    (comp.programming)
  • Re: Intro to Programming w/ Machine Language
    ... )> If n is sufficiently large, the Ocomplexity obviously matters. ... You only stated that big-oh complexity ... Not if the algorithms were carefully chosen in the first place. ... Or, much more prevalent, the choice of datatypes for search lists, ...
    (alt.lang.asm)
  • Re: unprovability of the security of computational cryptography
    ... Public key algorithms are based on factoring ... We only know the complexity of the current algorithms. ... if you would want to build a block cipher whose security was ...
    (sci.crypt)
  • Re: Quantum Computation
    ... >Also, note that complexity is a property of *problems*, not algorithms, ... Your last remark assumes that machines are being treated as black ... >which Quantum Computing is better than classical, ...
    (sci.physics.research)