|
Страница 21 из 37
Восемь в семь Большинство современных компьютеров используют размеры бай-
та, которые являются степенью двойки. Заглавные и строчные буквы
и знаки пунктуации составляют приблизительно 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 символов) будут длинее, чем несжатая версия. Одна-
ко, на длинных файлах этого не произойдет.
|