6
$\begingroup$

Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy).

Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern (redundancy)?

Note:

Most lossless compression programs do two things in sequence: the first step generates a statistical model for the input data, and the second step uses this model to map input data to bit sequences in such a way that "probable" (e.g. frequently encountered) data will produce shorter output than "improbable" data.

Techniques take advantage of the specific characteristics of images such as the common phenomenon of contiguous 2-D areas of similar tones. Every pixel but the first is replaced by the difference to its left neighbor. This leads to small values having a much higher probability than large values. This is often also applied to sound files, and can compress files that contain mostly low frequencies and low volumes. For images, this step can be repeated by taking the difference to the top pixel, and then in videos, the difference to the pixel in the next frame can be taken.

A hierarchical version of this technique takes neighboring pairs of data points, stores their difference and sum, and on a higher level with lower resolution continues with the sums. This is called discrete wavelet transform.

$\endgroup$
  • 2
    $\begingroup$ How would you compress something without considering whether it contains redundant data? I don't understand what you mean. $\endgroup$ – adrianN Oct 25 '16 at 11:22
  • 1
    $\begingroup$ Which resources have you checked? Are you familiar with wavelet compression, one of the first things that should pop up on Google? $\endgroup$ – Raphael Oct 25 '16 at 12:56
  • 1
    $\begingroup$ @Jim Then the algorithm that just outputs its input is a lossless compression algorithm that fits your definition and doesn't consider redundancies in the input data. $\endgroup$ – adrianN Oct 25 '16 at 14:02
  • 2
    $\begingroup$ Wikipedia is not known for its accuracy. $\endgroup$ – Yuval Filmus Oct 25 '16 at 16:07
  • 2
    $\begingroup$ @Jim If you quote things from any source, you have to credit it! $\endgroup$ – Raphael Oct 25 '16 at 22:09
4
$\begingroup$

Modeling data compression as a combination of statistical modeling and encoding seems a bit obsolete these days. In many compression algorithms, the most important step is combinatorial modeling, which finds structure in the data and uses the structure to transform the data into something that can be compressed with statistical methods. For example:

  • Burrows-Wheeler transform permutes the characters based on the lexicographic ordering of the suffixes starting after them.
  • Algorithms in the Lempel-Ziv family describe the text in terms of exact and/or inexact repeats.
  • A graph can be described in terms of bicliques (subgraphs with an edge from every node in vertex set $A$ to every node in vertex set $B$).
  • A text can be represented by a context-free grammar.
  • A collection of similar strings can be described by the edit operations required to transform a reference string into each of the individual strings.
  • The collection can also be described by a finite automaton recognizing a more general language, plus the paths used to produce each of the strings.
  • A suffix array has self-repetitions, where each pointer in the source substring is incremented by 1 in the target substring.
  • A (multi)set of integers can be represented as a binary sequence.

In principle, one can describe these combinatorial models in statistical terms, but the statistical viewpoint may not be very useful. Furthermore, many practical algorithms skip the statistical modeling/encoding part completely or do them in a naive way, as decompression speed may be more important than maximal compression.

All of these methods take advantage of the redundancy in the data or make it more explicit for the subsequent compression steps. After all, data compression is basically just getting rid of the redundancy in the data.

$\endgroup$
3
$\begingroup$

An interesting lossless compression algorithm for JPEG images was open-sourced this summer by Dropbox. The algorithm is called "Lepton" and achieves compression by "predicting coefficients in JPEG blocks and feeding those predictions as context into an arithmetic coder." The differences between the predictions and the actual coefficients are stored and these differences consume less space than the coefficients themselves. The algorithm takes advantage of the fact that real image data is rarely random and that gradients are smooth across blocks of pixels on average.

$\endgroup$
  • 3
    $\begingroup$ Lossless compression of JPEGs -- one entry in the "ironic algorithms" file! $\endgroup$ – Raphael Oct 25 '16 at 22:10
1
$\begingroup$

The answer to the question: Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern (redundancy)?

Is: Yes

The probability of each symbol is used, the order of the symbol is not. Also know as an Order-0 Markov chain, are used to encode data to reduces the number of bits for frequently used symbols, and more bits for infrequently used symbols.

Some Forms of entropy encoding: Huffman coding, Arithmetic coding , and the Recent Asymmetric Numeral Systems.

No Patterns have to repeat in order to apply entropy compression.

In fact, given the same data in another file in any random order will produce a compressed file of exactly the same size (if only the entropy encoding is used). Each being able to be decoded back to their respective source.

Entropy encoding is often used as the last step of compression (IE: Hoffman / Arithmetic / aRNS )

I suggest doing an internet search:

Entropy encoding

Entropy shannon

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.