Изменения

К примеру, множество двоичных слов <tex>S_1</tex> Примерами кодов без памяти являются [[Алгоритм Хаффмана|кодирование Хаффмана]] и кодирование Шеннона-Фано.=== Достоинства кодов без памяти === <tex> \{00*Данные коды являются префиксными, 01что упрощает декодирование, 100, 110, 1010, 1011\} </tex> является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных совместных комбинаций (<tex>w_i</tex>, <tex>w_j</tex>) из <tex>S_1</tex>поэтому часто именно им отдается предпочтение. *Таким способом кодирования удается получить более короткие коды, то видно, что <tex>w_i</tex> никогда не явится префиксом (или началом) <tex>w_j</tex>чем с помощью кода фиксированной длины. С другой стороны, множество <tex>S_2</tex> = <tex> \{00*Декодировать сообщение можно по мере поступления, 001, 1110\} </tex> не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества {{---}} 001. Соответственно, множество <tex>S_1</tex> может быть множеством кодовых слов для вектора данных в коде без памяти, а <tex>S_2</tex> {{---}} нетполучая его целиком.

Примерами === Недостатки кодов без памяти ===Коды Хаффмана и Шеннона-Фано являются оптимальными, но все же имеют ряд недостатков. *При кодировании методами Хаффмана или Шеннона используются вероятности появления символов алфавита в тексте. То есть для построения кода нам нужно обладать этой информацией. Поэтому необходимо знать всю кодируемую последовательность заранее.*Для того, чтобы декодер мог расшифровать файл, таблицу частот, которой пользовался кодер, следует записать в сжатый файл. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может не оправдать сжатия. Хотя для кодов Хаффмана можно таблицу передавать [[Оптимальное хранение словаря в алгоритме Хаффмана| оптимально]]*Необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и дерево кодирования Хаффмана), другого {{---}} для собственно кодирования. === Универсальное кодирование ==={{Определение|id = def1|definition ='''Универсальный код ''' (англ. ''universal code'') {{---}} префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение — монотонно (то есть <tex>p(i) \geqslant p(i+1)</tex> для любого <tex>i</tex>), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей.}}Универсальное кодирование применяется, когда декодер не знает, что ему придет следующим, и ему приходится работать с данными по мере поступления. Коды Элиаса позволяют производить процесс декодирования очень просто. По определенному правилу последовательно считываем группы из нулей или единиц и на основании результатов обработки только что считанных данных читаем дальше по тому же правилу. Следовательно, мы можем однозначно декодировать число, либо сказать, что в коде ошибка. Таким образом, мы можем быстро передавать последовательность чисел, так же быстро и точно ее декодируя. Коды Элиаса для их построения не требуют использования вероятности появления символов, чем выигрывают у кодов Хаффмана и кодирование Шеннона — Фано. Данные коды могут быть использованы для шифрования, так как по скорости построение и декодирование этих кодов сильно выигрывает у большинства остальных, что в настоящее время очень важно. Однако длины кодов Элиаса зачастую превышают длины обычных двоичных представлений чисел, что накладывает ограничения на область их использования. Это является следствием такого способа кодирования информации. Поэтому лучше использовать эти коды тогда, когда нам передают маленькие числа. Данные коды применяются и имеют неплохие результаты сжатия. Например, если мы строку преобразуем при помощи алгоритма [[Преобразование 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>111_2+</tex> = '''<tex>111_2 = 15</tex>'''.

Гамма-код Элиаса не подходит для кодирования нулевых значений или отрицательных чисел. Для того, чтобы закодировать ноль нужно прибавить к нему <tex>1</tex> до кодирования и отнять после декодирования. Чтобы закодировать все целые числа можно установить биекцию (соответствие), отображая целые числа из <tex>(0, 1, -1, 2, -2, 3, -3, ...\dots)</tex> в <tex>(1, 2, 3, 4, 5, 6, 7, ...\dots)</tex>.

# В двоичном представлении числа <tex>N = 10 = 1010_2 </tex> всего <tex>4</tex> значащих бита <tex>(L = 4)</tex>.# В двоичном представлении числа <tex>L = 4 = 100_2 </tex> всего <tex>3</tex> значащих бита <tex>(M = 3)</tex>.

|1||'''1'''|||1||'''1'''||1

|2...3||'''01x'''||3||'''010x'''||4

|4...7||'''001xx'''||5||'''011xx'''||5

|8...15||'''0001xxx'''||7||'''00100xxx'''||8

|16...31||'''00001xxxx'''||9||'''00101xxxx'''||9

|32...63||'''000001xxxxx'''||11||'''00110xxxxx'''||10

|64...127||'''0000001xxxxxx'''||13||'''00111xxxxxx'''||11

|128...255||'''00000001xxxxxxx'''||15||'''0001000xxxxxxx'''||14

'''Дельта-код''': <tex>n...(2\times{L}+1</tex> раз<tex>)...nx..(K</tex> раз<tex>)..x</tex>; длина: <tex>2\times{L}+K+1</tex> бит, где <tex>L = [\log_2{(K+1)}]</tex> {{- --}} целая часть логарифма числа <tex>(K+1)</tex> по основанию <tex>2</tex>; <tex>n</tex> {{--- }} биты, относящиеся к записи экспоненты дельта-кода, их число <tex>2\times{L} + 1</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>

|definition ='''Омега-код Элиаса ''' (англ. ''Elias omega code'') {{---}} — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Так же, как гамма- и дельта-код Элиаса, он приписывает к началу целого числа порядок его величины в универсальном коде. Однако, в отличие от двух других указанных кодов, омега-код рекурсивно кодирует префикс, именно поэтому он также известен, как '''рекурсивный код Элиаса'''.}}

Данные коды состоят из последовательности групп длинной <tex>L_1, L_2, L_3, …\dots, L_m</tex> бит, которые начинаются (слева) с бита <tex>1</tex>. В конце последовательности (справа) всегда <tex>0</tex>. Длина каждой следующей <tex>(n+1)</tex>-й группы задается значением битов предыдущей <tex>n</tex>-й группы.

# В <tex>N</tex> записать новое значение {{- --}} количество только что записанных цифр(бит), минус один.

*[https://ru.wikipedia.org/wiki/%D0%93%D0%B0%D0%BC%D0%BC%D0%B0-%D0%BA%D0%BE%D0%B4_%D0%AD%D0%BB%D0%B8%D0%B0%D1%81%D0%B0 Википедия {{- --}} Гамма-код Элиаса]*[https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D1%8C%D1%82%D0%B0-%D0%BA%D0%BE%D0%B4_%D0%AD%D0%BB%D0%B8%D0%B0%D1%81%D0%B0 Википедия {{--- }} Дельта-код Элиаса]*[https://ru.wikipedia.org/wiki/%D0%9E%D0%BC%D0%B5%D0%B3%D0%B0-%D0%BA%D0%BE%D0%B4_%D0%AD%D0%BB%D0%B8%D0%B0%D1%81%D0%B0 Википедия {{--- }} Омега-код Элиаса]*[https://ru.wikipedia.org/wiki/%D0%A3%D0%BD%D0%B8%D0%B2%D0%B5%D1%80%D1%81%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4 Википедия {{--- }} Универсальный код]