способ сжатия и восстановления данных без потерь

Формула изобретения

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

Описание изобретения к патенту

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

Основы теории информации были заложены К.Шенноном в 1948 году в своей пионерской работе по теории информации (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004, стр.25), в которой он ввел понятие энтропии источника. Фундаментально значение этой величины состоит в том, что она задает нижнюю границу возможного сжатия (Д.Сэломон «Сжатие данных, изображений и звука», Москва, Техносфера, 2004, стр.8). К этой границе можно приближаться сколь угодно близко с помощью подходящего способа кодирования источника. Под энтропией символа а, имеющего вероятность Р, подразумевается количество информации, содержащейся в а, которая равна -P·log₂ (P). (Д.Сэломон «Сжатие данных, изображений и звука», Москва, Техносфера, 2004, стр.25).

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

Известен способ сжатия и восстановления данных без потерь с использованием кодов переменной длины (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004 г., стр.26), включающий, выбор алфавита - набора символов от a ₁ до a_n, сбор статистики - вероятностей каждого символа алфавита в сжимаемом потоке данных, составление кодов переменной длины и замену исходных символов кодами переменной длины. Для восстановления первоначального потока данных в соответствии с построенными кодами переменной длины заменяют коды переменной длины на исходные символы алфавита.

Недостатком известного способа является:

- низкая скорость операций сжатия и восстановления;

- большое число вычислительных операций, необходимых для построения кодов переменной длины и восстановления данных.

Известен также способ сжатия и восстановления данных без потерь методом Хаффмана (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 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 до 24-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 до 24-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 бит.

Все числа от нуля до 2⁴-1, префиксные коды, порядковые номера чисел в префиксных группах заносят в таблицу 3 и сохраняют ее.

Таблица 3
Все числа от 0 до 24-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 до 24-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 бит, а только префиксным группам.