The Green Tree Of Compression Methods A Practical Introduction To Data Compression Русская версия 1.4 Практическое введение в сжатие информации Prolog ====== Что такое информация ? По самому популярному определению, любое взаимодействие между объектами, в процессе которого один приобретает некоторую субстанцию, а другой ее не теряет, называется информационным взаимодействием; при этом передаваемая субстанция называется информацией. Такую информацию, подпадающую под это определение, можно назвать "физически обусловленной". Но оно не учитывает физически НЕ-обусловленную, "абсолютную" информацию, никак не зависящую от материального мира. Простейший пример - таблица умножения, известная каждому с младенчества, но не потерявшая своей актуальности и поныне; информация о том, что сумма квадратов катетов равна квадрату гипотенузы, что отношение площади круга к площади квадрата со стороной, равной радиусу круга, - "пи", а длины окружности к ее радиусу - два "пи"... и т.д. Это именно абсолютная информация об объектах НЕматериального мира. Исчезнет материальный мир, а эта информация - вся останется. И таблица умножения, и все теоремы и формулы всех ветвей математики. Более сложный пример - последовательность чисел, кодирующая ДНК некоторого человека N, или последовательность чисел, полученная в результате оцифровки его фотографии. Эта информация, конечно, не имеет смысла вне материального мира, зато, в отличие от "хаотической" информации, получает смысл в материальном мире, и тем самым как бы "повышает статус" благодаря ему, проявляет те или иные "качества" и "стороны", "развивается" в нем. Только из-за него, только в физическом мире (и разных его моделях) "лучшая" часть информации становится "знанием" и даже "мудростью", а остальная так и остается непроявленным "хаосом". Таким образом, разница между аналоговой информацией и цифровой (физической, данные, data) - гораздо глубже и принципиальнее, чем может показаться изначально. Ответы ====== Question1: Как сжимают информацию ? На compression-pointers.com - сотни ссылок, а на act.by.net - сотни программ-компрессоров. Что в них, о чем они, все эти методы, стандарты, алгоритмы, программы ? Answer1: Все достаточно просто. Но сначала - несколько определений. БИТ - это "атом" цифровой информации: представим себе небольшой "ящик" где- то в пространстве-времени (в микросхеме, на магнитном/оптическом диске, линии связи) со всего лишь двумя возможными состояниями: полный (1, единица, да, истина, существует) и пустой (0, ноль, нет, ложь, не существует). Конечную последовательность битов назовем КОДОМ. БАЙТ (традиционный) - это последовательность восьми битов. N-битный (обобщенный) байт - последовательность N битов - имеет 2^N (два в степени N) возможных значений-состояний (таким образом, традиционный 8-битный байт может принимать 256 разных значений: 0,1,...,255) Конечную последовательность байтов назовем СЛОВОМ, а количество байт в слове - ДЛИНОЙ СЛОВА. В общем случае слово построено из N-битных байтов, а не 8-битных (таким образом, код - это слово из 1-битных байтов). Q2: Что же такое "символ", в таком случае ? Ведь именно это слово фигурирует в многочисленных международных патентах о методах и устройствах для сжатия информации? A2: СИМВОЛ - это "атом" некоторого языка (например, буква, цифра, нота). ASCII (American Standard Code for Information Interchange) ставит в соответствие каждому значению 8-битного байта символ. Но чтобы построить соответствие для всех символов из множества национальных алфавитов народов мира, необходимо больше: 16 бит на символ (стандарт UNICODE). И последнее определение: СЖАТИЕМ конечного объема цифровой информации (БЛОКА) называется такое его описание, при котором создаваемый СЖАТЫЙ блок содержит меньше битов, чем исходный, но по нему однозначно восстановим каждый бит исходного блока. Так называемое сжатие-с-потерями (lossy compression) - это два разных процесса (как правило, параллельных): (1) выделение сохраняемой части из блоков информации - создание модели, зависящей от цели сжатия и особенностей Источника и Приемника информации, по возможности улучшающей (данные для) (2) собственно сжатие (lossless compression). При измерении физических параметров (яркость, частота, амплитуда, сила тока и т.д.) неточности неизбежны, поэтому "округление" вполне допустимо. Q3: Чем отличаются эти определения от ныне существующих ? A3: С незапамятных времен, когда 8-битных процессоров было больше, чем 16-битных, а в UNICODE не было необходимости, под символом чаще всего подразумевают байт, а под байтом - последовательность восьми битов. Последовательность двух байтов компьютерный мир называет словом (WORD), а четырех - двойным словом (DWORD). Очень многие процессоры (остальные, не x86-совместимые) устроены так, что в каждой адресуемой ячейке памяти лежит 16-, 24- или 32-битный байт, а вовсе не 8-битный, как во всех IBM-совместимых ПК. Если "сжатый" блок длиннее исходного - то это перекодирование, но не сжатие по определению, вопреки "мнению" многих сжимающих программ (паковщики, компрессоры, архиваторы), увеличивающих длину на 1...5%, а не на один бит в "худшем случае" несжимаемых данных. Если сжатие-с-потерями не содержит функций истинного сжатия, то это удаление информации, несущественной для заданной цели, в рамках принятой модели. Впрочем, определений понятий "сжатие" и особенно "код" существует столько, что недоразумений возникает куда больше, чем хотелось бы. Теперь, с такими четкими определениями, кажется достаточно очевидным следующее: A) Каждый из методов сжатия хорош ИЛИ для сжатия блоков битов, ИЛИ блоков байтов, ИЛИ блоков слов, - потому что это очень разные объекты. Можно задать четкие математические определения для этих трех базовых видов цифровой информации, но ясно и без формул: сжимая заданный блок, метод сжатия предполагает о нем одно из трех: (1) вероятности битов различны; (2) вероятности появления байтов различны; (3) вероятности разных слов неодинаковы. B) Заданный блок сожмется лучше, если известна его структура: или это блок слов из N-битных байтов, или же это блок N-битных байтов, или блок битов. А также, разумеется, если известен "ответ": как, по каким закономерностям блок был создан, какой длины были записи-байты, как они формировались. Иначе говоря, чем точнее процесс сжатия учитывает процесс создания блока, тем лучше сжатие. А создаваемые блоки принадлежат, как правило, одному из этих трех базовых видов: биты, байты, слова. Можно добавить и ещё два "граничных" вида: нулевой - "хаос" (невозможно обнаружить никаких закономерностей - ни для битов, ни для байтов или слов) и четвертый - "тексты" (последовательности слов) появляются по некоторому правилу. Например, блок содержит русские предложения, английские, и тексты функций на языке C. Другие виды - например, смесь хаоса и байтов, или битов и слов - встречаются существенно реже. C) В каждом из трех случаев возможны два варианта: вероятности элементов (битов (1), байтов (2), слов (3)) различны, и а) не зависят от предшествующих и последующих, то есть "контекста" ("источник Бернулли"); б) сильно зависят от контекста ("источник Маркова"). Промежуточные случаи практически столь редки, что ими можно пренебречь (например, иногда зависят, иногда нет; зависят, но не все; зависят, но не от всего контекста, а от избранных его элементов...) Видно, что случай 2б (вероятности байтов различны и зависят от контекста) идентичен случаю 3 (вероятности слов различны), а вот 1б и 2 - не идентичны (простейший пример - сжатые данные, файлы .zip, .gif, .jpg и т.д.). Связано это с тем, что по определению конечная последовательность байтов - это слово, а битов - код, а не байт. Иначе говоря, байт- это запись фиксированной длины, а слово- произвольной. D) Для упрощения структуры данных и улучшения сжатия, сжимая блоки слов, лучше создавать блоки байтов и/или битов, сжимая блоки байтов - создавать блоки битов, и только сжимая блоки битов - конечный сжатый блок, несжимаемый "хаос". По некоторым причинам, большинство современных программ-компрессоров просто пропускают третий этап (сжатие блоков битов), или "склеивают" его со вторым (сжатие блоков байтов), начиная процесс с предположения, что задан блок слов. И только архиваторы с опциями для мультимедийного сжатия проверяют - а не блок ли это байтов. Поэтому принято говорить в терминах "первичного" и "вторичного" сжатия: сначала - моделирование или сортировка (тасование байтов), затем - encoding (дожатие) байтов в коды. Например, как справедливо пишут в учебниках для школьников, все первые архиваторы, ARC, ARJ, LHA, PAK, ZIP и т.д, использовали LZ77 или LZ78 с последующим дожатием методом Хаффмана или Шеннона-Фэно. Q4: Что же это за причины? A4: Во-первых, большинство "природных" данных, появляющихся в компьютерах с устройств ввода (клавиатура, сканер, микрофон, видеокамера...) - это действительно блоки слов (в общем случае - слова из не-8-битных байтов: современные графические устройства оперируют 24- или 32-битными байтами - "пикселами", а аудио - 8- , 16- или 32-битными "сэмплами"). Также и исполнимый код для процессора (файлы .exe , .dll и т.д.) - блоки слов. Блоки байтов и битов появляются, как правило, лишь при компьютерной обработке этих "природных" данных. Таким образом, основная задача сжимающего алгоритма - выяснить, как были построены слова блока, по каким правилам - закономерностям. Именно "первичный" алгоритм играет решающую роль в достижении приемлемого качества сжатия, близкого к мировому рекорду (см. например http://act.by.net ). Во-вторых, компьютерам гораздо легче оперировать с байтами, чем с битами. Каждый байт имеет свой адрес в памяти, каждый адрес указывает на один байт (8-битный, если это обычный IBM-совместимый компьютер). Всего лишь 20 лет назад появились первые 16-битные процессоры, способные обрабатывать больше 8-и битов одной инструкцией. В-третьих, известных алгоритмов для сжатия блоков битов практически нет (по первым двум причинам). Прекрасные результаты дают правильно выбранные первичный и вторичный алгоритмы, а третий шаг занимает много времени, но мало улучшает качество сжатия. Более 10 лет назад, когда разрабатывался "универсальный" формат .zip, почти все тексты были блоками 8-битных ASCII символов, исполнимые модули - для 16- или 8-битных процессоров, а большинство мультимедийных файлов - графических и звуковых - блоки 8- или 4-битных байтов. Поэтому вполне достаточно было иметь один алгоритм для всех данных: и слов (тексты, исполнимые модули), и 8-битных байтов (мультимедийные данные). С тех пор было создано много специальных алгоритмов для конкретных типов данных, но мало универсальных программ, дающих результаты, близкие к мировым рекордам, на всех типах данных (RK, UHArc, RAR, ACE, ERI). Q5: Какие-нибудь еще способы классификации данных ? A5: Безусловно, их существует множество. Выше изложен лишь самый актуальный. Можно еще упомянуть: - Одномерные данные, двумерные (например, картинки), трехмерные (видео, объемные образы) и так далее. Известно, что не-одномерных в настоящее время - вообще - менее десяти процентов (от общего числа файлов), а в частности - вероятность встретить их в наборе "неизвестные данные" - менее процента (их, как правило, хранят отдельно и обрабатывают специальными алгоритмами). Но в этом случае (выяснено, что данные - неодномерны) будет сразу решен более важный вопрос - биты ли это, байты или слова: байты с вероятностью более 0.999. - Так называемые "textual" и "binary" data. Классическая классификация. По нашим определениям: первое - блоки слов, второе - все остальное, в том числе всевозможные смеси "живая и мертвая вода в одном флаконе" (то есть файле). - Классификация по расширениям (.ARC,.AVI,.BMP и т.д.). Это путь для тех, кто намерен создавать коммерческие архиваторы и потом при каждом запуске сорить в монитор в стиле "!!You MUST REGISTER after a 30 days test period. Please read ORDER.TXT!!!". (Людям, знающим методы сжатия семейств PPM и BlockSorting, может казаться, что существуют order-1, order-2, order-3 и т.д. типы данных). Q6: Какие методы сжатия известны сейчас? A6: Для блоков слов или байтов: LZ77, LZ78, LZW (Lempel-Ziv-Welch) и много других вариантов "скользящего окна"; сортировка заданного блока - BlockSorting: полная (BWT, Burrows-Wheeler Transform) и частичная (по последним P символам), а также по параллельному блоку; PPM (prediction by partial match), Марковы и другие моделирования; для байтов - MTF (move to front), методы Хаффмана и Шеннона-Фэно, ЭОМО (Экспоненты-Отдельно-Мантиссы-Отдельно), LPC (Linear Prediction Coding) и его простейший вариант - Delta Coding (compute/code differences between neighboring bytes), Distance Coding (compute/code distances between equal values), он же Homala Benesa (how many larger (bytes) before next same (byte)); для байтов или битов - RLE, арифметическое кодирование со всеми модификациями (range coder, ELS - entropy logarithmic scale и т.д.), ERI93, ENUC (enumerative coding). Это только основные семейства (ветви из трех главных ветвей дерева) методов. В каждом семействе - множество методов, у каждого метода - множество вариантов, у каждого варианта - свои параметры. Q7: Но ведь их обычно комбинируют ? A7: Как показывает практика, к блокам слов полезно на первом этапе применять один или несколько алгоритмов из первой группы: в простейшем случае - один, в лучшем - выбирая между ними один раз, перед началом сжатия блока, a в совсем лучшем - синтезируя их внутри блока (особенно полезен синтез LZ + BlockSorting). На втором этапе - алгоритмы из второй группы, на третьем - из третьей. В случае блока байтов первый, самый сложный этап, лучше пропустить, а в случае блока битов лучше сразу перейти к третьему этапу, пропустив первые два. Незачем применять методы для слов - к битам или байтам ("удачный" пример - PNG), а алгоритмы для байтов - к битам или словам (старейшие компрессоры: метод Хаффмана, единственный известный в те времена, применяется ко всем типам данных, вопроса об их структуре попросту не возникает: есть один метод, выбирать не из чего). Но не стоит совсем забывать и о "неправильных", "непрактичных" данных: например, несомненно, возможны такие блоки слов, к которым лучше применять RLE, и лишь затем - другие методы (RLE к словам: каждое слово записано N раз, N>1). Или такие блоки битов, к которым лучше применять PPM (плохо сжатые данные - .ZIP, .MP3, .GIF, .JPG, .PNG и т.д.) Q8: Что можно сказать о статическом и динамическом кодировании ? A8: В те далекие времена, когда компьютеры были большими, а файлы - маленькими, проблемы выделения в заданном файле логически разных фрагментов- не возникало. Во-первых, относительно меньше было файлов с разнородными данными, да и самих типов данных было поменьше: размерность байтов редко достигала даже 24-х, и тем более 32-х или 64-х (4-канальный звук с 16-битным качеством). Во-вторых, сами логически разные подфрагменты были столь малы, что издержки на описание границ подфрагментов были сравнимы с выигрышем в случае их использования. На запись нового бинарного дерева (методы Хаффмана или Шеннона-Фэно; 8-битные байты) требуется порядка ста байтов, к тому же сложность и время работы метода могут увеличиться почти вдвое - поэтому обращать внимание на фрагменты короче килобайта не имеет смысла. Тем более, если средний размер файла - сто килобайт, а вероятность того, что записи в нем совершенно разные - менее процента. Сейчас с этим иначе: и средний размер в десяток раз больше, и вероятность разнородности фрагментов файла - примерно во столько же. Теоретически любой алгоритм сжатия можно сделать как "совсем статическим" (все параметры жестко заданы изначально) так и "совсем динамическим" (все параметры периодически перевычисляются). Но практически, произнося слова "статический или динамический", имеют в виду самый первый алгоритм, описанный Хаффманом в 1952-м году. Q9: Как выяснить, содержит ли заданный файл блок битов, байтов или слов? A9: Это один из самых интересных и важных вопросов. Из отчетов на http://i.am/artest и i.am/ACT видно, что неверная трактовка блока приводит к сжатию в 1.5-2 раза хуже (pkzip 183%, IMP 147%, PNG 140% ... BMF 100%). В основном, в файлах лежат блоки слов, из 8-ми или 16-битных байтов, а "мультимедийные" (аудио-, видео-, графические) файлы - блоки 8-, 16-, 24- или 32-битных байтов. Поэтому самый простой способ - посмотреть расширение файла, или заголовок, или, протестировав несколько килобайт, выбрать метод, лучший на этом фрагменте. Незачем применять алгоритмы, хорошие для блоков слов, к байтам или битам, а созданные для сжатия байтов- к битам или словам. Q10: Есть ли другие методы, кроме этого, простейшего ? A10: Следующий способ сложнее и занимает больше времени. Допустим, у нас есть алгоритм, вычисляющий некоторую "меру упорядоченности" (м.у.) заданного блока слов, возвращающий значение от нуля (полный хаос, все слова разные) до единицы (полный порядок, все слова одинаковые), а также аналогичный алгоритм, вычисляющий м.у. заданного блока байтов, и алгоритм для м.у. блока битов. Тогда, предположив, что заданный блок - слова, применим к нему первый алгоритм, и вычислим первую величину - W, затем предположим, что в блоке - байты, и получим второе значение - Y, и наконец, вычислим третью меру B, применив третий алгоритм. Сравнивая полученные три числа W,Y,B (их значения лежат в интервале от нуля до единицы), легко видим, чему больше соответствует изучаемый блок. Если же допустим, что байт может быть еще и 16- или 32-битным, необходимо вычислять три величины для байтов и три - для слов, то есть всего - семь. Q11: Похоже, все три алгоритма действуют примерно одинаково, но с разными элементами - битами, байтами и словами ? A11: Именно так. В простейшем случае, если элементы - биты, и алгоритм предварительно разбивает заданный блок битов на логически разные фрагменты (то есть, к примеру, случай "сто нулей, затем сто единиц", рассматривается как два "хороших", а не как один "плохой"): B= ( |n[1] - N/2| + |n[0] - N/2| ) / N где N - число битов в блоке, n[1] - число единиц, n[0] - число нулей. Легко видно, что B=0, если n[1]=n[0]=N/2 ; B=1, если n[1]=N или n[0]=N . Аналогичный тривиальный пример для случая 8-битных байтов: Y = ( |n[255]-N/256| + ... + |n[0]-N/256| ) * 128 / (N*255) Y=0 если n[255]=...=n[0]=N/256; Y=1 если n[255]=N или n[254]=N...или n[0]=N. Q12: Довольно просто для битов и байтов, но как быть со словами, ведь их длина 3,4,...,L , а L - порядка десяти, а сами слова могут быть составлены из 8-, 16- или 32-битных байтов ? A12: Как в любом исследовании: идеи, допущения, моделирование, тестирование, оптимизация... Поиск более эффективного алгоритма - процесс увлекательный и даже азартный. Будущее искусства сжатия информации предсказуемо, а успех - всегда близок. Новые нерешенные задачи о сжатии будут появляться и через 50, и через 100 лет после написания этих строк, и новые алгоритмы будут разрабатываться для их оптимального решения. Во-первых, 8-битные элементы скоро станут так же редки, как 16-битные лет пятнадцать-двадцать назад. Во-вторых, современные компьютеры ограничены одномерной и не ассоциативной (not content-addressable) памятью. Хотя некоторые процессоры и могут трактовать память как двухмерную, они относительно редки и новы. Наконец, если мы посмотрим на определение сжатия, увидим, что в нем нет никаких ограничений на то, каким должно быть сжимающее описание. Оно может ссылаться на все, что приемнику сжатого блока всегда будет доступно. Но когда эта внешняя используемая информация недоступна, сжатый блок правильно разжать не удастся. Таким образом, если мы только предполагаем, что все, что использовалось при сжатии-описании, будет доступно при разжатии, но не знаем этого точно, получается "потенциально потерьное" сжатие. ТОлько нефизическая информация всегда доступна, она никак не зависит от материальных объектов (см. Пролог). Объем ее бесконечен. И когда мы изучаем, как она может быть применена (вейвлеты, фракталы, например) - на самом деле мы изучаем, как мы от нее зависим. Epilog ====== RHLAOC ~~~~~~ HLAO http://www.faqs.org/faqs/compression-faq/part2/ HL http://www.cs.sfu.ca/CC/365/li/squeeze/ O http://www.data-compression.com/theory.html HL http://www.data-compression.com/lossless.html RHL-O- http://www.dspguide.com/datacomp.htm RH- http://www.go2net.com/internet/deep/1997/01/01/ RHL http://www.ganssle.com/articles/acompres.htm RHLAO http://www.newmediarepublic.com/dvideo/compression/adv04.html H O- http://www.rdrop.com/~cary/html/data_compression.html RHLAO- http://www.arturocampos.com/cp_ch1.html RHLA- http://w3.antd.nist.gov/cag/lecser_ay1/lecser_ay1.html RH- - http://www.ccs.neu.edu/groups/honors-program/freshsem/19951996/jnl22/jeff.html RHLAO http://www.ece.umn.edu/users/kieffer/ece5585.html RHLAO- http://www.ics.uci.edu/~dan/pubs/DataCompression.html RHL-O http://www.ils.unc.edu/~willc/dcfulltext.html L O http://www.cs.pdx.edu/~idr/unbzip2.cgi?compression/acb_compress.html.bz2 R-L-O http://cswww.willamette.edu/~sarnold/cs443/compression.html RHLAO- http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html RHLA http://vectorsite.tripod.com/ttdcmp1.html R L O http://members.aol.com/breunling/obcompr.htm RHLAO- http://www.rasip.fer.hr/research/compress/algorithms/index.html HLA - http://www.ifi.uio.no/~ftp/publications/cand-scient-theses/SHuseby/html/node41.html RHLAO http://www.cs.su.oz.au/~symvonis/teaching/cs4-data-compression.html -L- - http://www.image.cityu.edu.hk/~loben/thesis/node22.html L O http://home.uleth.ca/~borrtj/pres/index.htm RHL-O- http://www.scit.wlv.ac.uk/~c9581158/main.html RHLA - http://www.eee.bham.ac.uk/WoolleySI/All7/body0.htm RHLAO- http://wannabe.guru.org/alg/node163.html R - страница содержит описание Run Length Encoding H - описание Huffman Coding L - Lempel-Ziv A - Arithmetic Coding O - (хоть несколько слов про) другие методы C - попытки классификации типов данных и/или методов сжатия К сожалению, ни в одном из этих введений/обзоров не найдено полезной информации - о классификации данных; - о классификации методов сжатия, "дереве" методов; - о том, какие методы сжатия к каким данным применять, то есть ответа на один из важнейших вопросов: **************************************************************************** * How to choose the most appropriate algorithm, * * having nothing but the data itself ? * *Как выбрать самый подходящий алгоритм сжатия блока, имея лишь сами данные?* *Ведь методов сжатия - все больше и больше с каждым днем! * **************************************************************************** Этот текст, English (ver.1.4) лежит на http://geocities.com/eri32/int.htm Russian (ver.1.4) на http://geocities.com/eri32/intro.htm With best kind regards, A.Ratushnyak, http://i.am/artest go Back to main ARTest page
