Сжатие с восстановлением

2.2 Сжатие с восстановлением

Методы сжатия с восстановлением должны обеспечить переход к исходному сообщению при заданном КСЖ.

n1 – число символов в исходном сообщении

n2 – число символов в сжатом сообщении

Простейшим способом такого сжатия является способ хранения атрибутов в виде битовой матрицы.

Передаются только единицы, которые оговариваются либо частотой, либо временем и т. д.

2.3 Методы сжатия цифровой информации с повторяющимися фрагментами

 

Предполагается, что информация записывается в файлы. Первая часть применима для тех информационных массивов, в которых повторяющиеся фрагменты стоят в начале строки. В этом случае используется символ пропуска r, весь массив передается одной строкой.

123456r7r41r2

Восстановление начинается от конца к началу, при известном количестве символов в строке. Запись каждой строки производится до символа пропуска.

Далее сверху вниз записываем символы предыдущей строки.

Второй способ используется для тех массивов, в которых повторы не только в начале строки: используется символ r и символ конца строки k.

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

Восстановление начинают с первой исходной строки, где количество пропусков определяется предыдущей строкой.

Если информация анкетного типа, записанная в алфавитно-цифровой форме, то можно использовать вместо части повторяющегося текста два значка (символа). Один из символ повтора, а второй – сколько букв пропущено при повторе.

2.4 Зонное сжатие

 

Метод зонного сжатия используют для текстовых массивов с учетом символов естественного алфавита и знаков препинания.

28 = 256

предложено использовать четыре бита (полубайт) для записи каждой буквы, тем самым создавая некоторый алфавит из шестнадцати букв, где каждая ячейка дает нам m = 24 = 16

162 = 256

Мы наши шестнадцать букв делим на некоторое количество зон:

0	0000	4	0100	8	1000
1	0001	5	0101	9	1001
2	0010	6	0110	A	1100
3	0011	7	0111	B	1011
C	1100	D	1101	E	1110
F	1110

Для русского алфавита достаточно 13 букв, распределенных по трем зонам.

0…С – имена букв

D…F – имена зон

С учетом вероятности появления букв друг с другом в тексте, таблица для русского алфавита выглядит следующим образом:

	D	E	F
0	Space	З	Ц
1	О	У	Ж
2	Е	Д	Х
3	А	Я	Ч
4	Р	Ь	Э
5	П	Ф	Ю
6	Т	Ы	,
7	Н	Щ	.
8	В	Ш	;
9	И	Б	:
A	С	Г	!
B	М	К	?
C	Л	Й	-

Сжатие определяется нахождением букв в одной или в соседних зонах. И вероятность нахождения буквы где-либо по отношению к другой букве:

а – вероятность нахождения буквы в зоне D

б – вероятность нахождения буквы в зоне E

в – вероятность нахождения буквы в зоне F

Каждая буква записывается двумя символами:

номер зоны

номер буквы

если рядом стоящие буквы попадают в одну зону, то номер зоны пишется только один раз, а буквы чередуем.

В некоторых случаях можно использовать сочетание из двух и более букв в таблице, разделенные по зонам, принцип разделения можно оставить тем же.

Любой из перечисленных методов сжатия используется тогда, когда он дает максимальный эффект, который определяется величиной коэффициента сжатия или объемом сэкономленной памяти.