Short version of this article was published in spring 2001 in the popular Russian "Hard'n'Soft" magazine. It's of historical interest only after the "Data Compression Methods" book is published.Мультимедийной информацией (ММИ) называют, как правило, звук (поток audio), двумерные картинки, video (поток двумерных картинок), трехмерные образы. В течение века не менее актуальными станут и другие виды - поток трехмерных образов, поток запахов. В чем отличия ММИ от других видов информации ? 1) ИСТОЧНИК ее - приборы, измеряющие параметры физического мира. С некоторой натяжкой любую информацию, получаемую цифровым устройством из физического мира через измерительные (оцифровывающие) устройства, можно назвать ММИ (например, сила тока, скорость движения, направление ветра). Процесс называют аналого-цифровым преобразованием (АЦП) или "оцифровкой" (обратный процесс - цифро-аналоговое преобразование - ЦАП). Результат процесса оцифровки - мультимедийные данные (ММД), форма ММИ. Неизбежны неточности при измерении, и допустимо "округление" в нужную сторону, в том числе такое, в результате которого сжатие будет лучше. Если же известно, что ПРИЕМНИК заданного блока ММД - органы чувств человека (в первую очередь глаза или уши), то можно "округлять" с учетом их свойств. Можно учитывать и особенности канала связи, по которому будут передаваться оцифрованные ММД (медные провода, кварцевое оптоволокно, воздух, вода...) 2) РАЗМЕРНОСТЬ. Для хранения числа-результата каждого измерения обычно используется от 4-х битов (16 значений) до 32-х (2 в 32-й степени =4 с лишним миллиарда), но как правило,- 16, 24 или 32. То есть размерность байта R=16, 24 или 32, а не 8, как в большинстве других случаев: исполнимый код для процессоров семейства x86, восьмибитный ASCII-текст, базы данных (16-битный UNICODE-текст и исполнимый код для других процессоров в целом менее актуальны в настоящее время). Причем блок ММД состоит исключительно из байтов одной размерности R, в отличие от баз данных, кода для x86 и т.д. 3) ЛИНЕЙНОСТЬ. Измерения проводятся через равные интервалы времени (поток звука - audio, поток картинок - video, и др.) и через равные расстояния в пространстве (двумерные картинки, трехмерные образы...) Байты-значения измерений записываются в блок ММД последовательно. Иногда при записи ММД в блоки их периодически "выравнивают", чтобы расстояние от начала блока до границы выравниваемого фрагмента удовлетворяло некоторому критерию. Например, в .BMP-картинках каждая новая строка изображения должна начинаться с адреса, кратного четырем, а в .RAS-файлах - кратного двум. Но байты, лежащие между фрагментами, не несут полезной информации о блоке ММД. Если же все-таки несут, то это уже блок обработанных ММД (ОММД), и процесс его сжатия должен ориентироваться на вид этой обработки, иначе сжатие будет существенно хуже, чем в случае учета обработки. За исключением случаев "палитризованных" картинок и иных блоков ОММД, каждое значение байта _линейно_ зависит _только_ от значений соседних в пространстве-времени байтов. В случае текста оно зависит еще и от языка (русский, английский, китайский...) и типа файла (DOS текст, Unix текст, текст на Си, на HTML). В случае исполнимого кода - от типа процессора и компилятора. И алгоритмы сжатия/расжатия должны либо заранее знать особенности обрабатываемых блоков, либо описывать-передавать-получать-использовать эти особенности в процессе работы. В случае ММД таких осложнений нет: свойства физического мира всегда одинаковы. 4) КАНАЛЫ. Три первых пункта описывают блок одноканальных ММД. Как правило, блок ММД содержит информацию о нескольких каналах ММД. Например, в случае стерео звука это два канала - левый и правый. А в случае картинки можно считать каналом либо каждую строку, либо каждый столбец цифрового изображения. Или же вовсе не трактовать столбцы или строки как разные каналы, а просто считать, что окрестность каждого байта - двумерная, а не одномерная. Тем более что, во-первых, если двумерная картинка описывает поверхность трехмерного объекта (допустим, шара), то длины каналов будут разными, а их выбор проблематичным. Во-вторых, каждый квант изображения (точка, пиксел) обычно состоит из нескольких компонент: например, RGB - яркость красного (red), зеленого (green), синего (blue); HSB - тон цвета (hue), насыщенность (saturation) и яркость (brightness). Эти компоненты тоже можно считать разными каналами, и, как правило, именно это удобнее, так как их обычно 2, 3 или 4, а не столько, сколько строк или столбцов (от десятков до тысяч). В общем случае, если блок ММД описывает N каналов, то либо он состоит из N фрагментов длиной X байт, либо из X фрагментов по N байт. То есть N каналов идут либо последовательно, либо параллельно. Это и будет определением канала. Содержимое (множество байтов) каждого канала зависит либо от всех остальных каналов (RGB, HSB и т.д.), либо только от соседних (строки, столбцы). Вот, собственно, и все. Первый пункт будем далее считать определением ММД, а отклонения от свойств 2, 3 или 4 - особыми случаями ММД. Как использовать эти четыре особенности ММД для их сжатия ? Несколько слов о сжатии вообще. Надеюсь, читатель знаком с основными понятиями и идеями сжатия (описания, устраняющего избыточность) информации, изложенными в [1]. Существует два подхода к сжатию - беспотерьное сжатие (lossless), и сжатие с потерями (lossy). Именно второй применяют при сжатии ММД чаще, из-за особенностей Источника и Приемника. Теоретически любой "потерьный" алгоритм можно сделать "беспотерьным", но чаще всего такой искусственно переориентированный алгоритм оказывается намного менее эффективным, чем алгоритмы, идущие к той же цели другими путями, и изначально ориентированные на lossless - сжатие без потерь. С другой стороны, блоки/потоки данных любого типа .ABZ можно сжимать с "потерями" (возможно, даже улучшающими содержимое с точки зрения Приемника) алгоритмом, специально "заточенным" под данные этого типа .ABZ (например, DocumentPress Игоря Павлова[22], оптимизация таблиц в заголовках EXE-файлов). Базовых же стратегий сжатия три: 1) "Окно-Словарь" (Трансформация Потока). Описание поступающих данных на основании уже имеющихся. Например, LZ-методы для потоков/блоков слов, т.е. когда комбинации поступающих байтов предсказуемы по уже обработанным комбинациям. Преобразование по таблице, RLE, LPC, DC, MTF, SEM, Subband Coding - для байтов, т.е. когда не имеет смысла рассматривать комбинации длиной два и более байта (или "запоминать" эти комбинации, в случае Linear Prediction Coding). Никаких вероятностей, в отличие от второго случая, не вычисляется. В результате трансформации формируются, как правило, несколько потоков (за исключением LZ78, LZW и т.п.) Даже если суммарный объем потоков увеличивается, их структура улучшается, и последующее сжатие идет проще, быстрее и лучше. 2) Статистика. а) Адаптивная (поточная). Вычисление вероятностей для поступающих данных на основании статистики по уже обработанным. Кодирование с использованием этих вычисленных вероятностей. Например, семейство PPM-методов[2] -для слов, адаптивные Huffman, Shannon-Fano, Арифметическое Кодирование - для байтов. В отличие от первого случая, давно собраная статистика имеет тот же вес, что и недавняя, если алгоритм не борется с этим специально. Кроме того, считаются вероятными все комбинации, в том числе те, что еще не встречались в потоке, и, скорее всего, никогда не встретятся. б) Блочная. Отдельно кодируется и добавляется к сжатому блоку его статистика. Статические Huffman/Shannon-Fano и Arithmetic для байтов. Статический (pre-conditioned) PPM для слов[9]. 3) Трансформация Блока. Входящие данные разбиваются на блоки, которые затем трансформируются целиком (а в случае однородных данных лучше брать весь блок, который требуется сжать). BlockSorting-методы, в том числе BWT[3], здесь же Fourier Transform, Discrete Cosine Transform, Discrete Wavelet Transform, фрактальные преобразования, Enumerative Coding. Как и в первом случае, в результате могут формироваться несколько блоков, а не один. Опять же, даже если суммарная длина блоков не уменьшается, их структура значительно улучшается, и последующее сжатие происходит проще, быстрее и лучше. Одним предложением: алгоритм сжатия может быть или статистическим, или трансформирующим, и обрабатывать данные либо поточно, либо блоками, причем чем больше и однороднее данные и память, тем эффективнее блочные алгоритмы; чем меньше и неоднороднее данные и память, тем эффективней поточные методы; чем сложнее Источник, тем сильнее улучшит сжатие оптимальная трансформация, чем проще Источник, тем эффективней прямолинейное статистическое решение "в лоб" (так называемые источники Бернулли и Маркова). Комплексные, более совершенные алгоритмы сжатия будут синтезировать все стратегии, но пока таких нет, и базовых стратегий - три. Все ныне существующие компрессоры используют для блоков слов либо метод из семейства LZ, либо из семейства BlockSorting, либо из PPM, но никак не синтез всех трех или хотя бы двух стратегий (см. например [4], а также [5] и [6]). Впрочем, некоторые синтезирующие алгоритмы существуют давно. Во-первых, успешно совмещают поточную и блочную стратегии фавориты интернета MP3, MPEG и JPEG (о них написаны тысячи научных и популярных статей, в том числе о дискретном косинусном преобразовании, главном из используемых ими алгоритмов, поэтому дальше о них речи не пойдет - см. [7] и [8]). Во-вторых, правильный компрессор последовательно применяет три-четыре алгоритма (препроцессинг-фильтрация, сжатие слов, затем байтов, наконец битов), и последний из них, как правило, статистический, хотя первые два-три могут быть и трансформирующими. Из-за наличия у ММД характерных свойств - линейность, размерность, каналы - трансформации улучшают сжатие практически всегда. Далее, ММД поступают, как правило, достаточно большими и однородными блоками, да и памяти доступно все больше. Поэтому более эффективные кодеки (пара компрессор плюс декомпрессор) первичным методом, применяемым к истинным ММД и определяющим эффективность всего процесса (вторичные алгоритмы работают с ОММД), используют один из методов третьей стратегии (Трансформация Блоков). Какие существуют трансформации ? 1. RLE, Run Length Encoding, Кодирование Длин Повторов. Самый тривиальный способ сжатия. Использующий меньше всего памяти и времени. Компрессор находит повторы одинаковых элементов Z и замещает их набором { элемент Z, флаг повтора, число элементов в повторе N }. Остальные же элементы попросту копируются из входного потока в выходной. Если памяти доступно больше, чем несколько байт, вместо флага повтора можно записывать расстояние до следующего повтора. Как и всякий поточный метод, RLE применим и к блокам данных. Вообще блочные методы отличаются лишь тем, что не могут работать, пока не задана длина буфера с данными. Остальное же - их свойства, а не признаки: - чем меньше размер блока, тем менее эффективен блочный метод (поточным методам это свойство присуще в меньшей степени); - всякий элемент блока преобразуется одинаковым образом, независимо от его расстояния до начала и конца блока (это свойственно и многим поточным методам, например SEM и Delta Coding); - почти все блочные методы являются двухпроходными (LZ77 и т.п. намного эффективнее с двумя проходами "поиск слов" и "анализ и преобразование", например flexible parsing [18], [19]). Если предполагается дальнейшее сжатие выхода RLE, то можно создавать четыре выходных потока/блока: длины повторов N[i]; элементы повторов Z[i]; длины остальных фрагментов, в которых повторов не найдено, R[i]; остальные фрагменты OF[i]. Может оказаться, что сжатие улучшится, если первые элементы остальных фрагментов (элементы, "обрывающие" повторы) записывать в отдельный пятый поток/блок, а последние элементы OF - в шестой. Основные принципы сжатия информации видны уже на этом самом тривиальном примере. Остается упомянуть, что RLE - частный случай "скользящего окна", словарных методов типа LZ*, когда размер этого окна-словаря равен единице, то есть ссылка-смещение может быть только на один элемент назад, а длина - любой. RLE эффективнее на ММД с маленькой размерностью R, от 1 до 8 битов. Чем больше размерность R байтов ММД, тем менее вероятно, что применение RLE к этим ММД улучшит сжатие. 2. SEM (Separate Exponents and Mantissas). Отделение мантиссы числа от экспоненты. Большое семейство методов, называемое обычно Integer Coding[10], включающее структурную модель Фенвика, Rice codes [11], Fibonacci codes, Golomb codes[12], Elias Gamma и Delta codes[13] и много других, более сложных вариантов, например DAKX[14]. А в простейшем случае создается два потока: старшие N битов, младшие (R-N) битов. Очевидно, что первый поток - старшие биты (Most Significant Bits) при правильном выборе N сжимается, как правило, лучше, особенно в случае ММД. Но еще эффективнее разделение числа на экспоненту (номер старшего ненулевого бита B) и мантиссу (остальные биты, младше B). Первый поток получается байтовым, второй - битовым. Можно и дальше разделять получающиеся потоки, особенно первый. SEM часто применяется при сжатии ММД, в сочетании с другими методами, а в алгоритмах сжатия с потерями SEM присутствует обязательно. 3. MTF (Move To Front, Сдвиг К Вершине) и DC (Distance Coding, Кодирование Расстояний) хорошо описаны в BWT-FAQ-e Вадима Юкина [3]. Добавить можно лишь то, чего я пока не видел в описаниях этих методов. MTF в общем случае использует скользящее окно длиной N элементов, а не один, как в обычном, всегда рассматриваемом варианте. По элементам в этом окне определяются их частоты, по которым и строится таблица преобразования элементов входного потока в выходной. С остальными элементами, выходящими за окно, происходит то же, что в обычном варианте. Причем вес элементов в окне может убывать, например, линейно: от N у элемента, только что вошедшего в окно, до 1 у того, который окажется за окном на следующем шаге. Или, допустим, экспоненциально, или вообще не убывать: один вес у всех элементов, независимо от их расстояния до "вершины" окна. В отличие от методов Хаффмана/Шеннона-Фэно, "дерево" получается "прямое", а не "ветвистое": оно строится так, что на каждом этаже находится только один элемент. Такой MTF больше похож на PPM первого порядка, но, в отличие от него, на выход подаются байты, а не величины вероятностей в диапазоне от 0 до 1. 4. DC же в общем случае, в отличие от вышеописанных трех методов, RLE, SEM и MTF, применим к N-мерным данным, а не только одномерным. В двумерном случае можно кодировать расстояние до ближайшего равного элемента либо парой расстояний (X,Y) в декартовой системе координат, либо парой (угол, расстояние по прямой), или же "расстояние по спирали": 28 23 18 11 19 24 17 6 2 7 20 27 10 1 0 3 12 25 16 5 4 8 13 22 15 9 14 21 26 Аналогично в случае, если известно только то, что выше, или на той же высоте и левее: 17 14 18 11 8 6 9 12 16 7 3 2 4 10 15 13 5 1 0 Судя по всему, никто еще не пробовал применять 2-мерный DC для сжатия графики, но такие эксперименты могут привести к хорошим результатам на широком классе данных. "Плоский" одномерный DC, как и RLE, теоретически в большинстве случаев тем эффективней, чем меньше размерность R байта ММД, но практически... Опять же, примеры использования DC на одномерных ММД мне неизвестны, и скорее всего, их еще нет, так как DC привлек внимание исследователей недавно, и до сих пор исследован заметно меньше, чем другие методы. 5. LPC (Linear Prediction Coding, линейно предсказывающее кодирование), в том числе очень сложные, но и очень эффективные варианты CELP (Code-Excited Linear Prediction)[15,16] и MELP (Mixed Excitation Linear Prediction)[17], разработанные для сильного сжатия речи с потерями. Гораздо проще и распространеннее простейший вариант, называемый Delta Coding, дельта-кодирование. Например, ADPCM, Adaptive Delta PCM, Pulse Code Modulation. Используется аппроксимация B[i]=B[i-1], и поток { B[i] } преобразуется в { B[i]- -B[i-1] }. Из-за третьего свойства ММД ("ЛИНЕЙНОСТЬ") разность между соседними элементами, как правило, невелика. Поэтому Delta Coding применим ко всем "типичным" ММД, независимо от их происхождения, размерности и прочего. Более того, именно третье свойство ММД обычно применяют для нахождения ММД среди неизвестных данных. В том числе из-за крайне малого потребления ресурсов - памяти и процессорного времени. Через второй по сложности вариант ( приближение B[i-1]=(B[i]+B[i-2])/2, преобразование в B[i]-2*B[i-1]+B[i-2] ) приходим к общему виду: B[i]=sum(K[j]*B[j]), 0 < j < i . Обычно зависимость B[i] от предыдущих элементов убывает экспоненциально, и использовать больше десяти B[j] совершенно бесполезно. В двумерном случае второй вариант будет: B[i,k]=(B[i-1,k]+B[i,k-1])/2 , по B[i,k] строим { B[i,k]-(B[i-1,k]+B[i,k-1])/2 } . А третий: B[i,k]=(B[i-1,k]+B[i,k-1]+B[i-1,k-1])/3 Четвертый: B[i,k]-B[i-1,k]=B[i,k-1]-B[i-1,k-1] Дальнейшие усложнения в случае ММД не столь эффективны. Качественное улучшение- на десятки процентов - дает учет двух-трех соседних элементов, а остальных - на один-два процента. Использовать их все же полезно, но с другой целью: хорошо улучшает сжатие ММД дельта-кодированием процедура учета шума: каждый элемент ММД B[i] отклоняется от своего предсказуемого значения не только из-за "сильных" обусловленных воздействий, но и из-за слабых фоновых колебаний, то есть шума: B[i]=S[i]+N[i]. Ясно, что, во-первых, чем меньше вклад шума N[i], тем LPC эффективнее, а на фрагментах с "тишиной", содержащих только шум, LPC применять невыгодно (т.к. разности R-битных элементов будут (R+1)-битными, а не R-битными). А во-вторых, чем больше элементов рассмотреть, тем легче отделить главную тенденцию от фонового шума. 6. Изучая Delta Coding, легко изобрести еще один фундаментальный метод - Subband coding. В самом деле, если есть два "параллельных" блока (одинаковой длины) или потока (синхронных) B[i] и C[i], о которых известно, что они не независимы, как это использовать ? Если B и C - старшие и младшие биты после SEM, трудно придумать что-то лучше PBS, о нем рассказано ниже. Но если B и C - параллельные каналы ММД (показания близко стоящих измерительных устройств), то чаще всего они будут очень похожи: силы воздействия на них будут одного порядка (хотя вклад шума может быть и разным). Например, левый и правый каналы стерео звука. Попробуем учесть это с помощью такой же аппроксимации, что и в случае LPC: B[i]=C[i]. Если оказалось, что, действительно, кодировать D[i]=B[i]-C[i] выгоднее, чем B[i] или C[i], то какую функцию применить к остальному каналу ? Правильно, вместо остального канала можно хранить сумму A[i]=B[i]+C[i] , и это тоже на большинстве ММД дает выигрыш в степени сжатия. Главный недостаток такого разложения на среднее (average) и разность (delta) уже назывался выше: если для хранения элементов потоков B[i] и C[i] используется по R bit, то суммы и разности их будут (R+1)-битными. Если B[i] и C[i] - от 0 до 255, то суммы- от 0 до 510, разности- от -255 до 255. Что с этим делать ? Во-первых, заметим, что A[i] и D[i] либо оба четны, либо оба нечетны. То есть младший бит A[i] совпадает с младшим битом D[i]. Поэтому можно создавать либо D[i]= B[i]-C[i] и A[i]=(B[i]+C[i])/2 , либо D[i]=(B[i]-C[i])/2 и A[i]= B[i]+C[i] . Избавиться от второго "лишнего" бита можно лишь ценой некоторой потери в степени сжатия (деление целочисленное, (A)mod(B) - остаток от деления A на B) : либо V[i]=(B[i]+C[i])mod(2^R) и E[i]=(B[i]-V[i]/2)mod(2^R) , либо V[i]=(B[i]+C[i])mod(2^R) и E[i]=(C[i]-V[i]/2)mod(2^R) , либо E[i]=(B[i]-C[i])mod(2^R) и V[i]=(B[i]-E[i]/2)mod(2^R) , либо E[i]=(B[i]-C[i])mod(2^R) и V[i]=(C[i]+E[i]/2)mod(2^R) . Докажите, что по любой из этих пар массивов можно восстановить B[i] и C[i], а по этим - нельзя: A[i]=(B[i]+C[i])/2 и E[i]=(B[i]-A[i])mod(2^R) , A[i]=(B[i]+C[i])/2 и E[i]=(C[i]-A[i])mod(2^R) , D[i]=(B[i]-C[i])/2 и V[i]=(B[i]-D[i])mod(2^R) , D[i]=(B[i]-C[i])/2 и V[i]=(C[i]+D[i])mod(2^R) . Если каналов не два, а больше, допустим, девять, поиск оптимального преобразования становится очень нетривиальной задачей. Заметим лишь, что можно разбивать каналы на пары и применять Average+Delta преобразование к этим парам, а затем к результатам, а можно последовательно брать третий, четвертый и т.д. каналы и на каждом N-ом шаге сохранять разность N-го канала и среднего по всем N-1 предыдущим. Все это, однако, лишь предисловие к Subband Coding. Вернемся к случаю, когда канал только один. Применимо ли Average+Delta ? Да. Разбиваем все элементы B[i] на пары (B[2*j], B[2*j+1]) и преобразуем в два потока - Среднее и Разность. В случае ММД физический смысл Среднего - низкие частоты, а Разности - высокие. Традиционный Subband Coding состоит в многократном применении Average+Delta, каждый раз - к первому из двух создаваемых блоков, к низким частотам. Статья на русском для начинающих про Subband Coding и SEM: [20]. 7. Parallel Blocks Sorting. Сортировка Параллельных Блоков. Описание этого метода публикуется впервые. Подтверждают это и ведущие специалисты. Именно PBS используется для беспотерьного сжатия мультимедийных файлов в компрессоре ERI32, достигающем на самом известном наборе 24-битных картинок Kodak True Color Images мирового рекорда[21]. Имеем два параллельных блока: "основание" и "разбираемый". Сначала проходим по первому блоку, вычисляя каких байтов в нем сколько (цикл по размеру блока, получаем "длины ящиков"). Далее по полученному массиву N[i] создаем массив S[i]=N[i]+N[i-1] (цикл до 2^R, вычисляем "начала ящиков"). И наконец, главный цикл: идем синхронно по "основанию" и "разбираемому", берем байт X из "основания" и байт Z из "разбираемого", записываем Z по адресу (S[X]), прибавляем к S[X] единицу (цикл по размеру блока "раскладка по ящикам"). Заметим, что "оснований" может быть и два, и больше, тогда в первом и третьем циклах "суммарное основание" получается как сумма X1 + X2*2^R + X3*2^(2*R)+... Очень важен порядок оснований: первое, второе, третье, и т.д. Например, разделив (SEM) блок 32-битных байтов на "старшие 8", "средние 8" и "младшие 16", ST, SR и ML, сжатие будет лучше при суммарном основании SR+ST*256, а не ST+SR*256. Очевидно, что "основанием" может служить и сам "разбираемый" блок, циклически сдвинутый на C байт (наибольший интерес представляет C=1, то есть сортировка N[i] по N[i-1]). И даже в этом случае оснований может быть несколько. Если это двухмерные изображения, вторым основанием может быть "разбираемый", сдвинутый на такое D, чтобы байт N[i-D] был вторым из двух известных соседних, допустим, левого и верхнего. Это возможно потому, что прямоугольный блок двухмерных ММД можно записать в одномерную память последовательно, строка за строкой. Тогда D будет как раз длиной строки прямоугольного блока, (i-1) -ый элемент - пиксел слева от i-го, а (i-D) -ый - пиксел сверху от i-го. К сожалению, уже нет места для рассмотрения еще более сложных алгоритмов. Даже самое краткое описание каждого из них займет от ста до двухсот строк. 8. VQ, Vector Quantization. Векторная квантизация[23]. 9. Wavelet Transform[24] 10. Fractal Transform[25] 11. Enumerative Coding[26] 12. ERI93 Дальнейшие подробности и статьи - на http://artest.i.am и http://dogma.net/DataCompression/ Подводя итог, вернемся к определению ММД и рассмотрим его альтернативный вариант. I. ММИ - информация, приходящая из физического мира. ММД - результат ее измерения оцифровывающими устройствами. Кто и как их обрабатывает - вопрос второй. Есть и компьютерно синтезированные ММД (СММД), но их общий объем гораздо меньше, и их лучше рассматривать как базы данных: практически всегда даже невооруженным глазом видна искусственность, а алгоритмы их распознавания - не сложнее алгоритмов синтеза "hand-made" ММД. В частности, такие картинки сжимаются без потерь в 10 и более раз, а полученные оцифровкой - примерно в два-три раза. Оптимальное сжатие искусственных ММД - это алгоритм их создания. Но возможно и альтернативное "обратное" определение (спасибо Е.Шелвину), считающее Приемник важнее Источника. II. ММИ - информация, предназначенная для восприятия органами чувств человека. ММД - данные произвольной структуры/формата, являющиеся представлением некоторого объема ММИ. А что является их источником - вопрос второй. Но у альтернативного определения, похоже, больше недостатков, чем у первого. Вот некоторые из них: (1) Пока записанный блок ММД, допустим, звука, ни один человек не прослушал - он еще не является ММД, но как только прослушал - является ? Конечно, аналогичный "обратный" вопрос можно задать и первому определению: если блок ММД, допустим, "белый шум", создан оцифровкой тишины или белого листа бумаги, то это ММД, а если блок - результат работы компьютера, - то не ММД ? Именно так. В том числе потому, что реальный объект (физический мир) всегда сложнее (компьютерной) модели. Даже простейшие объекты (тишина, белый шум), а чем объект сложнее, тем больше он будет отличаться от своей модели. (2) Значительная часть данных, обладающих тремя главными свойствами ММД (размерность, линейность, каналы), обусловленными особенностями оцифровки и хранения ММИ, не будет являться ММД исключительно из-за определения ММД. (3) Главной характеристикой ММИ в альтернативном случае является "качество" - то есть соотношение в ней собственно информации и шумовой составляющей. А главным свойством ММД - наличие в них шума. Тем не менее, есть ММД без шума (и более того, в идеале ММД не содержат шума и сжимаются без потерь). Пример: так настраиваем микрофон в тишине, а сканер - на белом листе бумаги, чтобы шум был только в двадцатых битах. После этого при записи звука и сканировании изображений сохраняем только 16 битов каждого сэмпла и пиксела. Если доля шума меньше 0.01% - им можно смело пренебрегать в большинстве случаев. Большое спасибо Вадиму Юкину и Евгению Шелвину за комментарии и вопросы по первым версиям этой статьи. References ========== [1] http://geocities.com/eri32/int.htm [2] http://sochi.net.ru/~maxime/doc/ppm.txt [3] http://sochi.net.ru/~maxime/doc/bwt.txt [4] http://members.nbci.com/vycct/ [5] http://act.by.net/ [6] http://geocities.com/eri32/ [7] http://www.mp3-tech.org/ [8] http://www.jpeg.org/ [9] http://www.cbloom.com/src/ppmz.html [10] http://wannabe.guru.org/alg/node167.html [11] http://www.jucs.org/jucs_3_2/symbol_ranking_text_compression/html/paper.html [12] http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html [13] http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html [14] http://www.dakx.com/theory/index.html [15] http://www.data-compression.com/speech.html [16] http://rice.ecs.soton.ac.uk/jason/speech_codecs/standards/index.html [17] http://www.plh.af.mil/ddvpc/melp.htm [18] http://www.arturocampos.com/ac_flexible_parsing.html [19] http://www.dcs.warwick.ac.uk/~nasir/work/fp/ [20] http://www.computerra.ru/online/influence/kulibin/7261/ [21] http://geocities.com/eri32/kodak.html [22] http://www.7-zip.com/docpress.html [23] http://www.data-compression.com/vq.html [24] http://dogma.net/DataCompression/Wavelets.shtml [25] http://dogma.net/DataCompression/Fractal.shtml [26] ftp://oz.ee.umn.edu/users/kieffer/seminar/5585supp3.pdf Этот текст, English (ver.1.0) лежит на http://geocities.com/eri32/mmd.htm Russian (ver.1.0) на http://geocities.com/eri32/mmi.txt With best kind regards, A.Ratushnyak, http://i.am/artest go Back to main ARTest page Сжатие мультимедийной информации
версия 1.0