Изменения

Примерами кодов без памяти являются [[Алгоритм Хаффмана|кодирование Хаффмана]] и кодирование Шеннона - Фано.

Коды Хаффмана и Шеннона — -Фано являются оптимальными, но все же имеют ряд недостатков. Во-первых, при *При кодировании методами Хаффмана или Шеннона используются вероятности появления символов алфавита в тексте. То есть для построения кода нам нужно обладать этой информацией. Поэтому необходимо знать всю кодируемую последовательность заранее.*Для того, чтобы декодер мог расшифровать файл , таблицу частот, которой пользовался кодер, следует записать в сжатый файл. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может не оправдать сжатия. Во-вторых, необходимость Хотя для кодов Хаффмана можно таблицу передавать [[Оптимальное хранение словаря в алгоритме Хаффмана| оптимально]]*Необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-деревадерево кодирования Хаффмана), другого {{---}} для собственно кодирования. 

Универсальное кодирование применяется, когда декодер не знает, что ему придет следующим, и ему приходится работать с данными по мере поступления. Коды Элиаса позволяют производить процесс декодирования очень просто. По определенному правилу последовательно считываем группы из нулей или единиц и на основании результатов обработки только что считанных данных читаем дальше по тому же правилу. Следовательно, мы можем однозначно декодировать число, либо сказать, что в коде ошибка. Таким образом, мы можем быстро передавать последовательность чисел, так же быстро и точно ее декодируя. Коды Элиаса для их построения не требуют использования вероятности появления символов, чем выигрывают у кодов Хаффмана и Шеннона. Данные коды могут быть использованы для шифрования, так как по скорости построение и декодирование этих кодов сильно выигрывает у большинства остальных, что в настоящее время очень важно. Однако длины кодов Элиаса зачастую превышают длины обычных двоичных представлений чисел, что накладывает ограничения на область их использования. Это является следствием такого способа кодирования информации. Поэтому лучше использовать эти коды тогда, когда нам передают маленькие числа. Данные коды применяются и имеют неплохие результаты сжатия. Например, если мы строку преобразуем при помощи алгоритма [[Преобразование MTF|move-to-front]], то получим на выходе последовательность довольно небольших чисел. На небольшие числа коды Элиаса тратят мало бит, поэтому данный алгоритм будет довольно эффективен. Если мы получим значительное количество нулей, а что-то большое будет встречаться иногда, то мы неплохо закодируем и сожмём последовательность. Например, хороший результат даст такая связка: Барроуз-Уиллер + MTF + Коды Элиаса.

Значащие цифры начинаются со старшей ненулевой цифры: например, в числе <tex>000001101_2</tex> = <tex>1\times2^0+0\times2^1+1\times2^2+1\times2^3+0\times2^4+0\times... \dots = 13</tex> это последние <tex>4</tex> цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем.

# Считываем единицу и <tex>N = 3</tex> бит. Получаем <tex>2^3</tex> <tex>+</tex> <tex>111_2</tex> = '''<tex>15</tex>'''.

Можно видеть, что для чисел <tex>2, 3, 8...\dots 15</tex> дельта-код длиннее гамма-кода, для чисел <tex>1, 4...7, 16...31</tex> длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Это происходит вследствие того, как строятся данные коды. Как показано выше, длина гама-кода <tex>2\times{K} + 1</tex>, что при больших <tex>K</tex> очевидно больше, чем <tex>2\times{[\log_2{(K+1)}]} + K + 1</tex>

Здесь быстрое возрастание количества значений в группе сильно напоминает [https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%90%D0%BA%D0%BA%D0%B5%D1%80%D0%BC%D0%B0%D0%BD%D0%B0 [СНМ (реализация с помощью леса корневых деревьев)#Асимптотика|функцию Аккермана]]. Начиная с третьей <tex>(i = 3)</tex> группы их диапазон лежит между значениями функции <tex>A(i - 3, 4) + 3</tex> и <tex>A(i -2, 4) + 3</tex>.