GetWiki

{{short description|Data compression approach allowing perfect reconstruction of the original data}}{{Use mdy dates|date=August 2021}}Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy.WEB, Unit 4 Lab 4: Data Representation and Compression, Page 6,bjc.edc.org/bjc-r/cur/programming/4-internet/4-representation-compression/6-compression.html?topic=nyc_bjc/4-internet.topic&course=bjc4nyc.html&novideo&noassignment#:~:text=Lossless%20compression%20works%20by%20removing,an%20example%20of%20lossless%20compression., 2022-04-09, bjc.edc.org, By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates (and therefore reduced media sizes).By operation of the pigeonhole principle, no lossless compression algorithm can shrink the size of all possible data: Some data will get longer by at least one symbol or byte.Compression algorithms are usually effective for human- and machine-readable documents and cannot shrink the size of random data that contain no redundancy. Different algorithms exist that are designed either with a specific type of input data in mind or with specific assumptions about what kinds of redundancy the uncompressed data are likely to contain.Lossless data compression is used in many applications. For example, it is used in the ZIP file format and in the GNU tool gzip. It is also often used as a component within lossy data compression technologies (e.g. lossless mid/side joint stereo preprocessing by MP3 encoders and other lossy audio encoders).NEWS, Price, Andy, Lossless Streaming – the future of high res audio,audiomediainternational.com/lossless-streaming-back-to-the-future/, Audio Media International, 3 March 2022, Lossless compression is used in cases where it is important that the original and the decompressed data be identical, or where deviations from the original data would be unfavourable. Common examples are executable programs, text documents, and source code. Some image file formats, like PNG or GIF, use only lossless compression, while others like TIFF and MNG may use either lossless or lossy methods. Lossless audio formats are most often used for archiving or production purposes, while smaller lossy audio files are typically used on portable players and in other cases where storage space is limited or exact replication of the audio is unnecessary.

Techniques

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” (i.e. frequently encountered) data will produce shorter output than “improbable” data.The primary encoding algorithms used to produce bit sequences are Huffman coding (also used by the deflate algorithm) and arithmetic coding. Arithmetic coding achieves compression rates close to the best possible for a particular statistical model, which is given by the information entropy, whereas Huffman compression is simpler and faster but produces poor results for models that deal with symbol probabilities close to 1.There are two primary ways of constructing statistical models: in a static model, the data is analyzed and a model is constructed, then this model is stored with the compressed data. This approach is simple and modular, but has the disadvantage that the model itself can be expensive to store, and also that it forces using a single model for all data being compressed, and so performs poorly on files that contain heterogeneous data. Adaptive models dynamically update the model as the data is compressed. Both the encoder and decoder begin with a trivial model, yielding poor compression of initial data, but as they learn more about the data, performance improves. Most popular types of compression used in practice now use adaptive coders.Lossless compression methods may be categorized according to the type of data they are designed to compress. While, in principle, any general-purpose lossless compression algorithm (general-purpose meaning that they can accept any bitstring) can be used on any type of data, many are unable to achieve significant compression on data that are not of the form for which they were designed to compress. Many of the lossless compression techniques used for text also work reasonably well for indexed images.

Multimedia

These 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. JPEG2000 additionally uses data points from other pairs and multiplication factors to mix them into the difference. These factors must be integers, so that the result is an integer under all circumstances. So the values are increased, increasing file size, but hopefully the distribution of values is more peaked. {{Citation needed|date=December 2007}} The adaptive encoding uses the probabilities from the previous sample in sound encoding, from the left and upper pixel in image encoding, and additionally from the previous frame in video encoding. In the wavelet transformation, the probabilities are also passed through the hierarchy.

Historical legal issues

