СЖАТИЕ ДАННЫХ
Методы сжатия данных позволяют заданное количество информа-
ции упаковать в меньший объем. Они часто используются в вычисли-
тельных системах для увеличения ресурсов памяти за счет снижения
необходимых объемов, для снижения времени передачи информации
(особенно по телефонному каналу), для повышения уровня секрет-
ности. Хотя существует много схем сжатия данных, мы рассмотрим
только две из них. Первая - это битовое сжатие, в котором более
одного символа запоминается в одном байте, а вторая - это уничто-
жение символов, при котором осуществляется удаление символов из
файла.
Восемь в семь
Большинство современных компьютеров используют размеры бай-
та, которые являются степенью двойки. Заглавные и строчные буквы
и знаки пунктуации составляют приблизительно 63 кодов, что требу-
ет 6 бит для представления байта (6-битовый байт может принимать
значения от 0 до 63). Однако, большинство компьютеров использует
8-битовый байт; таким образом 25% байта тратится зря в текстовых
файлах. Следовательно, можно упаковать 4 символа и 3 байта.
Единственная проблема состоит в том, что в коде ASCII существует
более 63 различных символов. Это означает, что некоторые необхо-
димые символы требуют по крайней мере 7 бит. Можно использовать
представление не в коде ASCII, но это нежелательно. Самый простой
вариант - это упаковка 8 символов в 7 байт, основывающийся на том
факте, что ни буквы, ни знаки пунктуации не используют восьмого
бита в байте. Следовательно, вы можете использовать восьмой бит
каждого из семи байт для запоминания восьмого символа. Данный ме-
тод экономит 12,5% памяти. Однако, многие компьютеры, включая IBM
PC, используют весь 8-битовый байт для представления специальных
и графических символов. Кроме того, некоторые текстовые процессо-
ры используют восьмой бит для задания команд текстовой обработки.
Следовательно, использование данного типа упаковки данных возмож-
но только с файлами типа ASCII, которые не используют восьмого
бита.
Для демонстрации того, как это происходит, рассмотрим следу-
ющие 8 символов, представленные как 8-битовые байты:
байт 1 0111 0101
байт 2 0111 1101
байт 3 0010 0011
байт 4 0101 0110
байт 5 0001 0000
байт 6 0110 1101
байт 7 0010 1010
байт 8 0111 1001
Как вы видите, восьмой байт всегда равен 0. Так происходит
всегда, кроме случая, когда восьмой бит используется для контроля
четности. Самый простой способ сжатия 8 символов в 7 байт состоит
в том, чтобы распределить 7 значащих бит байта 1 в семь неисполь-
зуемых восьмых битовых позиций байтов 2-8. Семь оставшихся байт
будут выглядеть следующим образом:
байт 2 1111 1101
байт 3 1010 0011
байт 4 1101 0110
байт 5 0001 0000
байт 6 1110 1101
байт 7 0010 1010
байт 8 1111 1001
байт 1 - читать вниз
Для восстановления байта 1 вы собираете вместе восьмые биты
каждого из 7 байт.
Данный метод сжимает любой текстовый файл на 1/8 или на
12,5%. Это весьма существенная экономия. Например, если вы пере-
давали исходный текст вашей любимой программы другу по телефонной
линии на большое расстояние, то вы сократите расходы на 12,5%
(напомним, что объектный и исполнительные коды программы требуют
всех 8 бит).
Следующая программа осуществляет сжатие текстового файла,
используя описанный метод:
{ данная программа сжимает 8 байт в семь }
program compress_file;
type
str80 = string[80];
var
inf, outf: str80;
ch: char;
t: integer;
procedure compress(inf, outf: str80);
var
infile, outfile: file of byte;
ch, ch2: byte;
done: boolean;
begin
assign(infile, inf);
reset(infile);
assign(outfile, outf);
rewrite(outfile);
done := FALSE;
repeat
Read(infile, ch);
if eof(infile) then
done := TRUE
else
begin
ch:=ch shl 1; {выдвижение свободного бита}
for t := 0 to 6 do
begin
if eof(infile) then
begin
ch2 := 0;
done := TRUE;
end else Read(infile, ch2);
ch2:=ch2 and 127; {сброс старшего бита }
ch2:=ch2 or ((ch shl t) and 128); {pack bits}
Write(outfile, ch2);
end;
end; {else}
until done;
WriteLn('file compressed'); 7
close(infile); close(outfile);
end; {compress}
procedure decompress(inf, outf: str80);
var
infile, outfile:file of byte;
ch, ch2: byte;
s: array[1..7] of byte;
done: boolean;
begin
assign(infile, inf);
reset(infile);
assign(outfile,outf);
rewrite(outfile);
done := FALSE;
repeat
ch := 0;
for t := 1 to 7 do
begin
if eof(infile) then
done := TRUE
else
begin
Read(infile, ch2);
s[t] := ch2 and 127; {сброс старшего бита}
ch2 := ch2 and 128; {очистка младших битов}
ch2 := ch2 shr t; {распаковка}
ch := ch or ch2; {встраивание восьмого байта}
end;
end;
Write(outfile, ch);
for t := 1 to 7 do Write(outfile, s[t]);
until done;
WriteLn('file decompressed');
close(infile); close(outfile);
end; {decompress}
begin
Write('введите имя входного файла: ');
ReadLn(inf);
Write('введите имя выходного файла: ');
ReadLn(outf);
Write('сжатие или распаковка (C or D): ');
ReadLn(ch);
if upcase(ch)='C' then compress(inf, outf)
else if upcase(ch)='D' then decompress(inf,outf);
end.
Данная программа достаточно сложна, так как различные биты
должны быть сдвинуты циклически. Если вы помните, что надо сде-
лать с первым из каждых восьми байт то легче понять программу.
Для того, чтобы программа работала правильно, длина сжимаемого
файла должна быть кратна 8. Это означает, что очень короткие фай-
лы (меньше 64 символов) будут длинее, чем несжатая версия. Одна-
ко, на длинных файлах этого не произойдет.
Шестнадцатибуквенный алфавит
Хотя это не подходит для всех ситуаций, интерес представляет
метод сжатия данных, в котором уничтожаются ненужные буквы из
слова, то есть слово сокращается. Сжатие данных происходит за
счет того, что неиспользуемые символы не запоминаются. Экономия
пространства за счет сокращений довольно распространена, напри-
мер, "Mr" используется вместо "Mister". Вместо применения общеп-
ринятых сокращений в описываемом в данном разделе методе осущест-
вляется автоматическое удаление различных букв из сообщения. Для
реализации этого необходимы "минимальный алфавит. Минимальным на-
зывается такой алфавит, из которого исключены редко используемые
буквы и оставлены только те, которые необходимы для составления
большинства слов или для избежания неоднозначности. Следователь-
но, любой символ, который не входит в минимальный алфавит, будет
удален из слова, в котором он появился. Предметом выбора является
минимальный алфавит. В данном разделе используются 14 наиболее
часто встречающихся букв плюс символы пробела и возврата каретки.
Автоматизация процесса сокращения требует, чтобы вы знали,
какие буквы в алфавите используются наиболее часто, чтобы можно
было составить минимальный алфавит. Теоретически вы могли бы
подсчитать буквы в каждом слове словаря; однако, у различных лю-
дей словарные смеси отличаются, поэтому частотная диаграмма,
построенная только на словах английского языка, не может отражать
действительной частоты использования букв. В качестве альтернати-
вы вы можете подсчитать частоты использования букв в данной главе
и использовать их в качестве основы для составления вашего мини-
мального алфавита. Для реализации этого вы могли бы использовать
следующую простую программу. Данная программа пропускает все зна-
ки пунктуации, исключая точку, запятую и пробел.
{данная программа подсчитывает число символов каждого
типа в файле}
program countchars;
type
str80 = string[80];
var
inf: str80;
t: integer;
alpha: array[0..25] of integer;
space, period, comma: integer;
{ данная функция возвращает TRUE, если ch является
буквой алфавита }
function isalpha(ch: char): boolean;
begin
isalpha:=(upcase(ch)>='A') and (upcase(ch)<='Z');
end; {isalpha}
{ подсчет числа встреч каждого символа в файле }
procedure count(inf: str80);
var
infile: file of char;
ch: char;
begin
assign(infile, inf);
reset(infile);
while not eof(infile) do
begin
Read(infile, ch);
ch := upcase(ch);
if isalpha(ch) then
alp a[ord(ch)-ord('A')] := alpha[ord(ch)-ord('A')]+1
else case ch of
' ': space := space+1;
'.': period := period+1;
',': comma := comma+1;
end;
end;
close(infile);
end; {count}
begin
Write('введите имя входного файла: ');
ReadLn(inf);
for t := 0 to 25 do alpha[t] := 0;
space := 0; comma := 0; period := 0;
count(inf);
for t := 0 to 25 do
WriteLn(chr(t+ord('A')), ': ', alpha[t]);
WriteLn('space:', space);
WriteLn('period:', period);
WriteLn('comma:', comma);
end.
После прогона данной программы с текстом данной главы вы по-
лучите следующую таблицу частот:
A 2525 P 697
B 532 Q 62
C 838 R 1656
D 1145 S 1672
E 3326 T 3082
F 828 U 869
G 529 V 376
H 1086 W 370
I 2242 X 178
J 39 Y 356
K 94 Z 20
L 1103
M 1140 Space 1 5710
N 2164 Period 2 234
O 1767 Comma 3 513
1 - пробел; 2 - точка; 3 - запятая.
Данные частоты использования букв хорошо согласуются со
стандартной смесью английского языка, а некоторое отклонение объ-
ясняется повторяющимся использованием ключевых слов Турбо Паскаля
в программах.
Для того, чтобы добиться значительного сжатия данных, вы
должны существенно урезать алфавит за счет наименее часто исполь-
зуемых букв. Хотя существует много вариантов минимального алфави-
та, в данной главе в него включены 14 наиболее часто используемых
букв и пробел, которые составляют 85% всех символов данной главы.
Так как символ возврата каретки необходим для предотвращения раз-
рывов слов, он также должен быть включен в алфавит. Таким обра-
зом, минимальный алфавит будет следующим:
A B D E H I L M N O R S T U <пробел><возврат каретки>
Следующая программа удаляет все символы, кроме выбранных.
Программа записывает комбинацию возврат каретки/перевод строки,
если она присутствует. Это делает вывод читабельным.
{ программа сжатия и удаления символов }
program compres2;
type
str80 = string[80];
var
inf, outf: str80;
ch: char;
t: integer;
procedure comp2(inf, outf: str80);
var
infile, outfile: file of char;
ch: char;
done: boolean;
begin
assign(infile, inf);
reset(infile);
assign(outfile, outf);
rewrite(outfile);
done := FALSE;
repeat
if not eof(infile) then
begin
Read(infile, ch);
ch := upcase(ch);
if pos(ch,'ABCDEJILMNORSTU')<>0 then Write(outfile,ch);
if ord(ch)=13 then Write(outfile, ch); {cr}
if ord(ch)=10 then Write(outfile, ch); {lf}
end
else done := TRUE;
until done;
WriteLn('файл сжат ');
close(infile); close(outfile);
end; {compress}
begin
Write('введите имя входного файла:');
ReadLn(inf);
Write('введите имя выходного файла: ');
ReadLn(outf);
comp2(inf, outf);
end.
8Программа использует встроенную функцию Pos для определения
того, входит ли считанный символ в минимальный алфавит. Роs возв-
ращает 0, если не входит, и номер позиции символа в алфавите,
если входит.
Если вы примените программу к следующему сообщению
Attention High Command:
Attack successul. Please send additional supplies
and fresh troops. This is essential to maintain
our foolhold.
General Frashier
сжатое сообщение будет следующим
ATTENTOIN I COMMAND
ATTAC SUCCESSUL LEASE SEND
ADDITIONAL SULEIS AND RES TROOS TIS
IS ESSENTIAL TO MAINTAIN OUR OOTOLD
ENERAL RASIER
Как вы видите, сообщение является довольно читабельным, хотя
некоторая неоднозначность присутствует. Неоднозначность является
главным недостатком данного метода. Однако, если вы знакомы со
словарем писавшего сообщение, то возможно выберите лучший мини-
мальный алфавит, который снимет часть неясностей и неоднознач-
ностей.
Исходное сообщение имеет длину 168 байт, а упакованное сооб-
щение - 142 байта, следовательно, экономия составляет приблизи-
тельно 16%.
Если к данному сообщению применить и удаление символов и би-
товое сжатие, то сообщение сократится приблизительно на 28%. Нап-
ример, если бы вы были капитаном подводной лодки и хотели послать
сообщение в штаб, но не желали бы выдать ваше местоположение, то
вы могли бы захотеть сжать сообщение, используя оба метода, чтобы
оно было как можно короче.
Как метод битового сжатия, так и метод удаления символов
используются в криптографии. Битовое сжатие само по себе шифрует
информацию и делает декодирование более трудным. Метод удаления
символов при применении его до шифрования имеет одно преимущест-
во: он изменяет частоту использования символов в исходном тексте.
