53
правки
Изменения
Нет описания правки
====Кодер====
1. Функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.<br/>
2. Инициализируем переменные tmp, для сохранения последнего элемента и last для хранения предыдущего числа.
Инициализируем цикл.<br/> 3. В цикле: <br/>
* 3.1 Сохраняем элемент с индексом i.<br/>
* 3.2 Вычисляем разницу между элементом под номером i и i-1 и перезаписываем ее в элемент массива с индексом i.<br/>
==Интервальное кодирование==
При интервальном кодировании все символы сообщения кодируются как одно число, для того чтобы достичь наилучшего коэффициента сжатия. Это работает эффективно с вероятностями появления символа не являющимися степенями двойки.
Интервальное кодирование работает так:<br/>
1. Выделяется достаточно большой диапазон целых чисел и дается оценка вероятности вхождения для символов.<br/>
2. Исходный диапазон чисел делится на поддиапазоны, размер которых пропорционален вероятности вхождения символа, за который они отвечают.<br/>3. Каждый символ сообщения кодируется, после чего диапазон сокращается до размера диапазона только что закодированного символа и вновь делится по вероятностям.<br/>
В декодере должны быть такое же распределение вероятностей как и при кодировании.
== Пример ==
Закодируем строку <tex>abehhilopsu</tex>.<br/>Для начала пропустим ее через дельта фильтр.<br/>Тогда исходная строка <tex>abehhilopsu</tex> примет вид: <tex>a</tex> <tex>1</tex> <tex>3</tex> <tex>3</tex> <tex>0</tex> <tex>1</tex> <tex>3</tex> <tex>3</tex> <tex>1</tex> <tex>3</tex> <tex>2</tex>. Как мы видим, теперь в нашей строке вместо 10 различных символов 5 различных символа.<br/>
Далее применим к получившейся строке метод "скользящего" окна:
{| border="1"
|<2,1,<tex>2</tex>>
|}
Получаем код: <tex>00a001003110431212<EOM></tex>, где <tex><EOM></tex>— это символ конца сообщения.<br> Для нашей строки получаем диапазон [<tex>0; 10^9</tex>] и распределение вероятностей: {<tex>0</tex>: 0,37; <tex>1</tex>: 0,26; <tex>2</tex>: 0,11; <tex>3</tex>: 0,11; <tex>4</tex>: 0,05; <tex>a</tex>: 0,05; <tex><EOM></tex>: 0,05}<br>
Таким образом, произведя интервальное кодирование нашей строки, получим диапазон который будет отвечать закодированному сообщению.
== См.также ==
* [[Алгоритмы LZ77 и LZ78]]
