СПОСОБ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ДАННЫХ БЕЗ ПОТЕРЬ
METHOD OF COMPRESSING AND RETRIEVING DATA WITHOUT LOSS

Изобретение относится к области электросвязи, а именно к области, связанной с сокращением избыточности передаваемой информации, и может быть использовано для сжатия и восстановления без потерь цифровых данных в информационных системах и системах электросвязи.
2
Основы теории информации были заложены К.Шенноном в 1948 году в своей пионерской работе по теории информации (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004, стр.25), в которой он ввел понятие энтропии источника. Фундаментально значение этой величины состоит в том, что она задает нижнюю границу возможного сжатия (Д.Сэломон «Сжатие данных, изображений и звука», Москва, Техносфера, 2004, стр.8). К этой границе можно приближаться сколь угодно близко с помощью подходящего способа кодирования источника. Под энтропией символа а, имеющего вероятность Р, подразумевается количество информации, содержащейся в а, которая равна -P·log(P). (Д.Сэломон «Сжатие данных, изображений и звука», Москва, Техносфера, 2004, стр.25).
Различают сжатие без потерь, при котором возможно полностью восстановить исходную информацию, и сжатие с частичной потерей данных, при котором происходит восстановление данных с частичной потерей информации.
1
n
Известен способ сжатия и восстановления данных без потерь с использованием кодов переменной длины (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004 г., стр.26), включающий, выбор алфавита - набора символов от a до a, сбор статистики - вероятностей каждого символа алфавита в сжимаемом потоке данных, составление кодов переменной длины и замену исходных символов кодами переменной длины. Для восстановления первоначального потока данных в соответствии с построенными кодами переменной длины заменяют коды переменной длины на исходные символы алфавита.
Недостатком известного способа является:
- низкая скорость операций сжатия и восстановления;
- большое число вычислительных операций, необходимых для построения кодов переменной длины и восстановления данных.
Известен также способ сжатия и восстановления данных без потерь методом Хаффмана (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004 г., стр.30; М.Вернер "Основы кодирования", Москва, Техносфера, 2004 г., стр.29), включающий для выбранного алфавита
- составление списка символов алфавита в порядке убывания их вероятностей;
- объединение двух символов с наименьшими вероятностями в один составной знак. Переупорядочивание списка символов в соответствии с предыдущим шагом. Затем продолжают этот процесс до тех пор, пока все символы не будут объединены;
- начинают с последнего объединения. Приписывают первой компоненте составного символа символ 0, второй - символ 1. Продолжают до тех пор, пока все простые символы не будут закодированы.
Для восстановления необходимо в соответствии с построенными кодами Хаффмана преобразовать сжатый поток к первоначальному виду (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004 г., стр.38.; М.Вернер "Основы кодирования", Москва, Техносфера, 2004 г., стр.29). Для этого начинают с исходного узла построенного кодового дерева и двигаются в зависимости от считанного символа вверх или вниз до конечного узла.
Недостатками известного способа являются:
- низкая скорость операций сжатия и восстановления данных;
- максимальное сжатие достигается, если вероятности символов равны отрицательным степеням числа 2;
- различные длины кодовых слов приводят к неравномерным задержкам при восстановлении данных.
Техническим результатом заявляемого изобретения является повышение скорости операций сжатия и восстановления данных, повышение коэффициента сжатия данных для данных с высокой энтропией, упрощение реализации способа сжатия и восстановления, снижение числа операций сжатия и восстановления данных.
Указанный технический результат достигается тем, что в способе сжатия и восстановления данных, включающем выбор равных длин отрезков, на которые затем разбивают поток сжимаемых данных и обозначают эту длину через n бит, затем подсчитывают вероятности каждого из чисел длины n бит во всем сжимаемом потоке данных, согласно изобретению числа объединяют в префиксные группы и обозначают эти группы префиксными кодами, при этом в первую группу помещают числа с наибольшими вероятностями и присваивают данной префиксной группе самый короткий префиксный код, в следующую группу также помещают числа с наибольшими вероятностями из тех чисел, которые не были помещены в предыдущую группу, и присваивают данной префиксной группе следующий по длине префиксный код, а всего префиксных групп не должно быть больше n, после чего в каждой префиксной группе все числа нумеруют по порядку начиная с нуля и получают порядковый номер числа в префиксной группе, при этом для записи любого порядкового номера числа в конкретной префиксной группе выделяют такое количество бит, которое необходимо для записи максимального порядкового номера числа в данной префиксной группе, при этом как минимум сумма длины в битах самого короткого префиксного кода и длины в битах, выделенной для записи порядковых номеров чисел в префиксной группе, обозначенной самым коротким префиксным кодом, должна быть меньше n, затем числа от нуля до 2n-1, префиксные коды, порядковые номера чисел в префиксных группах заносят в таблицу и сохраняют ее, после этого преобразуют весь поток сжимаемых данных таким образом, что вместо исходного числа длины n бит записывают код префиксной группы и порядковый номер числа в префиксной группе, всю дальнейшую последовательность действий повторяют для следующего числа длины n бит, для восстановления потока данных считывают префиксный код группы и порядковый номер числа в префиксной группе и в соответствии с таблицей заменяют префиксный код группы и порядковый номер числа в префиксной группе на число, соответствующее префиксному коду группы и порядковому номеру числа в префиксной группе, затем считывают следующий префиксный код группы и порядковый номер числа в префиксной группе и всю дальнейшую последовательность действий повторяют.
Способ осуществляют следующим образом.
Выбирают равные длины отрезков, на которые затем разбивают поток сжимаемых данных и обозначают эту длину через n бит. Затем подсчитывают вероятности каждого из чисел длины n бит во всем сжимаемом потоке данных. Числа объединяют в префиксные группы и обозначают эти группы префиксными кодами, при этом в первую группу помещают числа с наибольшими вероятностями и присваивают данной префиксной группе самый короткий префиксный код, в следующую группу также помещают числа с наибольшими вероятностями из тех чисел, которые не были помещены в предыдущую группу, и присваивают данной префиксной группе следующий по длине префиксный код. Всего префиксных групп не должно быть больше n. После этого в каждой префиксной группе все числа нумеруют по порядку начиная с нуля и получают порядковый номер числа в префиксной группе, при этом для записи любого порядкового номера числа в конкретной префиксной группе выделяют такое количество бит, которое необходимо для записи максимального порядкового номера числа в данной префиксной группе. Как минимум сумма длины в битах самого короткого префиксного кода и длины в битах, выделенной для записи порядковых номеров чисел в префиксной группе, обозначенной самым коротким префиксным кодом, должна быть меньше n. Затем числа от нуля до 2n-1, префиксные коды, порядковые номера чисел в префиксных группах заносят в таблицу и сохраняют ее. Теперь преобразуют непосредственно поток данных. Для этого вместо первого числа длиной n бит записывают код префиксной группы и порядковый номер числа в префиксной группе. Всю дальнейшую последовательность действий повторяют для следующего числа длины n бит.
Для восстановления потока данных считывают префиксный код группы и порядковый номер числа в префиксной группе и в соответствии с таблицей заменяют префиксный код группы и порядковый номер числа в префиксной группе на число, соответствующее префиксному коду группы и порядковому номеру числа в префиксной группе. Затем считывают следующий префиксный код группы и порядковый номер числа в префиксной группе и всю дальнейшую последовательность действий повторяют.
Пример конкретного выполнения способа.
Выбирают равные длины отрезков, на которые затем разбивают поток сжимаемых данных. Обозначают эту длину через n бит, например 4 бит (см. табл.1). Затем подсчитывают вероятности каждого из чисел длины 4 бит во всем сжимаемом потоке данных (табл.1, графа 3). После этого числа объединяют в префиксные группы и обозначают эти группы префиксными кодами (см. табл.2). В первую группу помещают числа с наибольшими вероятностями и присваивают данной префиксной группе самый короткий префиксный код. Так в первую префиксную группу объединены числа 0001, 0010, 0100, 1000 и этой группе присвоен префиксный код 0. В следующую группу также помещают числа с наибольшими вероятностями из тех чисел, которые не были помещены в предыдущую группу. Это числа 0111, 1011, 1101, 1110. Этой группе присваивают префиксный код 10. Всего префиксных групп сформировано 4. После чего в каждой префиксной группе все числа нумеруют по порядку начиная с нуля и получают порядковый номер числа в префиксной группе (таблица 2, графа 4).
Таблица 1
Все числа от 0 до 2<sup>4</sup>-1 (в двоичном виде)
Количество чисел в сжимаемой последовательности
Вероятности чисел в сжимаемом потоке данных
1
2
3
0000
100
100/3200
0001
300
300/3200
0010
300
300/3200
0011
100
100/3200
0100
300
300/3200
0101
100
100/3200
0110
100
100/3200
0111
300
300/3200
1000
300
300/3200
1001
100
100/3200
1010
100
100/3200
1011
300
300/3200
1100
100
100/3200
1101
300
300/3200
1110
300
300/3200
1111
100
100/3200
Для записи любого порядкового номера числа в конкретной префиксной группе выделяют такое количество бит, которое необходимо для записи максимального порядкового номера числа в данной префиксной группе, поэтому в примере для записи порядковых номеров чисел во всех префиксных группах выделяют по два бита.
При этом как минимум сумма длины в битах самого короткого префиксного кода и длины в битах, выделенной для записи порядковых номеров чисел в префиксной группе, обозначенной самым коротким префиксным кодом, должна быть меньше 4. В приведенном примере код первой префиксной группы 0 занимает один бит, для записи порядкового номера числа в данной префиксной группе необходимо 2 бит.
Таблица 2
Все числа от 0 до 2<sup>4</sup>-1 (в двоичном виде)
Количество в сжимаемом потоке данных
Префиксные коды групп
Порядковый номер числа в префиксной группе
1
2
3
4
0000
100
111
00
0001
300
0
00
0010
300
0
01
0011
100
110
00
0100
300
0
10
0101
100
110
01
0110
100
110
10
0111
300
10
00
1000
300
0
11
1001
100
110
11
1010
100
111
01
1011
300
10
01
1100
100
111
10
1101
300
10
10
1110
300
10
11
1111
100
111
11
Таким образом, для записи любого числа, которое отнесено к первой префиксной группе потребуется 3 бит. При этом выигрыш от такого преобразования составит один бит на каждое число длиной 4 бит.
4
Все числа от нуля до 2-1, префиксные коды, порядковые номера чисел в префиксных группах заносят в таблицу 3 и сохраняют ее.
Таблица 3
Все числа от 0 до 2<sup>4</sup>-1 (в двоичном виде)
Префиксные коды групп
Порядковый номер числа в префиксной группе
1
2
3
0000
111
00
0001
0
00
0010
0
01
0011
110
00
0100
0
10
0101
110
01
0110
110
10
0111
10
00
1000
0
11
1001
110
11
1010
111
01
1011
10
01
1100
111
10
1101
10
10
1110
10
11
1111
111
11
Все вышеперечисленные действия предшествуют преобразованию потока данных.
Теперь преобразуют непосредственно поток данных. Для этого вместо первого числа длиной 4 бит исходного потока данных записывают код префиксной группы и порядковый номер числа в префиксной группе в соответствии с таблицей 3. Всю дальнейшую последовательность действий повторяют для всех последующих отрезков длины 4 бит.
Для восстановления потока данных считывают префиксный код группы и порядковый номер числа в префиксной группе и в соответствии с таблицей 3 заменяют префиксный код группы и порядковый номер числа в префиксной группе на число, соответствующее префиксному коду группы и порядковому номеру числа в префиксной группе, затем считывают следующий префиксный код группы и порядковый номер числа в префиксной группе и всю дальнейшую последовательность действий повторяют.
В таблице 4 показан расчет итогового размера, до которого будет сжат исходный поток данных без учета количества бит, необходимого для записи таблицы 3.
Размер всего потока данных до сжатия составлял: 4 бит*3200=12800 бит.
Размер данных после сжатия составил 12400 бит.
Заявляемый способ позволяет достичь
- более высокого коэффициента сжатия данных по сравнению с методом сжатия данных Хаффмана для данных с высокой энтропией;
- высокой скорости операций сжатия и восстановления данных, достигаемой, за счет замены операций вычисления операциями поиска по таблице и сокращения вычислительных операций;
Таблица 4
Все числа от 0 до 2<sup>4</sup>-1 (в двоичном виде)
Количество чисел в сжимаемом потоке (в десятичном виде)
Запись числа после преобразования (код группы и порядковый номер в группе)
Количество бит, которое занимает сжатое число (в десятичном виде)
Количество бит, необходимое для сжатия всех чисел: графу 2×графу 4 (в десятичном виде)
1
2
3
4
5
0000
100
111 00
5
500
0001
300
0 00
3
900
0010
300
0 01
3
900
0011
100
110 00
5
500
0100
300
0 10
3
900
0101
100
110 01
5
500
0110
100
110 10
5
500
0111
300
10 00
4
1200
1000
300
0 11
3
900
1001
100
110 11
5
500
1010
100
111 01
5
500
1011
300
10 01
4
1200
1100
100
111 10
5
500
1101
300
10 10
4
1200
1110
300
10 11
4
1200
1111
100
111 11
5
500
Итого:
3200
12400
- заявляемый способ может быть использован для отрезков различной длины;
- способ прост в реализации.
Таким образом, более высокая скорость выполнения операция сжатия и восстановления данных достигается за счет того, что префиксные коды присваиваются не всем числам длины n бит, а только группам, число которых значительно меньше, а также за счет того, что снижается количество вычислительных операций, в частности операций чтения кодов переменной длины, эти вычислительные операции заменяются операциями чтения записей из таблицы, что занимает значительно меньше времени.
Более высокий коэффициент сжатия достигается за счет того, что производятся операции группировки чисел и префиксные коды присваиваются не всем числам длины n бит, а только префиксным группам.