Editing Lossless compression (section)

== 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===
* [[Asymmetric numeral systems|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
* [[LZ77 and LZ78|Lempel-Ziv compression]] (LZ77 and LZ78) – Dictionary-based algorithm that forms the basis for many other algorithms
** [[Deflate]] – Combines LZ77 compression with Huffman coding, used by [[ZIP (file format)|ZIP]], [[gzip]], and [[Portable Network Graphics|PNG]] images
** [[Lempel–Ziv–Markov chain algorithm]] (LZMA) – Very high compression ratio, used by [[7zip]] and [[XZ Utils|xz]]
** [[Lempel–Ziv–Storer–Szymanski]] (LZSS) – Used by [[WinRAR]] in tandem with Huffman coding
** [[Lempel–Ziv–Welch]] (LZW) – Used by [[GIF]] images and Unix's <code>[[compress]]</code> 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)
* [[Super Audio CD#DST|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 (file format)|Shorten]] (SHN)
* TTA (True Audio Lossless)
* [[WavPack]] (WavPack lossless)
* [[Windows Media Audio 9 Lossless|WMA Lossless]] (Windows Media Lossless)

=== Raster graphics ===

* Lossless only encoding
** [[BMP_file_format|BMP]]
** [[Portable Network Graphics|PNG]] – Portable Network Graphics
** [[GIF]] – Graphics Interchange Format
* Lossy and Lossless encoding options
** [[AV1#AV1 Image File Format (AVIF)|AVIF]] – AV1 Image File Format
** [[FLIF]] – Free Lossless Image Format
** [[High Efficiency Image File Format|HEIF]] – High Efficiency Image File Format, using [[High Efficiency Video Coding|HEVC]]
** [[ILBM]] – (RLE compression of [[Amiga]] [[Interchange File Format|IFF]] images)
** [[JBIG2]] – compression of B&W images
** [[JPEG 2000]] – (via Le Gall–Tabatabai 5/3<ref>{{cite web |last1=Sullivan |first1=Gary |title=General characteristics and design considerations for temporal subband video coding |publisher=[[Video Coding Experts Group]] |website=[[ITU-T]] |date=8–12 December 2003 |url=https://www.itu.int/wftp3/av-arch/video-site/0312_Wai/VCEG-U06.doc |access-date=13 September 2019}}</ref><ref name="Unser">{{cite journal |last1=Unser |first1=M. |last2=Blu |first2=T. |title=Mathematical properties of the JPEG2000 wavelet filters |journal=IEEE Transactions on Image Processing |date=2003 |volume=12 |issue=9 |pages=1080–1090 |doi=10.1109/TIP.2003.812329 |pmid=18237979 |bibcode=2003ITIP...12.1080U |url=https://infoscience.epfl.ch/record/63104/files/unser0305.pdf }}</ref><ref>{{cite book |last1=Bovik |first1=Alan C. |title=The Essential Guide to Video Processing |date=2009 |publisher=[[Academic Press]] |isbn=9780080922508 |page=355 |url=https://books.google.com/books?id=wXmSPPB_c_0C&pg=PA355}}</ref> reversible integer [[wavelet transform]])
** [[Lossless JPEG#JPEG-LS|JPEG-LS]]
** [[JPEG XL]]
** [[JPEG XR]] – formerly ''WMPhoto'' and ''HD Photo''
** [[Discrete cosine transform|LDCT]] – [[Discrete Cosine Transform]]<ref>{{cite journal |last1=Ahmed |first1=Nasir |author1-link=N. Ahmed |last2=Mandyam |first2=Giridhar D. |last3=Magotra |first3=Neeraj |editor-first1=Arturo A. |editor-first2=Robert J. |editor-first3=Edward J. |editor-last1=Rodriguez |editor-last2=Safranek |editor-last3=Delp |title=DCT-based scheme for lossless image compression |journal=Digital Video Compression: Algorithms and Technologies 1995 |date=17 April 1995 |volume=2419 |pages=474–478 |doi=10.1117/12.206386 |publisher=International Society for Optics and Photonics|bibcode=1995SPIE.2419..474M }}</ref><ref>{{cite book |doi=10.1109/ICASSP.1998.681802 |chapter=Reversible discrete cosine transform |title=Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181) |date=1998 |last1=Komatsu |first1=K. |last2=Sezaki |first2=K. |volume=3 |pages=1769–1772 |isbn=0-7803-4428-6 }}</ref>
** [[PCX]] – PiCture eXchange
** [[QOI (image format)|QOI]] – Quite OK Image Format
** [[Truevision TGA|TGA]] – Truevision TGA
** [[Tag Image File Format|TIFF]] – Tag Image File Format
** [[WebP]]

=== 3D Graphics ===
* [[OpenCTM]] – Lossless compression of 3D triangle meshes

=== Video ===

See [[List of codecs#Lossless video compression|list of lossless video codecs]]

===Cryptography===
[[Cryptosystem]]s 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]].<ref name="MenezesOV1996">{{cite book|author1=Alfred J. Menezes|author2=Paul C. van Oorschot|author3=Scott A. Vanstone|title=Handbook of Applied Cryptography |url=https://books.google.com/books?id=MhvcBQAAQBAJ&q=%22compression%22+%22unicity+distance%22|date=16 October 1996|publisher=CRC Press|isbn=978-1-4398-2191-6}}</ref> 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 ===
[[Compression of genomic sequencing data|Genetics compression algorithms]] (not to be confused with [[genetic algorithm]]s) 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 [[International_HapMap_Project|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.<ref>{{cite journal |author=Chanda, P. |author2=Elhaik, E. |author3=Bader, J.S. | title=HapZipper: sharing HapMap populations just got easier | journal=Nucleic Acids Res | pages=1–7 | year=2012 | pmid=22844100 | doi=10.1093/nar/gks709 | volume=40 | issue=20 | pmc=3488212}}</ref>

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.<ref name=Pratas>{{cite book |last1=Pratas |first1=D. |last2=Pinho |first2=A. J. |last3=Ferreira |first3=P. J. S. G. |date=2016 |chapter=Efficient compression of genomic sequences |title=Data Compression Conference |location=Snowbird, Utah |url=http://sweet.ua.pt/pratas/papers/Pratas-2016b.pdf}}</ref> For [[eukaryotes]] XM is slightly better in compression ratio, though for sequences larger than 100 MB its computational requirements are impractical.

===Executables===
{{main article|Executable compression}}
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 (computer programming)|demo]] coding, where competitions are held for demos with strict size limits, as small as 1 [[kilobyte]].
This type of compression is not strictly limited to binary executables, but can also be applied to scripts, such as [[JavaScript]].