Изменения

Перейти к: навигация, поиск

Гамма-, дельта- и омега-код Элиаса

150 байт добавлено, 20:45, 29 ноября 2014
Коды переменной длины (Variable + Variable)
{{Определение
|id = def1
|definition ='''Унарное представление числа n ''' (англ. ''unary code'') {{---}} n подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: n нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.}}
Например, унарный код нуля {{---}} 0, единицы {{---}} 10, двойки {{---}} 110 и т. д.
{{Определение
|id = def1
|definition ='''Гамма-код Элиаса ''' (англ. ''Elias <tex>γ</tex> code'') {{---}} это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он обычно используется при кодировании целых чисел, максимальное значение которых не может быть определено заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто, чем большие.}}
==== Алгоритм построения гамма-кода Элиаса ====
{{Определение
|id = def1
|definition ='''Дельта-код Элиаса ''' (англ. ''Elias <tex>δ</tex> code'') {{---}} это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Как далее будет видно, дельта-код с некоторого числа короче гамма-кода.}}
==== Алгоритм построения дельта-кода Элиаса ====
{{Определение
|id = def1
|definition ='''Омега-код Элиаса ''' (англ. ''Elias <tex>ω</tex> code'') {{---}} — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Так же, как гамма- и дельта-код Элиаса, он приписывает к началу целого числа порядок его величины в универсальном коде. Однако, в отличие от двух других указанных кодов, омега-код рекурсивно кодирует префикс, именно поэтому он также известен, как '''рекурсивный код Элиаса'''.}}
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
577
правок

Навигация