4551
правка
Сжатие целочисленных последовательностей и множеств: различия между версиями
Материал из WEGA
Сжатие целочисленных последовательностей и множеств (посмотреть исходный код)
Версия от 12:05, 2 марта 2018
, 2 марта 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 74: | Строка 74: | ||
Более эффективный механизм применения байт-синхронизированных кодов был получен в результате наблюдения, заключающегося в том, что в качестве разделителя между ''байтом-ограничителем'' и ''байтом-продолжателем'' не обязательно должно использоваться принятое ранее число 128, и выбор подходящего числа определяет соответствующие компромиссные соотношения длин кодовых слов [3]. При использовании так называемого (S, C)-байт-синхронизированного подхода выбираются значения S и C, составляющие в сумме S + C = 256, так что каждое кодовое слово состоит из последовательности (пустой или непустой) байтов-продолжателей со значениями, большими или равными S, и заканчивается финальным байтом-ограничителем со значением, меньшим S. Также известны методы, в которых байты применяются в качестве единиц кодирования при выполнении кодирования Хаффмана, использующего либо восьмибитные символы для кодирования, либо семибитные символы с флагами [7]; а также методы, выполняющие частичную перестановку алфавита и не требующие полного отображения [6]. Кулпеппер и Моффат [6] также описали метод кодирования с синхронизацией по байтам, создающий множество кодовых слов на основе байтов, в которых первый байт уникальным образом определяет длину кодового слова. Аналогичным образом можно использовать полубайтовое кодирование, 4-битный аналог байт-синхронизированного подхода, при котором один бит резервируется для флага «ограничитель-продолжатель», а три остальных используются для хранения данных. | Более эффективный механизм применения байт-синхронизированных кодов был получен в результате наблюдения, заключающегося в том, что в качестве разделителя между ''байтом-ограничителем'' и ''байтом-продолжателем'' не обязательно должно использоваться принятое ранее число 128, и выбор подходящего числа определяет соответствующие компромиссные соотношения длин кодовых слов [3]. При использовании так называемого (S, C)-байт-синхронизированного подхода выбираются значения S и C, составляющие в сумме S + C = 256, так что каждое кодовое слово состоит из последовательности (пустой или непустой) байтов-продолжателей со значениями, большими или равными S, и заканчивается финальным байтом-ограничителем со значением, меньшим S. Также известны методы, в которых байты применяются в качестве единиц кодирования при выполнении кодирования Хаффмана, использующего либо восьмибитные символы для кодирования, либо семибитные символы с флагами [7]; а также методы, выполняющие частичную перестановку алфавита и не требующие полного отображения [6]. Кулпеппер и Моффат [6] также описали метод кодирования с синхронизацией по байтам, создающий множество кодовых слов на основе байтов, в которых первый байт уникальным образом определяет длину кодового слова. Аналогичным образом можно использовать полубайтовое кодирование, 4-битный аналог байт-синхронизированного подхода, при котором один бит резервируется для флага «ограничитель-продолжатель», а три остальных используются для хранения данных. | ||
'''Другие статические коды''' | '''Другие статические коды''' | ||
В литературе описан широкий спектр других вариантов кодирования. Некоторые из них настраивают кодировку за счет изменения границ блоков, определяющих код, и кодирования значения x в виде идентификатора унарного блока, за которым следует минимальное бинарное смещение в пределах обозначенного блока [15]. | |||
К примеру, гамма-код Элиаса можно рассматривать как унарно-бинарную комбинацию относительно вектора размеров блоков <math>\langle 2^0, 2^1, 2^2, 2^3, 2^4, ... \rangle</math>. Тейхола [15] предложил гибридный подход, в рамках которого выбирается параметр k, а вектор размеров блоков задается формулой <math>\langle 2^k, 2^{k+1}, 2^{k+2}, 2^{k + 3}, ... \rangle</math>. Одним из вариантов для параметра k является длина в битах медианы последовательности значений, так что первый бит каждого кодового слова делит диапазон наблюдаемых значений символов приблизительно пополам. Другой вариант описали Болди и Винья Vigna [2], которые использовали вектор <math>\langle 2k - l,(2^k - l)2^k, (2k - 1)2^{2k}, (2k - l)2^{3k} ,... \rangle</math> для получения семейства кодов, аналитически и эмпирически подходящих для случаев экспоненциального распределения вероятностей, в том числе связанных со сжатием веб-графов. При использовании этого метода значение k обычно принадлежит к диапазону от 2 до 4, а в суффиксной части используется минимальный двоичный код. | |||
Фенвик [8] представил детальный обзор широкого спектра методов статического кодирования. Чен и др. [4] также недавно рассматривали задачу кодирования сообщений над разреженными алфавитами. | |||
'''Контекстно-зависимый код''' | |||
