Я ищу алгоритм сжатия, который работает с символами меньше байта. Я быстро исследовал алгоритмы сжатия, и трудно определить размер используемых символов. Во всяком случае, есть потоки с символами меньше 8 бит. Есть ли параметр DEFLATE для определения размера его символов?Алгоритмы сжатия с малыми словарями
открытого текста символы меньшие чем байт
Оригинальные описания LZ77 и LZ78 описывают их в терминах последовательности десятичных цифр (символов, которые приблизительно в два раза меньше байта).
Если вы используете Google для «алгоритма сжатия ДНК», вы можете получить кучу информации об алгоритмах, специализированных для файлов сжатия, которые почти полностью состоят из 4 букв AGCT, словаря из 4 символов, каждый из которых содержит около 1/4 как байт. Возможно, один из этих алгоритмов может работать для вас с относительно небольшой настройкой.
Сжатие в стиле LZ77, используемое в LZMA, может показаться использующим два байта на символ для первых нескольких символов, которые он сжимает. Но после сжатия нескольких сотен символов открытого текста (буквы текста на естественном языке или последовательности десятичных цифр или последовательности из четырех букв, которые представляют базы ДНК и т. Д.), Двухбайтовые сжатые «куски», которые LZMA часто выступает в виде десятков или более символов открытого текста. (Я подозреваю, что то же самое верно для всех подобных алгоритмов, таких как алгоритм LZ77, используемый в DEFLATE).
Если в ваших файлах используется только ограниченный алфавит, который намного меньше всех 256 возможных значений байта, в принципе программист может адаптировать вариант DEFLATE (или какой-либо другой алгоритм), который мог бы использовать информацию об этом алфавите для создания сжатые файлы на несколько бит меньше по размеру, чем те же файлы, сжатые стандартным DEFLATE. Однако многие байт-ориентированные алгоритмы сжатия текста - LZ77, LZW, LZMA, DEFLATE и т. Д. Создают словарь общих длинных строк и могут давать производительность сжатия (с достаточно большим исходным файлом) в пределах нескольких процентов от того, адаптированный вариант - часто преимущества использования стандартного формата сжатого файла могут принести в жертву несколько процентов потенциальной экономии пространства.
сжатых символов меньше, чем байт
Многие алгоритмы сжатия, в том числе те, которые дают наиболее известный сжатие контрольных файлов, вывод сжатой информации бит за битом (например, большая часть PAQ серии компрессоров , а также некоторые типы арифметических кодеров), в то время как другие выводят сжатую информацию переменной длины без учета границ байтов (например, сжатие Хаффмана).
Некоторые способы описания арифметического кодирования говорят о фрагментах информации, таких как отдельные биты или пиксели, которые сжимаются до «менее одного бита информации».
EDIT: «Аргумент подсчета» объясняет, почему невозможно сжать все возможные байты, а тем более все возможные байты и несколько общих последовательностей байтов, в кодовые слова, длина которых меньше 8 бит. Тем не менее, несколько алгоритмов сжатия могут и часто представляют собой некоторые байты или (реже) некоторые последовательности байтов, каждый с кодовым словом, длиной менее 8 бит, путем «жертвования» или «ускользания» менее общих байтов, которые заканчиваются представленный другими кодовыми словами, которые (включая «escape») имеют длину более 8 бит.
Такие алгоритмы включают в себя:
Алгоритм Пайка использует 4 бита «01 01 "для представления 'e' (или в некоторых контекстах« E »), 8 бит« 0000 0001 »для представления слова« the »(4 байта, включая пробел перед ним) (или в некоторых контекстах« The »или «THE») и т. Д. В нем есть небольшой словарь примерно из 200 наиболее часто встречающихся английских слов, , включая суб-словарь из 16 чрезвычайно распространенных английских слов.
При сжатии английского текста с байтовым ориентированным кодированием Хаффмана последовательность «e» (пробел) сжимается до двух кодовых слов с общим количеством 6 бит.
Увы, когда задействовано кодирование Хаффмана, я не могу сказать вам точный размер этих «маленьких» кодовых слов или даже точно указать, что такое последовательность байтов или байтов, которое представляет небольшое кодовое слово, потому что оно различно для каждого файла , Часто одно и то же ключевое слово представляет собой другой байт (или другую последовательность байтов) в разных местах одного и того же файла. Декодер определяет, какая последовательность байтов или байтов представляет собой кодовое слово, основанную на подсказках, оставленных компрессором в заголовках, и на данных, которые были распакованы до сих пор. С кодированием диапазона или арифметическим кодированием «кодовое слово» может даже не быть целым числом бит.
Возможно, вы захотите изучить Golomb-Code. В коде golomb используется алгоритм разделения и покорения для сжатия inout. Это не сжатие словаря, но стоит упомянуть.
Не могли бы вы просто сделать весь словарь одним объектом и просто сжать его как более крупный объект? не уверен, что вы будете получать много сжатия (если есть), если вы делаете байт по байтам. – soandos
Я не собираюсь сжимать байт байтом. Я просто хочу использовать символы меньше одного байта для сжатия последовательностей байтов. Кажется, что DEFLATE использует как минимум два байта на символ. –
Почему вы хотите использовать символы «меньше одного байта», а не то, что использует DEFLATE? Есть ли какое-то преимущество, которое я здесь отсутствует? –