Арифметическое кодирование: различия между версиями
Перейти к навигации
Перейти к поиску
w>Unomano |
w>Ewger (→Принцип действия: перевод примера из материала на англ.) |
||
| Строка 11: | Строка 11: | ||
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока. | Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока. | ||
| + | <!-- закоментировано под перевод | ||
| + | == Пример работы == | ||
| + | [[Image:Arithmetic encoding.svg|400px|thumb|right|A diagram showing decoding of 0.538 (the circular point) in the example model. The region is divided into subregions proportional to symbol frequencies, then the subregion containing the point is successively subdivided in the same way.]] | ||
| + | Suppose we are trying to decode a message encoded with the four-symbol model described above. The message is encoded in the fraction 0.538 (for clarity, we are using decimal, instead of binary; we are also assuming that whoever gave us the encoded message gave us only as many digits as needed to decode the message. We will discuss both issues later.) | ||
| + | |||
| + | We start, as the encoder did, with the interval <nowiki>[0,1)</nowiki>, and using the same model, we divide it into the same four sub-intervals that the encoder must have. Our fraction 0.538 falls into the sub-interval for NEUTRAL, <nowiki>[0, 0.6)</nowiki>; this indicates to us that the first symbol the encoder read must have been NEUTRAL, so we can write that down as the first symbol of our message. | ||
| + | |||
| + | We then divide the interval <nowiki>[0, 0.6)</nowiki> into sub-intervals: | ||
| + | * the interval for NEUTRAL would be <nowiki>[0, 0.36)</nowiki> ''-- 60% of <nowiki>[0, 0.6)</nowiki>'' | ||
| + | * the interval for POSITIVE would be <nowiki>[0.36, 0.48)</nowiki> ''-- 20% of <nowiki>[0, 0.6)</nowiki>'' | ||
| + | * the interval for NEGATIVE would be <nowiki>[0.48, 0.54)</nowiki> ''-- 10% of <nowiki>[0, 0.6)</nowiki>'' | ||
| + | * the interval for END-OF-DATA would be <nowiki>[0.54, 0.6)</nowiki>. ''-- 10% of <nowiki>[0, 0.6)</nowiki>'' | ||
| + | |||
| + | Our fraction of .538 is within the interval <nowiki>[0.48, 0.54)</nowiki>; therefore the second symbol of the message must have been NEGATIVE. | ||
| + | |||
| + | Once more we divide our current interval into sub-intervals: | ||
| + | * the interval for NEUTRAL would be <nowiki>[0.48, 0.516)</nowiki> | ||
| + | * the interval for POSITIVE would be <nowiki>[0.516, 0.528)</nowiki> | ||
| + | * the interval for NEGATIVE would be <nowiki>[0.528, 0.534)</nowiki> | ||
| + | * the interval for END-OF-DATA would be <nowiki>[0.534, 0.540)</nowiki>. | ||
| + | |||
| + | Our fraction of .538 falls within the interval of the END-OF-DATA symbol; therefore, this must be our next symbol. Since it is also the internal termination symbol, it means our decoding is complete. (If the stream was not internally terminated, we would need to know where the stream stops from some other source -- otherwise, we would continue the decoding process forever, mistakenly reading more symbols from the fraction than were in fact encoded into it.) | ||
| + | |||
| + | The same message could have been encoded by the equally short fractions .534, .535, .536, .537 or .539. This suggests that our use of decimal instead of binary introduced some inefficiency. This is correct; the information content of a three-digit decimal is approximately 9.966 [[bit]]s; we could have encoded the same message in the binary fraction .10001010 (equivalent to .5390625 decimal) at a cost of only 8 bits. (Note that the final zero must be specified in the binary fraction, or else the message would be ambiguous without external information such as compressed stream size.) | ||
| + | |||
| + | This 8 bit output is larger than the information content, or [[information entropy|entropy]] of our message, which is 1.57 * 3 or 4.71 bits. The large difference between the example's 8 (or 7 with external compressed data size information) bits of output and the entropy of 4.71 bits is caused by the short example message not being able to exercise the coder effectively. We claimed symbol probabilities of <nowiki>[.6, .2, .1, .1]</nowiki>, but the actual frequencies in this example are <nowiki>[.33, 0, .33 .33]</nowiki>. If the intervals are readjusted for these frequencies, the entropy of the message would be 1.58 bits and you could encode the same NEUTRAL NEGATIVE ENDOFDATA message as intervals <nowiki>[0, 1/3); [1/9, 2/9); [5/27, 6/27);</nowiki> and a binary interval of <nowiki>[1011110, 1110001)</nowiki>. This could yield an output message of 111, or just 3 bits. This is also an example of how statistical coding methods like arithmetic encoding can yield a size gain, especially if the probability model is off. | ||
| + | |||
| + | --> | ||
{{методы сжатия}} | {{методы сжатия}} | ||
Версия от 22:52, 21 сентября 2007
Характеристики
Обеспечивает лучшую степень сжатия чем алгоритм Хаффмана. На каждый символ требуется почти бит, где — информационная энтропия источника.
Принцип действия
Пусть у нас есть некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1.
Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответствовать одному символу.
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
Ошибка Lua в Модуль:Navbox на строке 353: attempt to index local 'listText' (a nil value).
de:Arithmetisches Kodieren en:Arithmetic coding ja:算術符号 ko:산술 부호화 nl:Aritmetische codering pl:Kodowanie arytmetyczne pt:Codificação aritmética zh:算术编码