Adaptive coding: Difference between revisions

Revision as of 06:54, 7 December 2024

Latest revision as of 04:30, 6 March 2025

(One intermediate revision by one other user not shown)

Line 1:

{{unreferencedMore citations needed|date=JuneMarch 2009|bot=yes2025}}

'''Adaptive coding''' refers to variants of [[entropy encoding]] methods of [[lossless data compression]].{{Citation needed|date=March 2025}} They are particularly suited to [[streaming data]], as they adapt to localized changes in the characteristics of the data,{{Citation needed|date=March 2025}} and don't require a first pass over the data to calculate a probability model.<ref name=":0">{{Cite book |last=Williams |first=Ross N. |url=https://www.google.com/books/edition/Adaptive_Data_Compression/lBY6CcXU59EC?hl=en&gbpv=1&pg=PR11&printsec=frontcover |title=Adaptive Data Compression |date=1991 |publisher=Springer Science & Business Media |isbn=978-0-7923-9085-5 |language=en}}</ref> The cost paid for these advantages is that the encoder and decoder must be more complex to keep their states synchronized, and more computational power is needed to keep adapting the encoder/decoder state.

Almost all [[data compression]] methods involve the use of a ''model'', a prediction of the composition of the data. When the data matches the prediction made by the model, the encoder can usually transmit the content of the data at a lower information cost, by making reference to the model.

Line 6 ⟶ 7:

which are hardly comparable to compression techniques typically called ''adaptive''.

[[Run-length encoding]] and the typical [[JPEG]] compression with run length encoding and predefined Huffman codes do not transmit a model.

A lot of other methods adapt their model to the current file and need to transmit it in addition to the encoded data, because both the encoder and the decoder need to use the model.<ref>{{Cite journal |author1=Gutnisky, D. |author2=Dragoi, V. |year=2008 |title=Adaptive coding of visual information in neural populations |journal=Nature |volume=452 |pages=220–224 |doi=10.1038/nature06563}}</ref>

In adaptive coding, the encoder and decoder are instead equipped with a predefined meta-model about how they will alter their models in response to the actual content of the data, and otherwise start with a blank slate, meaning that no initial model needs to be transmitted. As the data is transmitted, both encoder and decoder adapt their models, so that unless the character of the data changes radically, the model becomes better-adapted to the data it is handling and compresses it more efficiently approaching the efficiency of the static coding.

==Adaptive method==

The operating method of adaptive encoding algorithms is as follows:<ref name=":0" />

===Encoder===