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

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

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

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

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

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

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

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

123456r7r41r2

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

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

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

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

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

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

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

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

28 = 256

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

162 = 256

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

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

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

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

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

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

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

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

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

номер зоны

номер буквы

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

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

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