3. Mtf (Move To Front, Сдвиг к Вершине) и dc (Distance Coding, Кодирование Расстояний) хорошо описаны в bwt-faq-e Вадима Юкина.

Добавить можно лишь то, чего я пока не видел в описаниях этих методов. 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) и MELP (Mixed Excitation Linear Prediction), разработанные для сильного сжатия речи с потерями.

Гораздо проще и распространеннее простейший вариант, называемый 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, каждый раз - к первому из двух создаваемых блоков, к низким частотам.

7. Parallel Blocks Sorting. Сортировка Параллельных Блоков. Описание этого метода публикуется впервые. Подтверждают это и ведущие специалисты. Именно PBS используется для беспотерьного сжатия мультимедийных файлов в компрессоре ERI32, достигающем на самом известном наборе 24-битных картинок Kodak True Color Images мирового рекорда.

Имеем два параллельных блока: «основание» и «разбираемый».

Сначала проходим по первому блоку, вычисляя каких байтов в нем сколько (цикл по размеру блока, получаем «длины ящиков»).

Далее по полученному массиву 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-го.

К сожалению, уже нет места для рассмотрения еще более сложных алгоритмов. Даже самое краткое описание каждого из них займет от ста до двухсот строк.