577
правок
Изменения
→Универсальное кодирование
Примерами кодов без памяти являются [[Алгоритм Хаффмана|кодирование Хаффмана]] и кодирование Шеннона-Фано.
=== Достоинства кодов без памяти ===
*Эти Данные коды являются однозначно декодируемымипрефиксными, в них никакое кодовое слово не является префиксом какого-то другого кодового слова. Это очень что упрощает декодирование, поэтому часто именно им отдается предпочтение.
*Таким способом кодирования удается получить более короткие коды, чем с помощью кода фиксированной длины.
*И что немаловажно, декодировать Декодировать сообщение можно по мере поступления, не получая его целиком.
=== Недостатки кодов без памяти ===
Коды Хаффмана и Шеннона-Фано являются оптимальными, но все же имеют ряд недостатков.
*При кодировании методами Хаффмана или Шеннона используются вероятности появления символов алфавита в тексте. То есть для построения кода нам нужно обладать этой информацией. Поэтому необходимо знать всю кодируемую последовательность заранее.*Для того, чтобы декодер мог расшифровать файл , таблицу частот, которой пользовался кодер, следует записать в сжатый файл. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может не оправдать сжатия. Хотя для кодов Хаффмана можно таблицу передавать [[Оптимальное хранение словаря в алгоритме Хаффмана| оптимально]]*Необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-деревадерево кодирования Хаффмана), другого {{---}} для собственно кодирования.
=== Универсальное кодирование ===
Универсальное кодирование применяется, когда декодер не знает, что ему придет следующим, и ему приходится работать с данными по мере поступления.
Коды Элиаса позволяют производить процесс декодирования очень просто. По определенному правилу последовательно считываем группы из нулей или единиц и на основании результатов обработки только что считанных данных читаем дальше по тому же правилу. Следовательно, мы можем однозначно декодировать число, либо сказать, что в коде ошибка. Таким образом, мы можем быстро передавать последовательность чисел , так же быстро и точно ее декодируя.
Коды Элиаса для их построения не требуют использования вероятности появления символов, чем выигрывают у кодов Хаффмана и Шеннона. Данные коды могут быть использованы для шифрования, так как по скорости построение и декодирование этих кодов сильно выигрывает у большинства остальных, что в настоящее время очень важно. Однако длины кодов Элиаса зачастую превышают длины обычных двоичных представлений чисел, что накладывает ограничения на область их использования. Это является следствием такого способа кодирования информации. Поэтому лучше использовать эти коды тогда, когда нам передают маленькие числа.
Данные коды применяются и имеют неплохие результаты сжатия. Например, если мы строку преобразуем при помощи алгоритма [[Преобразование MTF|move-to-front]], то получим на выходе последовательность довольно небольших чисел. На небольшие числа коды Элиаса тратят мало бит, поэтому данный алгоритм будет довольно эффективен. Если мы получим значительное количество нулей, а что-то большое будет встречаться иногда, то мы неплохо закодируем и сожмём последовательность. Например, хороший результат даст такая связка: Барроуз-Уиллер + MTF + Коды Элиаса.
== Разделение мантисс и экспонент ==
# <tex>65536 ... 2\times10^{19728} (2^{2^{2^2}} ... 2^{2^{2^{2^2}}} - 1)</tex> {{---}} всего <tex>4</tex> группы.
Здесь быстрое возрастание количества значений в группе сильно напоминает [[СНМ (реализация с помощью леса корневых деревьев)#Асимптотика|функцию Аккермана]]. Начиная с третьей <tex>(i = 3)</tex> группы их диапазон лежит между значениями функции <tex>A(i - 3, 4) + 3</tex> и <tex>A(i -2, 4) + 3</tex>.
{| class="wikitable" style="width:10cm" border=1
