Информатика и технология программирования

       

Упаковка данных


Возможность упаковки данных (архивирование) основана на том, что наиболее часто встречающиеся значения могут быть закодированы более короткими последовательностями битов, в то время как редко встречающиеся -длинными. В сумме это и дает эффект сокращения требуемого объема памяти. Самые простые архиваторы заранее "знают" о наиболее часто встречающихся значениях, более сложные -находят их сами. Например, при упаковке текста можно исходить из того, что наиболее вероятны последовательности букв одного регистра и одного алфавита (например, строчные латинские). В следующем примере для представления символа используется 5 битов (32 значения). Значениями 0..25 кодируются сами символы, объединенные в группы (строчные латинские буквы, прописные латинские, цифры и пр.), значениями 26..31 - группы символов. При следовании в тексте подряд двух символов из разных групп в последовательность 5-битовых кодов перед вторым символом добавляется его номер группы. 5-битовые коды упаковываются в массив байтов (8 бит).


//------------------------------------------------------bk48-01.cpp


//------Упаковка символов 5-битным кодом


unsigned char PACK[1000]; // Массив упакованных данных


int np; // Текущий байт


int nb; // Текущий бит


// Добавить бит в последовательность в массиве


void PutBit(int byte)
{
if (nb==0) PACK[np]=0; // Запись нового байта


PACK[np] |= (byte &#38 1) &#60&#60 nb;
nb = (nb+1) % 8; // Следующий бит


if (nb==0) np++; // Переход в следующий байт


}


// Добавить 5-битный код, начиная с младшего бита


void PutBit_5(int code)
{
int n;
for (n=0; n&#60 5; n++)
{ PutBit(code); code &#62&#62=1; }
}


&#35define ULAT 26 // Определение кодов групп


&#35define LLAT 27
&#35define DIGIT 28
int group; // Текущая группа символов


void PutChar(char c) // Упаковать и добавить символ


{
int code;
int newgroup; // Группа нового символа


if (c &#62='A' &#38&#38 c&#60='Z')
{ newgroup = ULAT; code = c - 'A'; }
else
if (c &#62='a' &#38&#38 c &#60='z')
{ newgroup = LLAT; code = c - 'a'; }
else
if (c &#62='0' &#38&#38 c &#60='9')
{ newgroup = DIGIT; code = c - '0'; }
else
if (c == ' ')
{ newgroup = DIGIT; code = 10; }
if (c == '\0')
{ newgroup = DIGIT; code = 11; }
if (newgroup != group)
{ group = newgroup; PutBit_5(group); }
PutBit_5(Code);
}


void PutString(char s[])
{ int n;
nb = np = n = 0;
do PutChar(s[n]); while(s[n++] !='\0');
}



Содержание раздела