Арифметическое кодирование — различия между версиями
Darkraven (обсуждение | вклад) м |
|||
| Строка 1: | Строка 1: | ||
== Определение == | == Определение == | ||
| − | {{Определение|definition= '''Арифметическое кодирование (Arithmetic coding) ''' {{---}} алгоритм сжатия информации без потерь. | + | {{Определение |
| + | |definition= '''Арифметическое кодирование (Arithmetic coding) ''' {{---}} алгоритм сжатия информации без потерь. | ||
}} | }} | ||
| − | Данный метод (как и алгоритм Хаффмана) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex> | + | Данный метод (как и алгоритм Хаффмана) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-log_2(p(a))</tex>, следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки). |
| + | == Принцип действия == | ||
| + | === Кодирование === | ||
| + | Алгоритму передаются текст для кодирования и список частот встречаемости символов. | ||
| + | # Рассмотрим отрезок <tex>[0; 1)</tex> на координатной прямой. | ||
| + | # Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления. | ||
| + | # Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Этот отрезок разделим на части, пропорциональные частотам встречаемости символов. | ||
| + | # Повторим пункт (3) до конца входного потока. | ||
| + | # Выберем любое число из получившегося отрезка (предпочтительно степень двойки). Это и будет результат арифметического кодирования. | ||
| + | <code> | ||
| + | left = 0 | ||
| + | right = 1 | ||
| + | while !eof | ||
| + | read(symb) | ||
| + | newRight = left + (right - left) * segment[symb].right <span style="color:green"> //segment[symb] — подотрезок отрезка [0; 1), соответствующий символу symb </span> | ||
| + | newLeft = left + (right - left) * segment[symb].left | ||
| + | left = newLeft | ||
| + | right = newRight | ||
| + | ans = (left + right) / 2 | ||
| + | </code> | ||
| + | === Декодирование === | ||
| + | Алгоритм по вещественному числу восстанавливает исходный текст. | ||
| + | # Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ. | ||
| + | # Нормируем подотрезок и вещественное число. | ||
| + | # Повторим п. (1—2) до тех пор, пока не получим ответ (до конца файла). | ||
| + | <code> | ||
| + | do | ||
| + | for i = 1 to n | ||
| + | if code >= segment[i].left && code < segment[i].right | ||
| + | write(segment[i].character) | ||
| + | code = (code – segment[i].left) / (segment[i].right – segment[i].left) | ||
| + | break | ||
| + | while (segment[i].character != eof) | ||
| + | </code> | ||
Версия 11:38, 23 декабря 2011
Определение
| Определение: |
| Арифметическое кодирование (Arithmetic coding) — алгоритм сжатия информации без потерь. |
Данный метод (как и алгоритм Хаффмана) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу с вероятностью появления допустимо ставить в соответствие код длины , следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).
Принцип действия
Кодирование
Алгоритму передаются текст для кодирования и список частот встречаемости символов.
- Рассмотрим отрезок на координатной прямой.
- Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
- Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Этот отрезок разделим на части, пропорциональные частотам встречаемости символов.
- Повторим пункт (3) до конца входного потока.
- Выберем любое число из получившегося отрезка (предпочтительно степень двойки). Это и будет результат арифметического кодирования.
left = 0
right = 1
while !eof
read(symb)
newRight = left + (right - left) * segment[symb].right //segment[symb] — подотрезок отрезка [0; 1), соответствующий символу symb
newLeft = left + (right - left) * segment[symb].left
left = newLeft
right = newRight
ans = (left + right) / 2
Декодирование
Алгоритм по вещественному числу восстанавливает исходный текст.
- Выберем на отрезке , разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
- Нормируем подотрезок и вещественное число.
- Повторим п. (1—2) до тех пор, пока не получим ответ (до конца файла).
do
for i = 1 to n
if code >= segment[i].left && code < segment[i].right
write(segment[i].character)
code = (code – segment[i].left) / (segment[i].right – segment[i].left)
break
while (segment[i].character != eof)