Many of these methods are implemented in open-source and proprietary tools, particularly LZW and its variants. Some algorithms are patented in the United States and other countries and their legal usage requires licensing by the patent holder. Because of patents on certain kinds of LZW compression, and in particular licensing practices by patent holder Unisys that many developers considered abusive, some open source proponents encouraged people to avoid using the Graphics Interchange Format (GIF) for compressing still image files in favor of Portable Network Graphics (PNG), which combines the LZ77-based deflate algorithm with a selection of domain-specific prediction filters. However, the patents on LZW expired on June 20, 2003.WEB,www.unisys.com/about__unisys/lzw, Unisys, LZW Patent Information, About Unisys, dead,www.unisys.com/about__unisys/lzw," title="web.archive.org/web/20090602212118www.unisys.com/about__unisys/lzw,">web.archive.org/web/20090602212118www.unisys.com/about__unisys/lzw, 2009-06-02, Many of the lossless compression techniques used for text also work reasonably well for indexed images, but there are other techniques that do not work for typical text that are useful for some images (particularly simple bitmaps), and other techniques that take advantage of the specific characteristics of images (such as the common phenomenon of contiguous 2-D areas of similar tones, and the fact that color images usually have a preponderance of a limited range of colors out of those representable in the color space).As mentioned previously, lossless sound compression is a somewhat specialized area. Lossless sound compression algorithms can take advantage of the repeating patterns shown by the wave-like nature of the {{nowrap|data{{px2}}{{mdash}}{{px2}}}}essentially using autoregressive models to predict the “next” value and encoding the (hopefully small) difference between the expected value and the actual data. If the difference between the predicted and the actual data (called the error) tends to be small, then certain difference values (like 0, +1, −1 etc. on sample values) become very frequent, which can be exploited by encoding them in few output bits.It is sometimes beneficial to compress only the differences between two versions of a file (or, in video compression, of successive images within a sequence). This is called delta encoding (from the Greek letter Δ, which in mathematics, denotes a difference), but the term is typically only used if both versions are meaningful outside compression and decompression. For example, while the process of compressing the error in the above-mentioned lossless audio compression scheme could be described as delta encoding from the approximated sound wave to the original sound wave, the approximated version of the sound wave is not meaningful in any other context.

Methods

{{See also|:Category:Lossless compression algorithms|List of lossless compression algorithms}}No lossless compression algorithm can efficiently compress all possible data {{xref|(see {{slink||Limitations}} for more on this)}}. For this reason, many different algorithms exist that are designed either with a specific type of input data in mind or with specific assumptions about what kinds of redundancy the uncompressed data are likely to contain.Some of the most common lossless compression algorithms are listed below.

General purpose

• ANS – Entropy encoding, used by LZFSE and Zstandard
• Arithmetic coding – Entropy encoding
• Burrows–Wheeler transform reversible transform for making textual data more compressible, used by bzip2
• Huffman coding – Entropy encoding, pairs well with other algorithms
• Lempel-Ziv compression (LZ77 and LZ78) – Dictionary-based algorithm that forms the basis for many other algorithms
  • Lempel–Ziv–Markov chain algorithm (LZMA) – Very high compression ratio, used by 7zip and xz
  • Lempel–Ziv–Storer–Szymanski (LZSS) – Used by WinRAR in tandem with Huffman coding
    • Deflate – Combines LZ77 compression with Huffman coding, used by ZIP, gzip, and PNG images
  • Lempel–Ziv–Welch (LZW) – Used by GIF images and Unix’s compress utility
• Prediction by partial matching (PPM) – Optimized for compressing plain text
• Run-length encoding (RLE) – Simple scheme that provides good compression of data containing many runs of the same value

Audio

• Adaptive Transform Acoustic Coding (ATRAC)
• Apple Lossless (ALAC – Apple Lossless Audio Codec)
• Audio Lossless Coding (also known as MPEG-4 ALS)
• Direct Stream Transfer (DST)
• Dolby TrueHD
• DTS-HD Master Audio
• Free Lossless Audio Codec (FLAC)
• Meridian Lossless Packing (MLP)
• Monkey’s Audio (Monkey’s Audio APE)
• MPEG-4 SLS (also known as HD-AAC)
• OptimFROG
• Original Sound Quality (OSQ)
• RealPlayer (RealAudio Lossless)
• Shorten (SHN)
• TTA (True Audio Lossless)
• WavPack (WavPack lossless)
• WMA Lossless (Windows Media Lossless)

Raster graphics

