побитовое терминаторное кодирование
Вот придумал метод компрессии медиа данных.
Собственно любой метод компрессии основан на некоторых закономерностях входного
сигнала. Допустим, обезьяна стучит по клавиатуре и чаще попадает по левой нижней
части (в правой руке мышка) тогда это один метод компрессии. если стучит
пятерней то все клавиши могут быть и равновероятны тогда первый метод не
подойдет, но вероятность комбинации бла- бла-бла будет выше.
Особенность медиаданных в том что имеется некоторое распределение значений, но
предпосылок для существенного отличия вероятностей близких значений N и N+1 нет.
Известно что медиаданные плохо поддаются компрессии, желательно просто хранить
младшие биты. Разумеется необходимо пользоваться каким-то предсказанием.
Предложение состоит в том чтоб старшие биты заменить символами расширенного
алфавита и паковать их арифметикой. Простейший вариант это старшую единице с
ведущими нулями заменить на символ Т
Получим
1 - Т
2 – 0Т
3 – 1Т
4 - 00Т
5 – 10Т
6 – 01Т
Записано от младших к старшим. Несложно представить и знаковые числа путем
преобразования
0 = 1 = Т
1 = 2 = 0Т
-1 = 3 = 1Т
2 = 4 = 00Т
-2 = 5 = 10Т
3 = 6 = 01Т
Возможно и использование 2-х или нескольких старших битов, при этом вероятность
старшей 01 и 11 будут отличаться. Таким образом чтоб приступить к паковке
достаточно просто набрать статистику по длине кодов. Это минимальное количество
информации и его можно хранить дешево.
Сейчас же часто пользуются предопределенными кодами Хафмена. Ясно что
предопределенное распределение может оказаться не оптимальным для конкретного
случая. Для 8-битных это еще куда ни шло, а что делать с 16 или допустим 24?
Метод Хафмена это префиксный метод, в отличие от предлагаемого постфиксного.
Если спускаться по дереву Хафмена , то может встретиться например, 3
равновероятных значения 2 бита много для 3 листьев и понятно что в этом случае
произойдет эффективности из-за грануляции. Арифметика же свободна от этих
недостатков. Вот коды паковки трехсимвольного алфавита {0,1,Т}. Разрядность
значений 32-24 бита, по исчерпанию 24-х барется следующий байт (здесь интель
ордер).
Сейчас подана заявка на это, ежели кого интересует прошу обращаться, могу и
переуступить.
Коды wav компрессора сжатие 80-70% . Из музыкального сборника наилучший результат дают естественно басовые вещи “locomotive breath” Juthro tull и “La Grande” ZZ Top. В этих кодах просто кодируется первая разность. Вторая дает до 62% Коды Микрософт специфик - единственная команда нужная JC- переход по переносу, для GNU инлайн в кавычках
// (C) Drobotenko A 2007-2008
// http://drobotenko.com/compres.html
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
struct Code01
{ unsigned cod;
int operator()(int z)
{ cod=z<0? (-z)<<1: (z<<1)|1;
return getBit();
}
int getBit()
{ unsigned k= cod;
return !(cod>>=1)?2:k&1;
}
};
struct DeCode01
{ int v,z,mask;
void init(){v=z=0; mask=1;}
void putBit(int b)
{ if(b>=1)
v|=mask;
mask<<=1;
}
int get()
{ return v&1? v>>1:-(v>>1);
}
};
void test_codedecode()
{ int j,k;
for(j=145;j!=-12333;j--)
{ DeCode01 dcd;
Code01 cd;
k=cd(j);
dcd.init();
for(;k!=2;)
{ dcd.putBit(k);
k=cd.getBit();
}
dcd.putBit(2);
k=dcd.get();
if(k==j)
k=__LINE__;
else
k=__LINE__;
}
}
struct
{ float chance;
int T, total;
} statistic[24];
void statistician(int v)
{ Code01 c;
int j=0,k=c(v);
for(;;)
{ statistic[j].total++;
if(k==2)
break;
j++;
k=c.getBit();
}
statistic[j].T++;
}
void test_compress(int nz,signed int *in,unsigned char *packed,signed int *out)
{
int j,k, in_j,jbit;
unsigned long kod_range=0xFFFFffffu;
unsigned long kod_out=0;
int jpak=0;
Code01 c01;
for(j=0,in_j=2;;)
{ if(in_j==2)
{ if(++j==nz)
break;
in_j=c01(in[j]-in[j-1]);
jbit=0;
}
else
in_j=c01.getBit(),jbit++;
unsigned codt=kod_range*statistic[jbit].chance, addcod;
switch(in_j)
{ case 0: kod_range=codt-1; addcod=0;
break;
case 1: kod_range=codt-1; addcod=codt;
break;
case 2: kod_range=kod_range-2*codt; addcod=2*codt;
break;
}
int jb=jpak,i8;
kod_out+=addcod;
__asm jnc _ncarry
_carry:
i8=packed[--jb]+1;
packed[jb]=i8;
if(i8&0x100)
goto _carry;
_ncarry:
if(!(kod_range&0xFF000000))
kod_range<<=8
,packed[jpak++]=(unsigned char)(kod_out>>24)
,kod_out<<=8;
}
packed[jpak++]=kod_out>>24;
packed[jpak++]=kod_out>>16;
packed[jpak++]=kod_out>>8;
packed[jpak++]=kod_out;
packed[jpak++]=0;
packed[jpak++]=0;
packed[jpak++]=0;
printf("Compression ratio % f\n",jpak*.5/nz);
kod_range=0xFFFFffffu;
kod_out=packed[3]|long(packed[2])<<8|long(packed[1])<<16|long(packed[0])<<24;
jpak=4;
out[0]=in[0];
DeCode01 dcd;
dcd.init();
int out_j;
for(j=0,jbit=0;;)
{ unsigned kod_0=kod_range*statistic[jbit].chance, addcod;
jbit++;
if(kod_out>=2*kod_0)
{ kod_range=kod_range-2*kod_0; addcod=2*kod_0;
out_j=2;
}
else
if(kod_out>=kod_0)
{ kod_range=kod_0-1; addcod=kod_0;
out_j=1;
}
else
{ kod_range=kod_0-1; addcod=0;
out_j=0;
}
kod_out-=addcod;
dcd.putBit(out_j);
if(out_j==2)
{ j++;
out[j]=out[j-1]+dcd.get();
if(in[j]!=out[j])
{ __asm nop;
assert(1);
return;
}
__asm nop;
dcd.init();
jbit=0;
if(j>=nz-1-3)
break;
}
if(!(kod_range&0xFF000000))
kod_out=(kod_out<<8)|packed[jpak++]
,kod_range<<=8;
}
}
void main(int , char **argv)
{ FILE *wav_file=fopen(argv[1],"rb");
fseek(wav_file,0,SEEK_END );
long sz=ftell(wav_file);
signed int *lift=(signed int *)malloc(sz)
,*right=(signed int *)malloc(sz)
,*control=(signed int *)malloc(sz);
unsigned char *output=(unsigned char *)malloc(sz);
fseek(wav_file,6000,SEEK_SET );
int j,k,nz=(sz-6000)/4;
short l16,r16;
for(j=0;j<nz;j++)
fread(&l16,2,1,wav_file)
,fread(&r16,2,1,wav_file)
,lift[j]=l16,right[j]=r16;
for(j=1;j< nz-1;j++)
statistician(lift[j]-lift[j-1])
,statistician(right[j]-right[j-1]);
for(j=0;j< 24;j++)
{ statistic[j].chance=(statistic[j].T+1.)/(statistic[j].total+1);
if(statistic[j].chance<.0003)
statistic[j].chance=.0003;
if(statistic[j].chance>.9997)
statistic[j].chance=.9997;
statistic[j].chance=(1-statistic[j].chance)*.5;
}
test_compress(nz,lift,output,control);
test_compress(nz,right,output,control);
}