Упаковка данных
Возможность упаковки данных (архивирование) основана на том, что наиболее часто встречающиеся значения могут быть закодированы более короткими последовательностями битов, в то время как редко встречающиеся -длинными. В сумме это и дает эффект сокращения требуемого объема памяти. Самые простые архиваторы заранее "знают" о наиболее часто встречающихся значениях, более сложные -находят их сами. Например, при упаковке текста можно исходить из того, что наиболее вероятны последовательности букв одного регистра и одного алфавита (например, строчные латинские). В следующем примере для представления символа используется 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 & 1) << nb;
nb = (nb+1) % 8; // Следующий бит
if (nb==0) np++; // Переход в следующий байт
}
// Добавить 5-битный код, начиная с младшего бита
void PutBit_5(int code)
{
int n;
for (n=0; n< 5; n++)
{ PutBit(code); code >>=1; }
}
#define ULAT 26 // Определение кодов групп
#define LLAT 27
#define DIGIT 28
int group; // Текущая группа символов
void PutChar(char c) // Упаковать и добавить символ
{
int code;
int newgroup; // Группа нового символа
if (c >='A' && c<='Z')
{ newgroup = ULAT; code = c - 'A'; }
else
if (c >='a' && c <='z')
{ newgroup = LLAT; code = c - 'a'; }
else
if (c >='0' && c <='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');
}