• AVIF – AV1 Image File Format
• FLIF – Free Lossless Image Format
• HEIF – High Efficiency Image File Format (lossless or lossy compression, using HEVC)
• ILBM – (lossless RLE compression of Amiga IFF images)
• JBIG2 – (lossless or lossy compression of B&W images)
• JPEG 2000 – (includes lossless compression method via Le Gall–Tabatabai 5/3WEB, Sullivan, Gary, General characteristics and design considerations for temporal subband video coding, Video Coding Experts Group, ITU-T, 8–12 December 2003,www.itu.int/wftp3/av-arch/video-site/0312_Wai/VCEG-U06.doc, 13 September 2019, JOURNAL, Unser, M., Blu, T., Mathematical properties of the JPEG2000 wavelet filters, IEEE Transactions on Image Processing, 2003, 12, 9, 1080–1090, 10.1109/TIP.2003.812329, 18237979, 2003ITIP...12.1080U, 2765169,pdfs.semanticscholar.org/6ed4/dece8b364416d9c390ba53df913bca7fb9a6.pdf,web.archive.org/web/20191013222932/https://pdfs.semanticscholar.org/6ed4/dece8b364416d9c390ba53df913bca7fb9a6.pdf, dead, 2019-10-13, BOOK, Bovik, Alan C., The Essential Guide to Video Processing, 2009, Academic Press, 9780080922508, 355,books.google.com/books?id=wXmSPPB_c_0C&pg=PA355, reversible integer wavelet transform)
• JPEG-LS – (lossless/near-lossless compression standard)
• JPEG XL – (lossless or lossy compression)
• JPEG XR – formerly WMPhoto and HD Photo, includes a lossless compression method
• LDCT – Lossless Discrete Cosine TransformJOURNAL, Ahmed, Nasir, N. Ahmed, Mandyam, Giridhar D., Magotra, Neeraj, Arturo A., Robert J., Edward J., Rodriguez, Safranek, Delp, DCT-based scheme for lossless image compression, Digital Video Compression: Algorithms and Technologies 1995, 17 April 1995, 2419, 474–478, 10.1117/12.206386, International Society for Optics and Photonics, 1995SPIE.2419..474M, 13894279, BOOK, Komatsu, K., Sezaki, Kaoru, Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP ‘98 (Cat. No.98CH36181), Reversible discrete cosine transform, 1998, 3, 1769–1772 vol.3, 10.1109/ICASSP.1998.681802, 0-7803-4428-6, 17045923,www.researchgate.net/publication/3747502,
• PCX – PiCture eXchange
• PDF – Portable Document Format (lossless or lossy compression)
• QOI – Quite OK Image Format
• PNG – Portable Network Graphics
• TGA – Truevision TGA
• TIFF – Tag Image File Format (lossless or lossy compression)
• WebP – (lossless or lossy compression of RGB and RGBA images)

3D Graphics

• OpenCTM – Lossless compression of 3D triangle meshes

Video

See list of lossless video codecs

Cryptography

Cryptosystems often compress data (the “plaintext“) before encryption for added security. When properly implemented, compression greatly increases the unicity distance by removing patterns that might facilitate cryptanalysis.BOOK, Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography,books.google.com/books?id=MhvcBQAAQBAJ&q=%22compression%22+%22unicity+distance%22, 16 October 1996, CRC Press, 978-1-4398-2191-6, However, many ordinary lossless compression algorithms produce headers, wrappers, tables, or other predictable output that might instead make cryptanalysis easier. Thus, cryptosystems must utilize compression algorithms whose output does not contain these predictable patterns.

Genetics and Genomics

Genetics compression algorithms (not to be confused with genetic algorithms) are the latest generation of lossless algorithms that compress data (typically sequences of nucleotides) using both conventional compression algorithms and specific algorithms adapted to genetic data. In 2012, a team of scientists from Johns Hopkins University published the first genetic compression algorithm that does not rely on external genetic databases for compression. HAPZIPPER was tailored for HapMap data and achieves over 20-fold compression (95% reduction in file size), providing 2- to 4-fold better compression much faster than leading general-purpose compression utilities.JOURNAL, Chanda, P., Elhaik, E., Bader, J.S., HapZipper: sharing HapMap populations just got easier, Nucleic Acids Res, 1–7, 2012, 22844100, 10.1093/nar/gks709, 40, 20, 3488212, Genomic sequence compression algorithms, also known as DNA sequence compressors, explore the fact that DNA sequences have characteristic properties, such as inverted repeats. The most successful compressors are XM and GeCo.BOOK, Pratas, D., Pinho, A. J., Ferreira, P. J. S. G., 2016, Efficient compression of genomic sequences, Data Compression Conference, Snowbird, Utah,sweet.ua.pt/pratas/papers/Pratas-2016b.pdf, For eukaryotes XM is slightly better in compression ratio, though for sequences larger than 100 MB its computational requirements are impractical.

Executables

Self-extracting executables contain a compressed application and a decompressor. When executed, the decompressor transparently decompresses and runs the original application. This is especially often used in demo coding, where competitions are held for demos with strict size limits, as small as 1k.This type of compression is not strictly limited to binary executables, but can also be applied to scripts, such as JavaScript.

Benchmarks

Lossless compression algorithms and their implementations are routinely tested in head-to-head benchmarks. There are a number of better-known compression benchmarks. Some benchmarks cover only the data compression ratio, so winners in these benchmarks may be unsuitable for everyday use due to the slow speed of the top performers. Another drawback of some benchmarks is that their data files are known, so some program writers may optimize their programs for best performance on a particular data set. The winners on these benchmarks often come from the class of context-mixing compression software.Matt Mahoney, in his February 2010 edition of the free booklet Data Compression Explained, additionally lists the following:WEB, Data Compression Explained, Matt Mahoney, 2010,nishi.dreamhosters.com/u/dce2010-02-26.pdf, 3–5,

• The Calgary Corpus dating back to 1987 is no longer widely used due to its small size. Matt Mahoney maintained the Calgary Compression Challenge, created and maintained from May 21, 1996, through May 21, 2016, by Leonid A. Broukhis.
• The Large Text Compression BenchmarkWEB,mattmahoney.net/dc/text.html, Large Text Compression Benchmark, mattmahoney.net, and the similar Hutter Prize both use a trimmed Pseudopedia XML UTF-8 data set.
• The Generic Compression Benchmark,WEB,mattmahoney.net/dc/uiq/, Generic Compression Benchmark, mattmahoney.net, maintained by Matt Mahoney, tests compression of data generated by random Turing machines.
• Sami Runsas (the author of NanoZip) maintained Compression Ratings, a benchmark similar to Maximum Compression multiple file test, but with minimum speed requirements. It offered the calculator that allowed the user to weight the importance of speed and compression ratio. The top programs were fairly different due to the speed requirement. In January 2010, the top program was NanoZip followed by FreeArc, CCM, flashzip, and 7-Zip.
• The Monster of Compression benchmark by Nania Francesco Antonio tested compression on 1Gb of public data with a 40-minute time limit. In December 2009, the top ranked archiver was NanoZip 0.07a and the top ranked single file compressor was ccmx 1.30c.

The Compression Ratings website published a chart summary of the “frontier” in compression ratio and time.WEB,compressionratings.com/rating_sum.html, Summary, September 1, 2016,compressionratings.com/rating_sum.html," title="web.archive.org/web/20160901094802compressionratings.com/rating_sum.html,">web.archive.org/web/20160901094802compressionratings.com/rating_sum.html, September 1, 2016, The Compression Analysis ToolWEB,www.noemax.com/free-tools/compression-analysis-tool.asp, Compression Analysis Tool, Noemax Technologies, Free Tools, is a Windows application that enables end users to benchmark the performance characteristics of streaming implementations of LZF4, Deflate, ZLIB, GZIP, BZIP2 and LZMA using their own data. It produces measurements and charts with which users can compare the compression speed, decompression speed and compression ratio of the different compression methods and to examine how the compression level, buffer size and flushing operations affect the results.

Limitations

Lossless data compression algorithms cannot guarantee compression for all input data sets. In other words, for any lossless data compression algorithm, there will be an input data set that does not get smaller when processed by the algorithm, and for any lossless data compression algorithm that makes at least one file smaller, there will be at least one file that it makes larger. This is easily proven with elementary mathematics using a counting argument called the pigeonhole principle, as follows:{{Sfn|Sayood|2002|p=41}}BOOK,books.google.com/books?id=exicCgAAQBAJ&pg=PA9, Tim Bell (computer scientist), Bell, Tim, Informatics in Schools. Curricula, Competences, and Competitions, 8th International Conference on Informatics in Schools: Situation, Evolution, and Perspectives, Lecture Notes in Computer Science, Springer Nature, Springer, September 28 – October 1, 2015, 9378, 2021-08-24, 8–9, 10.1007/978-3-319-25396-1, 978-3-319-25396-1, 26313283,

• Assume that each file is represented as a string of bits of some arbitrary length.
• Suppose that there is a compression algorithm that transforms every file into an output file that is no longer than the original file, and that at least one file will be compressed into an output file that is shorter than the original file.
• Let M be the least number such that there is a file F with length M bits that compresses to something shorter. Let N be the length (in bits) of the compressed version of F.
• Because N