4511
правок
Сжатие целочисленных последовательностей и множеств: различия между версиями
Перейти к навигации
Перейти к поиску
м
Сжатие целочисленных последовательностей и множеств (посмотреть исходный код)
Версия от 11:08, 2 марта 2018
, 2 марта 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 49: | Строка 49: | ||
'''Коды Фибоначчи''' | '''Коды Фибоначчи''' | ||
Еще один любопытный код был выведен на основе последовательности Фибоначии, которая в данном контексте выглядит следующим образом: <math>F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, F_5 = 8 | Еще один любопытный код был выведен на основе последовательности Фибоначии, которая в данном контексте выглядит следующим образом: <math>F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, F_5 = 8</math> и т. д. Представление натурального числа Цекендорфа представляет собой список чисел Фибоначчи, которые в сумме дают нужное число, при этом использование двух последовательных чисел Фибоначчи не допускается. К примеру, число 10 представляет собой сумму <math>2 + 8 = F_2 + F_5</math>. | ||
Самый простой код Фибоначчи выводится непосредственно из упорядоченного представления Цекендорфа для нужного числа и содержит бит в значении «0» в i-й позиции кодового слова (считая слева), если | Самый простой код Фибоначчи выводится непосредственно из упорядоченного представления Цекендорфа для нужного числа и содержит бит в значении «0» в i-й позиции кодового слова (считая слева), если <math>F_i \;</math> не входит в сумму, и «1» – если входит; индексы рассматриваются в порядке возрастания. Поскольку <math>F_i \;</math> и <math>F_{i + 1} \;</math> не могут одновременно входить в состав представления, последними двумя битами строки должны быть «01». Добавления справа бита «1», таким образом, будет достаточно для обозначения конца любого кодового слова. Как всегда, из предположения о монотонном возрастании вероятностей появления символов следует, что небольшим значениям присваиваются короткие коды. Единица кодируется значением «1-1», следующими кодовыми словами являются «01-1», «001-1», «101-1», «0001-1» и «1001-1»; дефисы здесь также служат иллюстративным целям. | ||
Байт-синхронизованные коды | В силу соотношения <math>F_n \approx \phi^n \;</math>, где <math>\phi \;</math> – золотое сечение <math>\phi = (1 + \sqrt{5})/2 \approx 1,61803 \;</math>, кодовое слово для x имеет длину примерно <math>1 + log_{\phi} \; x \approx 1 + 1,44 \; log_2 \; x</math> бит и оказывается более коротким по сравнению со словами гамма-кода Элиаса для всех значений, кроме x = 1. Оно также не уступает словам дельта-кода Элиаса для широкого диапазона практически важных значений между 2 и <math>F_19 = 6765</math>. Возможно также использование кодов Фибоначчи более высокого порядка, с большей минимальной длиной кодового слова, а также с уменьшенными коэффициентами при логарифмическом терме. Фенвик в своей работе [8] выполнил качественный обзор кодов Фибоначчи. | ||
'''Байт-синхронизованные коды''' | |||
Выполнение необходимых операций упаковки и распаковки битов для выявления неограниченных последовательностей битов может быть достаточно дорогостоящим с точки зрения пропускной способности функций декодирования. Для решения этой проблемы был разработан целый класс кодов, работающих не с битами, а с байтами - и байт-синхронизированные коды. | Выполнение необходимых операций упаковки и распаковки битов для выявления неограниченных последовательностей битов может быть достаточно дорогостоящим с точки зрения пропускной способности функций декодирования. Для решения этой проблемы был разработан целый класс кодов, работающих не с битами, а с байтами - и байт-синхронизированные коды. | ||
Простейшим примером байт-синхронизированного кода может служить восьмибитный аналог механизма гамма-кода Элиаса с чередованием битов. Верхний бит каждого байта зарезервирован для флага, имеющего значение «0» в случае, если этот байт является последним в кодовом слове, и «1», если он не является последним и нужно учитывать также следующий байт. Другие семь битов каждого байта используются для представления данных. К примеру, число 1234 кодируется при помощи двух байтов, «2 09-0 08», и реконструкируется при посощи вычисления (209 -128+ l)x 128°+ (008 + l)x 1281 = 1234. | Простейшим примером байт-синхронизированного кода может служить восьмибитный аналог механизма гамма-кода Элиаса с чередованием битов. Верхний бит каждого байта зарезервирован для флага, имеющего значение «0» в случае, если этот байт является последним в кодовом слове, и «1», если он не является последним и нужно учитывать также следующий байт. Другие семь битов каждого байта используются для представления данных. К примеру, число 1234 кодируется при помощи двух байтов, «2 09-0 08», и реконструкируется при посощи вычисления (209 -128+ l)x 128°+ (008 + l)x 1281 = 1234. | ||