Сжатие информации и кодирование

Сжатие и кодирование информации требуется прежде всего для орга­низации долговременного хранения и передачи данных. Обычно пакеты программ, игрушки и т.п. передают в виде архивов, запакованных специ­альными программами упаковщиками. Наиболее распространенными из них являются ARJ, ZIP, RAR. Любой упаковщик работает на трех основных принципах.

Если взять любой файл на диске, например этот текст, в нем есть часто встречающиеся символы, редко встречающиеся и вовсе отсутствую­щие. Например пробел в этом тексте встречается 2756 раз, точка 1139 раз, буква i 620 раз, но из 255 возможных символов алфавита 162 симво­ла в этом тексте не встречаются ни разу. Это более половины алфавита ЭВМ. Следовательно, для этого файла, два символа можно закодировать одним.

Кроме этого существуют повторяющиеся последовательности, например строка из пробелов. Тогда тоже достаточно в архиве сохранить один сим­вол и указать количество его повторений.

Для маленьких файлов существует третий способ сократить занимае­мое ими место. Файловая система MS DOS не может выделить для записи на диск блоками по 4 кБ. Даже если указывается, что файл занимает 1 байт, на самом деле он занимает 4 кБ, или для большего файла кратный 4 кБ размер. По этому даже простое слияние нескольких файлов в один, уже сокращает занимаемое ими место.

При передачи данных по каналам связи, например модем, встает обратная задача. Необходимо добавить к каждому передаваемому байту проверочную информацию, которая должна позволить принимаемой стороне распознать и если возможно исправить ошибку воз­никшую в канале связи. Этот процесс называется кодированием.

Может быть применено и шифрование. Тогда с информацией производят преобразования, например замену всех символов на другие значения из специальной таблицы. Понять такой текст без этой таблицы (ключа) не­возможно.

Программа анализа файла

#include <stdio.h>

#include <conio.h>

int main(void)

{

char name1[20],ch; /* Имя обрабатываемого файла */

FILE *File1; /* Указатель на файл */

unsigned int nc[256],i,n; /* nc - счетчик вхождений символов */

printf("\n Введите имя исходного файла: ");

scanf("%s",name1);

File1=fopen(name1, "rt");

if(File1==NULL)

{

printf("\n Открыть указанный файл невозможно."); return(1);

} /* Кон. if(ошибка открытия файла) */

for(i=0;i<256;i++) nc[i]=0; /* Обнуление счетчика */

while(!feof(File1))

{

fscanf(File1,"%1c",&ch);

nc[ch]++;

} /* Кон. while() просмотр файла */

fclose(File1);

n=0;

for(i=0;i<256;i++) if(nc[i]==0) n++; /* Подсчет числа неиспользуемых символов */

printf("\n В файле содержатся:");

for(i=1;i<256;i++)

{

printf("\n Символ: %c (%3d) содержимся %5d раз.",i,i,nc[i]);

if((i%20)==0) getch(); /* Задержка после вывода страницы */

} /* Кон. for() */

printf("\n В файле ни разу не использовались %d символов.",n);

return(1);

} /* Кон. main() */

Упаковщик файлов

Необходимо реализовать простейший упаковщик реализующий следующий алгоритм сжатия. Составляется таблица перекодировки символов, символы не используемые в файле в ней отсутствуют. Если количество не используемых символов велико, то можно записать в один символ несколько. Для этого рекомендуется использовать операцию сдвига.

В предлагаемой программе предлагается записывать два символа в один, это возможно если число используемых символов в тексте не превышает 32, только заглавные или строчные буквы. Иначе программа должно вывеси сообщение о невозможности сжать файл.

Позиционирование по файлу

Позиционирование по файлу осуществляет функция: fseek(*<Файл>, <Смещение>, <Откуда>) <Откуда> - одно из

SEEK_SET начало файла

SEEK_CUR - текущая позиция.

SEEK_END - конец файла.

*<Файл> - Указатель на файл полученный из open().

Двоичный сдвиг

<Переменная или число> >> <Количество разрядов>

<Переменная или число> << <Количество разрядов>

Операция выполняет двоичный сдвиг числа на указанное число разрядов, так как числа представляются в двоичной системе счисления, сдвиг на 1 разряд эквивалентен делению или умножению на 2.

Операция допустима только над типами int, long, char.