|
Страница 22 из 37
Шестнадцатибуквенный алфавит Хотя это не подходит для всех ситуаций, интерес представляет
метод сжатия данных, в котором уничтожаются ненужные буквы из
слова, то есть слово сокращается. Сжатие данных происходит за
счет того, что неиспользуемые символы не запоминаются. Экономия
пространства за счет сокращений довольно распространена, напри-
мер, "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
Энциклопедия по Турбо-Паскалю ч.2 = 35 =
IS ESSENTIAL TO MAINTAIN OUR OOTOLD
ENERAL RASIER
Как вы видите, сообщение является довольно читабельным, хотя
некоторая неоднозначность присутствует. Неоднозначность является
главным недостатком данного метода. Однако, если вы знакомы со
словарем писавшего сообщение, то возможно выберите лучший мини-
мальный алфавит, который снимет часть неясностей и неоднознач-
ностей.
Исходное сообщение имеет длину 168 байт, а упакованное сооб-
щение - 142 байта, следовательно, экономия составляет приблизи-
тельно 16%.
Если к данному сообщению применить и удаление символов и би-
товое сжатие, то сообщение сократится приблизительно на 28%. Нап-
ример, если бы вы были капитаном подводной лодки и хотели послать
сообщение в штаб, но не желали бы выдать ваше местоположение, то
вы могли бы захотеть сжать сообщение, используя оба метода, чтобы
оно было как можно короче.
Как метод битового сжатия, так и метод удаления символов
используются в криптографии. Битовое сжатие само по себе шифрует
информацию и делает декодирование более трудным. Метод удаления
символов при применении его до шифрования имеет одно преимущест-
во: он изменяет частоту использования символов в исходном тексте.
|