4430
правок
Сжатие целочисленных последовательностей и множеств: различия между версиями
Материал из WEGA
Сжатие целочисленных последовательностей и множеств (посмотреть исходный код)
Версия от 10:56, 2 марта 2018
, 2 марта 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
При переходе от одного члена семейства к другому предыдущий член определяет количество бит в стандартном бинарном представлении кодируемого значения x (иначе говоря, значение <math>1 + \lfloor log_2 \; x \rfloor)</math>; после определения длины концевые биты x, при пропуске верхнего бита, кодируются бинарным образом. | При переходе от одного члена семейства к другому предыдущий член определяет количество бит в стандартном бинарном представлении кодируемого значения x (иначе говоря, значение <math>1 + \lfloor log_2 \; x \rfloor)</math>; после определения длины концевые биты x, при пропуске верхнего бита, кодируются бинарным образом. | ||
К примеру, второй член семейства Элиаса, Cy («гамма-код»), можно рассматривать как унарно-бинарный код: унарный код определяет префиксную часть, представляющую собой степень x, а последующий бинарный отражает величину x в рамках диапазона, обозначенного префиксной частью. Таким образом, первые несколько кодовых слов гамма-кода выглядят как «0», «10-0», «10-1», «110-00» и так далее; дефисы здесь также приведены исключительно в иллюстративных целях. В общем случае кодовое слово в гамма-коде для значения x требует 1 + bl°g2 бит для унарной префиксной части и bl°g2 xc f°r – для бинарной суффиксной, а идеальное распределение вероятностей задается формулой Prob(x) > 1/(2x2). | |||
Следующий после Cy член семейства Elias – Cg. Единственное отличие между ними заключается в том, что префиксная часть кодовых слов в дельта-коде представлена в виде гамма-кода, а не унарного выражения. Следующие элементы семейства кодов Элиаса легко получить, рекурсивно применяя тот же процесс, однако с практической точки зрения Cg оказывается последним полезным членом семейства даже для относительно больших значений x. Чтобы убедиться в этом, заметим, что |Cy(x)| C |Q(x)| в случае x < 31, что означает, что Cg длиннее следующего кода Элиаса только для значений x > 232. | |||
'''Коды Фибоначчи''' | |||
Еще один любопытный код был выведен на основе последовательности Фибоначии, которая в данном контексте выглядит следующим образом: F1 = 1, F2 = 2, F3 = 3, F4 = 5, F5 = 8 и т. д. Представление натурального числа Цекендорфа представляет собой список чисел Фибоначчи, которые в сумме дают нужное число, при этом использование двух последовательных чисел Фибоначчи не допускается. К примеру, число 10 представляет собой сумму 2 + 8 = F2 + F5. | |||
Самый простой код Фибоначчи выводится непосредственно из упорядоченного представления Цекендорфа для нужного числа и содержит бит в значении «0» в i-й позиции кодового слова (считая слева), если Fi не входит в сумму, и «1» – если входит; индексы рассматриваются в порядке возрастания. Поскольку Fi и Fi+1 не могут одновременно входить в состав представления, последними двумя битами строки должны быть «01». Добавления справа бита «1», таким образом, будет достаточно для обозначения конца любого кодового слова. Как всегда, из предположения о монотонном возрастании вероятностей появления символов следует, что небольшим значениям присваиваются короткие коды. Единица кодируется значением «1-1», следующими кодовыми словами являются «01-1», «001-1», «101-1», «0001-1» и «1001-1»; дефисы здесь также служат иллюстративным целям. | |||
В силу соотношения Fn & фп, где ' – и золотое сечение ф = (1 + p5)/2 ^ 1:61803, кодовое слово для x имеет длину примерно 1 + log*, x Јrf 1 + 1:44log2 x бит и оказывается более коротким по сравнению со словами гамма-кода Элиаса для всех значений, кроме x = 1. Оно также не уступает словам дельта-кода Элиаса для широкого диапазона практически важных значений между 2 и F19 = 6765. Возможно также использование кодов Фибоначчи более высокого порядка, с большей минимальной длиной кодового слова, а также с уменьшенными коэффициентами при логарифмическом терме. Фенвик в своей работе [ ] выполнил качественный обзор кодов Фибоначчи. | |||
Байт-синхронизованные коды | |||
Выполнение необходимых операций упаковки и распаковки битов для выявления неограниченных последовательностей битов может быть достаточно дорогостоящим с точки зрения пропускной способности функций декодирования. Для решения этой проблемы был разработан целый класс кодов, работающих не с битами, а с байтами - и байт-синхронизированные коды. | |||
Простейшим примером байт-синхронизированного кода может служить восьмибитный аналог механизма гамма-кода Элиаса с чередованием битов. Верхний бит каждого байта зарезервирован для флага, имеющего значение «0» в случае, если этот байт является последним в кодовом слове, и «1», если он не является последним и нужно учитывать также следующий байт. Другие семь битов каждого байта используются для представления данных. К примеру, число 1234 кодируется при помощи двух байтов, «2 09-0 08», и реконструкируется при посощи вычисления (209 -128+ l)x 128°+ (008 + l)x 1281 = 1234. | |||
В этом простейшем случае байт-синхронизированного кода используются 8 d(log2 x)/7e бит, что делает его асимптотически более эффективным, чем гамма-код Элиаса, требующий 1 + 2 blog2 xc бит. Однако, поскольку минимальная длина кодового слова составляет восемь бит, байт-синхронизированные коды оказываются чрезмерно дорогостоящими для представления небольших чисел. | |||
Декодирование байт-синхронизированных кодов не требует продолжительного времени. Другое полезное свойство такого подхода – возможность быстрого «просмотра» вперед сжатого потока на заданное число кодовых слов. И, наконец, третье преимущество байт-синхронизированных кодов – возможность поиска в сжатом сообщении посредством перевода шаблона поиска в последовательность байтов при помощи того же алгоритма кодирования и последующего применения утилиты побайтового сопоставления с образцом [7]. Если все последние байты имеют нулевые верхние биты, это означает, что единичный прогон дополнительной проверки обнаружил ложные «попадания». | |||
Более эффективный механизм применения байт-синхронизированных кодов был получен в результате наблюдения, заключающегося в том, что в качестве разделителя между байтом-ограничителем и байтом-продолжателем не обязательно должно использоваться принятое ранее число 128, и выбор подходящего числа определяет соответствующие компромиссные соотношения длин кодовых слов [ ]. При использовании так называемого (S, C)-байт-синхронизированного подхода выбираются значения S и C, составляющие в сумме S + C = 256, так что каждое кодовое слово состоит из последовательности (пустой или непустой) байтов-продолжателей со значениями, большими или равными S, и заканчивается финальным байтом-ограничителем со значением, меньшим S. Также известны методы, в которых байты применяются в качестве единиц кодирования при выполнении кодирования Хаффмана, использующего либо восьмибитные символы для кодирования, либо семибитные символы с флагами [ ]; а также методы, выполняющие частичную перестановку алфавита и не требующие полного отображения [ ]. Кулпеппер и Моффат [6] также описали метод кодирования с синхронизацией по байтам, создающий множество кодовых слов на основе байтов, в которых первый байт уникальным образом определяет длину кодового слова. Аналогичным образом можно использовать полубайтовое кодирование, 4-битный аналог байт-синхронизированного подхода, при котором один бит резервируется для флага «ограничитель-продолжатель», а три остальных используются для хранения данных. | |||
'''Другие статические коды''' | |||
