4551
правка
Сжатие целочисленных последовательностей и множеств: различия между версиями
Материал из WEGA
Сжатие целочисленных последовательностей и множеств (посмотреть исходный код)
Версия от 11:14, 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> и т. д. Представление натурального числа Цекендорфа представляет собой список чисел Фибоначчи, которые в сумме дают нужное число, при этом использование двух последовательных чисел Фибоначчи не допускается. К примеру, число 10 представляет собой сумму <math>2 + 8 = F_2 + F_5</math>. | Еще один любопытный код был выведен на основе последовательности Фибоначии, которая в данном контексте выглядит следующим образом: <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>. | ||
| Строка 59: | Строка 60: | ||
'''Байт-синхронизованные коды''' | '''Байт-синхронизованные коды''' | ||
Выполнение необходимых операций упаковки и распаковки битов для выявления неограниченных последовательностей битов может быть достаточно дорогостоящим с точки зрения пропускной способности функций декодирования. Для решения этой проблемы был разработан целый класс кодов, работающих не с битами, а с байтами - и байт-синхронизированные коды. | Выполнение необходимых операций упаковки и распаковки битов для выявления неограниченных последовательностей битов может быть достаточно дорогостоящим с точки зрения пропускной способности функций декодирования. Для решения этой проблемы был разработан целый класс кодов, работающих не с битами, а с байтами - и байт-синхронизированные коды. | ||
Простейшим примером байт-синхронизированного кода может служить восьмибитный аналог механизма гамма-кода Элиаса с чередованием битов. Верхний бит каждого байта зарезервирован для флага, имеющего значение «0» в случае, если этот байт является последним в кодовом слове, и «1», если он не является последним и нужно учитывать также следующий байт. Другие семь битов каждого байта используются для представления данных. К примеру, число 1234 кодируется при помощи двух байтов, «2 09-0 08», и | Простейшим примером байт-синхронизированного кода может служить восьмибитный аналог механизма гамма-кода Элиаса с чередованием битов. Верхний бит каждого байта зарезервирован для флага, имеющего значение «0» в случае, если этот байт является последним в кодовом слове, и «1», если он не является последним и нужно учитывать также следующий байт. Другие семь битов каждого байта используются для представления данных. К примеру, число 1234 кодируется при помощи двух байтов, «2 09-0 08», и реконструируется при помощи вычисления (<math>209 - 128 + 1) \times 128^0 + (008 + 1) \times 128^1 = 1234</math>. | ||
В этом простейшем случае байт-синхронизированного кода используются 8 | В этом простейшем случае байт-синхронизированного кода используются <math>8 \lceil (log_2 \; x)/7 \rceil</math> бит, что делает его асимптотически более эффективным, чем гамма-код Элиаса, требующий <math>1 + 2 \lfloor log_2 \; x \rfloor</math> бит. Однако, поскольку минимальная длина кодового слова составляет восемь бит, байт-синхронизированные коды оказываются чрезмерно дорогостоящими для представления небольших чисел. | ||
| Строка 70: | Строка 73: | ||
Более эффективный механизм применения байт-синхронизированных кодов был получен в результате наблюдения, заключающегося в том, что в качестве разделителя между байтом-ограничителем и байтом-продолжателем не обязательно должно использоваться принятое ранее число 128, и выбор подходящего числа определяет соответствующие компромиссные соотношения длин кодовых слов [ ]. При использовании так называемого (S, C)-байт-синхронизированного подхода выбираются значения S и C, составляющие в сумме S + C = 256, так что каждое кодовое слово состоит из последовательности (пустой или непустой) байтов-продолжателей со значениями, большими или равными S, и заканчивается финальным байтом-ограничителем со значением, меньшим S. Также известны методы, в которых байты применяются в качестве единиц кодирования при выполнении кодирования Хаффмана, использующего либо восьмибитные символы для кодирования, либо семибитные символы с флагами [ ]; а также методы, выполняющие частичную перестановку алфавита и не требующие полного отображения [ ]. Кулпеппер и Моффат [6] также описали метод кодирования с синхронизацией по байтам, создающий множество кодовых слов на основе байтов, в которых первый байт уникальным образом определяет длину кодового слова. Аналогичным образом можно использовать полубайтовое кодирование, 4-битный аналог байт-синхронизированного подхода, при котором один бит резервируется для флага «ограничитель-продолжатель», а три остальных используются для хранения данных. | Более эффективный механизм применения байт-синхронизированных кодов был получен в результате наблюдения, заключающегося в том, что в качестве разделителя между ''байтом-ограничителем'' и ''байтом-продолжателем'' не обязательно должно использоваться принятое ранее число 128, и выбор подходящего числа определяет соответствующие компромиссные соотношения длин кодовых слов [3]. При использовании так называемого (S, C)-байт-синхронизированного подхода выбираются значения S и C, составляющие в сумме S + C = 256, так что каждое кодовое слово состоит из последовательности (пустой или непустой) байтов-продолжателей со значениями, большими или равными S, и заканчивается финальным байтом-ограничителем со значением, меньшим S. Также известны методы, в которых байты применяются в качестве единиц кодирования при выполнении кодирования Хаффмана, использующего либо восьмибитные символы для кодирования, либо семибитные символы с флагами [7]; а также методы, выполняющие частичную перестановку алфавита и не требующие полного отображения [6]. Кулпеппер и Моффат [6] также описали метод кодирования с синхронизацией по байтам, создающий множество кодовых слов на основе байтов, в которых первый байт уникальным образом определяет длину кодового слова. Аналогичным образом можно использовать полубайтовое кодирование, 4-битный аналог байт-синхронизированного подхода, при котором один бит резервируется для флага «ограничитель-продолжатель», а три остальных используются для хранения данных. | ||
'''Другие статические коды''' | '''Другие статические коды''' | ||
