Методы сжатия с восстановлением должны обеспечить переход к исходному сообщению при заданном КСЖ.
n1 – число символов в исходном сообщении
n2 – число символов в сжатом сообщении
Простейшим способом такого сжатия является способ хранения атрибутов в виде битовой матрицы.
Передаются только единицы, которые оговариваются либо частотой, либо временем и т. д.
Методы сжатия цифровой информации с повторяющимися фрагментами
Предполагается, что информация записывается в файлы. Первая часть применима для тех информационных массивов, в которых повторяющиеся фрагменты стоят в начале строки. В этом случае используется символ пропуска r, весь массив передается одной строкой.
123456r7r41r2
Восстановление начинается от конца к началу, при известном количестве символов в строке. Запись каждой строки производится до символа пропуска.
Далее сверху вниз записываем символы предыдущей строки.
Второй способ используется для тех массивов, в которых повторы не только в начале строки: используется символ r и символ конца строки k.
Если массив строк одинаковой длины содержит несколько повторяющихся фрагментов в различных местах строки, то в этом случае вводятся символы, обозначающее количество пропусков и можно не использовать символ r конца строки.
Восстановление начинают с первой исходной строки, где количество пропусков определяется предыдущей строкой.
Если информация анкетного типа, записанная в алфавитно-цифровой форме, то можно использовать вместо части повторяющегося текста два значка (символа). Один из символ повтора, а второй – сколько букв пропущено при повторе.
Зонное сжатие
Метод зонного сжатия используют для текстовых массивов с учетом символов естественного алфавита и знаков препинания.
28 = 256
предложено использовать четыре бита (полубайт) для записи каждой буквы, тем самым создавая некоторый алфавит из шестнадцати букв, где каждая ячейка дает нам m = 24 = 16
162 = 256
Мы наши шестнадцать букв делим на некоторое количество зон:
A | |||||
B | |||||
C | D | E | |||
F |
Для русского алфавита достаточно 13 букв, распределенных по трем зонам.
0…С – имена букв
D…F – имена зон
С учетом вероятности появления букв друг с другом в тексте, таблица для русского алфавита выглядит следующим образом:
D | E | F | |
Space | З | Ц | |
О | У | Ж | |
Е | Д | Х | |
А | Я | Ч | |
Р | Ь | Э | |
П | Ф | Ю | |
Т | Ы | , | |
Н | Щ | . | |
В | Ш | ; | |
И | Б | : | |
A | С | Г | ! |
B | М | К | ? |
C | Л | Й | - |
Сжатие определяется нахождением букв в одной или в соседних зонах. И вероятность нахождения буквы где-либо по отношению к другой букве:
а – вероятность нахождения буквы в зоне D
б – вероятность нахождения буквы в зоне E
в – вероятность нахождения буквы в зоне F
Каждая буква записывается двумя символами:
номер зоны
номер буквы
если рядом стоящие буквы попадают в одну зону, то номер зоны пишется только один раз, а буквы чередуем.
В некоторых случаях можно использовать сочетание из двух и более букв в таблице, разделенные по зонам, принцип разделения можно оставить тем же.
Любой из перечисленных методов сжатия используется тогда, когда он дает максимальный эффект, который определяется величиной коэффициента сжатия или объемом сэкономленной памяти.