Изменения

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

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

891 байт убрано, 18:04, 12 декабря 2014
Коды переменной длины (Variable + Variable)
|definition ='''Унарное представление числа <tex>n</tex> ''' (англ. ''unary code'') {{---}} <tex>n</tex> подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: <tex>n</tex> нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.}}
Например, унарный код нуля {{---}} <tex>0</tex>, единицы {{---}} <tex>10</tex>, двойки {{---}} <tex>110</tex> и т. д.
{{Определение
|id = def1
|definition ='''Универсальный код ''' (англ. ''universal code'') {{---}} префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение — монотонно (то есть <tex>p(i) \geqslant p(i+1)</tex> для любого <tex>i</tex>), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей.}}
=== Гамма-код Элиаса ===
577
правок

Навигация