СПОСОБ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ДАННЫХ БЕЗ ПОТЕРЬ Российский патент 2010 года по МПК H03M7/30 H03M7/42 

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

Основы теории информации были заложены К.Шенноном в 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 до 2⁴-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⁴-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 до 2⁴-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⁴-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 бит, а только префиксным группам.

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

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