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