СПОСОБ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ДАННЫХ БЕЗ ПОТЕРЬ
METHOD FOR LOSSLESS DATA COMPRESSION AND RETRIEVAL

Изобретение относится к области, связанной с сокращением избыточности передаваемой и хранимой информации, и может быть использовано для сжатия и восстановления без потерь цифровых данных в информационных системах и системах электросвязи.
2
Основы теории информации были заложены К. Шенноном в 1948 году в своей пионерской работе по теории информации (Д. Сэломон, «Сжатие данных, изображений и звука«, М.: Техносфера, 2004, стр.25), в которой он ввел понятие энтропии источника. Фундаментальное значение этой величины состоит в том, что она задает нижнюю границу возможного сжатия (Д. Сэломон, «Сжатие данных, изображений и звука», М.: Техносфера, 2004, стр.8). К этой границе можно приближаться сколь угодно близко, с помощью подходящего способа кодирования источника. Под энтропией символа а, имеющего вероятность Р, подразумевается количество информации, содержащейся в а, которая равна: - P·log(P) (Д. Сэломон, «Сжатие данных, изображений и звука», М.: Техносфера, 2004, стр.25).
с
Одним из основных показателей эффективности сжатия является коэффициент сжатия - К, который определяется как:
с
К = Размер выходного потока/размер входного потока.
Различают сжатие без потерь, при котором возможно полностью восстановить исходную информацию, и сжатие с частичной потерей данных, при котором происходит восстановление данных с частичной потерей информации.
Известны статистические способы сжатия и восстановления данных, которые используют статистические свойства сжимаемых данных (Д. Сэломон, «Сжатие данных, изображений и звука«, М.: Техносфера, 2004, стр.25). Под статистическими свойствами понимают вероятность каждого символа в потоке данных. Для нахождения статистических свойств считают количество каждого символа в потоке данных.
1
n
Известен статистический способ сжатия и восстановления данных без потерь с использованием кодов переменной длины (Д. Сэломон, "Сжатие данных, изображений и звука", М.: Техносфера, 2004 г. стр.26), включающий выбор алфавита - набора символов от a до a, сбор статистики - подсчет количества каждого символа в сжимаемом потоке данных и вычисление вероятностей каждого символа алфавита в сжимаемом потоке данных, составление кодов переменной длины и замену исходных символов кодами переменной длины, при этом часто встречающимся символам присваивают короткие коды, а редко встречающимся - длинные. Для восстановления первоначального потока данных в соответствии с построенными кодами переменной длины заменяют коды переменной длины на исходные символы алфавита. Наиболее известным из способов кодирования кодами переменной длины является способ Хаффмана (Д. Сэломон, "Сжатие данных, изображений и звука", М.: Техносфера, 2004, стр.30).
Недостатками известного способа является то, что:
- максимальное сжатие достигается, если вероятности символов равны отрицательным степеням числа 2;
- различные длины кодовых слов приводят к неравномерным задержкам при восстановлении данных;
- способ неэффективен, если символы алфавита имеют близкие вероятности;
- способ неприменим в случае использования двухсимвольного алфавита.
Известен также статистический способ сжатия и восстановления данных без потерь под названием арифметическое кодирование (Д.Сэломон, "Сжатие данных, изображений и звука", М.: Техносфера, 2004, стр.63), принятый за прототип, который включает:
- сбор статистики о сжимаемом потоке данных, то есть подсчет в сжимаемом потоке данных количества каждого символа;
- задание «текущего интервала» [0, 1);
- повторение следующих действий для каждого символа входного потока данных;
- разделение текущего интервала на части пропорционально вероятностям каждого символа;
- выбор подинтервала, соответствующего символу, и назначение его новым текущим интервалом.
Когда весь входной поток данных будет обработан, выходом алгоритма объявляется любая точка, которая однозначно определяет текущий интервал и будет записана в виде конечного цифрового кода.
Для декодирования полученной строки цифр в известном способе читают первую цифру кода и в соответствии с значениями таблицы, в которую на этапе сжатия были занесены символы сжимаемого потока данных, частоты и вероятности символов, интервалы, присвоенные символам, определяют первый символ, затем удаляют эффект первого символа из кода с помощью вычитания нижнего конца интервала символа и деления на длину этого интервала. Далее повторяют предыдущую последовательность действий до конца кода.
Способ сжатия и восстановления данных без потерь под названием арифметическое кодирование позволяет сжимать данные до теоретического предела (Д. Сэломон, "Сжатие данных, изображений и звука", М.: Техносфера, 2004, стр.76). Недостатком известного способа является:
- метод неэффективен, если вероятности символов в сжимаемом потоке данных равны или имеют близкие значения, то есть в случаях, когда энтропия потока данных стремится к максимальному значению.
Техническим результатом заявляемого изобретения является:
- повышение степени сжатия данных;
- возможность сжатия данных, ранее подвергнутых сжатию.
1
2
p
1
2
p
c
c
1
2
p
c
1
2
p
1
2
p
Указанный технический результат достигается тем, что в способе сжатия и восстановления данных без потерь, включающем подсчет количества в сжимаемом потоке данных, состоящем из р различных символов, каждого символа и обозначение через n, n…n, согласно изобретению выбирают алгоритм присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из произвольного количества символов и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, затем присваивают конкретному потоку данных из р различных символов в количестве n, n…n в соответствии с выбранным алгоритмом конкретный цифровой код N, после чего присвоенный цифровой код N и количество каждого символа n, n…n сохраняют, а для восстановления потока данных в соответствии с выбранным алгоритмом, присвоенным цифровым кодом N и значениями n, n…n находят конкретную перестановку с повторениями из р различных символов в количестве n, n…n, которая соответствует исходному потоку данных.
1
2
p
1
2
p
c
c
c
1
2
p
c
1
2
p
1
2
p
c
1
2
p
c
1
2
p
c
c
1
2
p
1
2
p
c
1
2
p
1
2
p
Указанный технический результат достигается также тем, что в способе сжатия и восстановления данных без потерь в сжимаемом потоке данных, состоящем из р различных символов, считают количество каждого символа в потоке данных и обозначают через n, n…n, согласно изобретению выбирают алгоритм А присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из произвольного количества символов и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, затем присваивают конкретному потоку данных из р различных символов в количестве n, n…n в соответствии с выбранным алгоритмом А конкретный цифровой код N, после чего считают общее количество символов в цифровом коде N и обозначают его через n, затем выбирают алгоритм В определения значений n, n…n через значение n и новые значения d, d…d и нахождения значений n, n…n через значения n, d, d…d, затем присвоенный цифровой код N и значения d, d…d сохраняют, а для восстановления потока данных считают общее количество символов в цифровом коде N и обозначают его через n, затем в соответствии с выбранным алгоритмом В и значениями d, d…d находят значения n, n…n, после чего в соответствии с выбранным алгоритмом А, кодом N и значениями n, n…n находят конкретную перестановку с повторениями из р различных символов в количестве n, n…n, которая соответствует исходному потоку данных. Способ осуществляют следующим образом.
1
2
p
1
2
p
с
c
1
2
p
В сжимаемом потоке данных, состоящем из р различных символов, считают количество каждого символа в потоке данных и обозначают через n, n…n. Затем выбирают алгоритм присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из произвольного количества символов и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, после чего присваивают конкретному потоку данных из р различных символов в количестве n, n…n в соответствии с выбранным алгоритмом конкретный цифровой код N, присвоенный цифровой код N и количество каждого символа n, n…n сохраняют.
c
c
1
2
p
c
c
1
2
p
1
2
p
0
1
p
0
1
p
k
0
1
p
0
1
p
0
1
p
0
p
k
Возможны различные алгоритмы нахождения N и восстановления исходного потока данных по значениям N, n, n…n, при этом наиболее оптимальным будет алгоритм, которому для нахождения N и для восстановления исходного потока данных по значениям N, n, n…n требуется выполнение наименьшего количества перестановок с повторениями, либо наименьшее количество вычислительных операций. Сжатие данных в заявляемом способе достигается за счет того, что для записи количества перестановок с повторениями из р различных символов в количестве n, n…n, определяемого формулой (n+n…+n)!/n!n!…n! (М. Холл, «Комбинаторика», М.: Мир, 1970, стр.13), требуется всегда меньшее количество информации, например бит, в случае использования двухсимвольного алфавита, чем для записи несжатого потока данных, то есть log[(n+n…+n)!/n!n!…n!]<[n+n…+n], где n…n- количество каждого символа от l до р, log - логарифм по основанию k.
c
1
2
p
В случае когда для хранения или передачи значений N и n, n…n требуется меньшее количество информации, чем для хранения или передачи исходного потока данных, достигается указанный технический результат.
c
1
2
p
1
2
p
Для восстановления потока данных в соответствии с выбранным алгоритмом, присвоенным цифровым кодом N и значениями n, n…n находят конкретную перестановку с повторениями из р различных символов в количестве n, n…n, которая соответствует исходному потоку данных.
1
2
p
1
2
p
c
Для реализации способа сжатия и восстановления данных без потерь для сжатия данных, ранее подвергнутых сжатию и имеющих высокую энтропию, в сжимаемом потоке данных, состоящем из р различных символов, считают количество каждого символа в потоке данных и обозначают через n, n…n, затем выбирают алгоритм А присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из произвольного количества символов и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, после чего присваивают конкретному потоку данных из р различных символов в количестве n, n…n в соответствии с выбранным алгоритмом А конкретный цифровой код N.
c
c
1
2
p
c
c
1
2
p
1
2
p
0
1
p
0
1
p
k
0
1
p
0
1
p
0
1
p
0
p
k
Возможны различные алгоритмы нахождения N и восстановления исходного потока данных по значениям N, n, n…n, при этом наиболее оптимальным будет алгоритм, которому для нахождения N и для восстановления исходного потока по значениям N, n, n…n требуется выполнение наименьшего количества перестановок с повторениями либо наименьшее количество вычислительных операций. Сжатие данных в заявляемом способе достигается за счет того, что для записи количества перестановок с повторениями из р различных символов в количестве n, n…n, определяемого формулой (n+n…+n)!/n!n!…n! (М. Холл, «Комбинаторика», М.: Мир, 1970, стр.13), требуется всегда меньшее количество информации, например бит, в случае использования двухсимвольного алфавита, чем для записи несжатого потока данных, то есть log[(n+n…+n)!/n!n!…n!]<[n+n…+n], где n…n - количество каждого символа от l до р, log - логарифм по основанию k.
c
c
1
2
p
c
1
2
p
1
2
p
c
1
2
p
c
1
2
p
Далее считают общее количество символов в цифровом коде N и обозначают его через n, затем выбирают алгоритм В определения значений n, n…n через значение n и новые значения d, d…d и нахождения значений n, n…n через значения n, d, d…d, затем присвоенный цифровой код N и значения d, d…d сохраняют.
1
2
p
c
1
2
p
1
2
p
c
1
2
p
1
2
p
1
2
p
0
1
0
1
c
1
2
p
Возможны различные алгоритмы определения значений n, n…n через значение n и новые значения d, d…d и нахождения значений n, n…n через значения n, d, d…d. Задача этого алгоритма - сократить затраты информации на хранение и передачу значений n, n…n. Поскольку ранее сжатые данные имеют более высокую неупорядоченность по сравнению с несжатыми данными, то есть более высокую энтропию, то во многих случаях n, n…n имеют близкие значения и могут быть сохранены более эффективно, например в случае использования двухсимвольного алфавита значения n, n, где n - количество нулей в потоке данных, n - количество единиц в потоке данных, могут отличаться от n на близкие величины, и хранение новых значений вместо n, n…n будет более оптимальным.
c
c
c
1
2
p
1
2
p
c
1
2
p
1
2
p
Для восстановления потока данных считают общее количество символов в цифровом коде N и обозначают его через n, затем в соответствии с выбранным алгоритмом В и значениями n, d, d…d находят значения n, n…n, после чего в соответствии с выбранным алгоритмом А, кодом N и значениями n, n…n находят конкретную перестановку с повторениями из р различных символов в количестве n, n…n, которая соответствует исходному потоку данных.
Пример 1 конкретного выполнения способа.
0
1
0
1
c
В качестве примера выполнения заявляемого способа сжатия и восстановления данных без потерь с целью наглядности и простоты выбираем двоичный алфавит, состоящий из символов нуль и единица. В сжимаемом двоичном потоке данных, например 000100000000, подсчитывают количество нулей и обозначают это количество через n, подсчитывают количество единиц и обозначают это количество через n. В данном случае n равно одиннадцати, а n равно единице. Затем в соответствии с выбранным алгоритмом конкретному двоичному потоку 000100000000, состоящему из нулей в количестве одиннадцать и одной единицы, присваивают только один неповторяющийся двоичный код N, который не используют для кодирования других двоичных чисел, состоящих из такого же количества нулей и единиц.
c
Для нахождения двоичного числа N могут быть использованы различные алгоритмы, например составляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем вначале помещают все нули, а затем все единицы и этой перестановке присваивают первый порядковый номер - нуль, далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы, результаты перестановок с повторениями и присвоенные порядковые номера в порядке возрастания сохраняют, а перестановки с повторениями осуществляют до тех пор, пока результат перестановок не совпадет с исходным несжатым двоичным потоком данных, или составляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем вначале помещают все единицы, а затем все нули и этой перестановке присваивают первый порядковый номер - нуль, далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы, результаты перестановок с повторениями и присвоенные порядковые номера в порядке убывания сохраняют, а перестановки с повторениями осуществляют до тех пор, пока результат перестановок не совпадет с исходным несжатым двоичным потоком данных.
c
Для данного примера 1 выполнения заявляемого способа сжатия и восстановления данных без потерь выбран следующий алгоритм нахождения числа N. Составляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем вначале помещают все нули, а затем все единицы и этой перестановке присваивают первый порядковый номер - нуль. Далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы. Результаты перестановок с повторениями и присвоенные порядковые номера в порядке возрастания заносят в Таблицу 1. Перестановки с повторениями осуществляют до тех пор, пока результат перестановок не совпадет с исходным несжатым двоичным потоком данных.
Таблица 1
№ п/п
Перестановки с повторениями из одиннадцати нулей и одной единицы
Порядковые номера перестановок с повторениями в двоичном виде
1
2
3
1
000000000001
0
2
000000000010
1
3
000000000100
10
4
000000001000
11
5
000000010000
100
6
000000100000
101
7
000001000000
110
8
000010000000
111
9
000100000000
1000
0
1
c
Далее сохраняют значения n, которое равно в двоичном виде 1011 и занимает четыре бита, n, которое равно в двоичном виде 1 и занимает один бит, а также двоичное число N длиной четыре бита, которое равно в двоичном виде 1000 и содержится в графе 3 строке 9 Таблицы 1 и соответствует порядковому номеру числа перестановок с повторениями из нулей в количестве одиннадцать и одной единицы в потоке данных 000100000000.
Таким образом, для записи исходного несжатого потока данных длиной двенадцать бит необходимо девять бит.
0
1
c
c
Для восстановления первоначального потока данных составляют перестановку длиной n плюс n бит, то есть 12 бит, причем вначале помещают все нули, в данном случае одиннадцать нулей, а затем все единицы, в данном случае одну. Таким образом получают перестановку 000000000001. Далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем результаты перестановок рассматривают как двоичные числа и осуществляют перестановки в порядке их возрастания, а число таких перестановок равно N, результат последней перестановки под номером N будет соответствовать несжатому потоку данных. Восстановленный поток данных представлен в графе 3 строке 9 Таблицы 2.
Таблица 2
№ п/п
Порядковый номер перестановок
Перестановки с повторениями из одиннадцати нулей и одной единицы
1
2
3
1
0
000000000001
2
1
000000000010
3
10
000000000100
4
11
000000001000
5
100
000000010000
6
101
000000100000
7
110
000001000000
8
111
000010000000
9
1000
000100000000
Пример 2 конкретного выполнения способа.
Также существует следующий вариант сжатия потока данных, представленного в примере 1. Составляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем вначале помещают все нули, а затем все единицы и этой перестановке присваивают первый порядковый номер - нуль. Далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы.
Результаты перестановок с повторениями и присвоенные порядковые номера в порядке возрастания заносят в Таблицу 1. Перестановки с повторениями осуществляют до тех пор, пока результат перестановок не совпадет с исходным несжатым двоичным потоком данных.
0
1
c
1
2
Для сохранения сжатых данных выбирают один из возможных алгоритмов определения значений n, n через n и новые значения d, d.
c
0
1
В данном примере для сохранения сжатых данных вместо сохранения значений N, n, n сохраняют следующие значения:
c
N;
1
1
0
c
d=n+n-n;
2
1
0
1
d=(n+n)/2-n.
c
c
1
0
Для восстановления первоначального потока данных считывают общее количество символов в цифровом коде N и обозначают через n. Далее находят значения n и n следующим образом:
1
0
1
c
- n+n=d+n;
1
1
0
2
- n=(n+n)/2-d,
0
1
c
1
- n=d+n-n.
0
1
c
c
Затем составляют перестановку длиной n плюс n бит, то есть 12 бит, причем вначале помещают все нули, в данном случае одиннадцать нулей, а затем все единицы, в данном случае одну. Таким образом получают перестановку 000000000001. Далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем результаты перестановок рассматривают как двоичные числа и осуществляют перестановки в порядке их возрастания, а число таких перестановок равно N, результат последней перестановки под номером N будет соответствовать несжатому потоку данных. Восстановленный поток данных представлен в графе 3 строке 9 Таблицы 2.
В данном варианте реализации способа сжатия и восстановления данных без потерь:
c
c
N=1000, а длина двоичного числа N равна четыре бита;
1
c
1
d=n-n=12-4=8, a длина двоичного числа d пять бита;
2
1
0
1
2
d=(n+n)/2-n=(1+11)/2-1=5; а длина двоичного числа d три бита.
c
1
1
Таким образом, при данном варианте сохранения двоичных чисел для восстановления потока данных будет необходимо 4+5+3=12 бит, то есть для записи результатов способа сжатия потребуется столько же бит, сколько и составляет длина несжатого потока данных. Поэтому для сохранения сжатого потока данных в данном конкретном примере целесообразно хранить непосредственно значения N, n, n.
Таким образом, выбор варианта сохранения результатов сжатия данных зависит от конкретного потока данных и может быть легко определен для конкретного потока данных.
Сравним полученные результаты с теоретическими расчетами, которые позволяют судить о максимально возможном сжатии конкретного потока данных.
2
с
1*
11
В соответствии с теорией (Д. Сэломон, "Сжатие данных, изображений и звука", М.: Техносфера, 2004, стр.26, 75) максимальное сжатие последовательности из одиннадцати нулей и одной единицы, которое теоретически может быть достигнуто с помощью способа арифметического кодирования, составляет log(1/12)(11/12)=5 бит, также понадобится как минимум четыре бита для хранения количества нулей и один бит для хранения количества единиц, которые будут необходимы для восстановления потока данных, всего для сохранения результатов сжатия необходимо минимум 10 бит, а коэффициент сжатия К указанного двоичного потока данных составит:
c(арифметическое кодирование)
K=10/12=0,833.
В примере 1 для записи указанной последовательности потребовалось 9 бит, а коэффициент сжатия указанного потока:
c(заявляемый способ)
K=9/12=0,75.
Таким образом, заявляемый способ превосходит способ арифметического кодирования по степени сжатия.
c
0
1
c
1
2
0
1
15
15
Для иллюстрации преимуществ сохранения не трех двоичных чисел N, n, n, а сохранения значений N, d и d оценим результаты сжатия двоичного потока данных длиной 65536 бит, состоящего из 2=32768 нулей - двоичное число n, и 2=32768 единиц - двоичное число n. Поскольку в данном потоке данных количество единиц и количество нулей одинаково, то данный поток невозможно сжать с помощью способа арифметического кодирования.
Для записи количества перестановок с повторениями из 32768 нулей и 32768 единиц потребуется:
2
0
1
0
1
log[(n+n)!/(n!n!)]=65528 бит.
1
1
0
c
1
2
2
1
0
1
c
0
1
2
c
2
0
2
1
Для записи двоичного числа d=n+n-n=32768+32768-65528=8 потребуется, включая случай, когда двоичное число d равно нулю, log(8+1)=4 бита. Для записи двоичного числа d=(n+n)/2-n=0 потребуется один бит. Таким образом, для записи исходного потока данных потребуется 65528+4+1=65533 бита, что на 3 бита короче, чем исходный несжатый поток данных. Если для записи результатов сжатия сохранять значения N, n, n, то потребуется log(N)+log(n)+log(n)=65528+15+15=65558, что на 22 бита больше, чем исходный поток данных.
Необходимо отметить, что заявляемый способ сжатия и восстановления данных без потерь, учитывая его высокую эффективность с точки зрения степени сжатия данных, в том числе и данных с высокой энтропией, может быть использован для сжатия данных, которые уже подвергались сжатию другими способами. Кроме этого заявляемый способ позволяет многократно сжимать уже сжатые этим же способом данные и в случае, когда затраты на хранение сжатых данных будут меньше, чем исходный несжатый поток данных, применение заявляемого способа будет эффективным.
Заявляемый способ сжатия и восстановления данных без потерь может быть применим для сжатия и последующего восстановления без потерь любых типов данных, например графических файлов, видеофайлов, файлов баз данных и других типов данных. Особенно актуальным может быть применение заявляемого способа в случаях, когда данные необходимо предварительно сжать, причем время, необходимое на сжатие, не является критически важным, а затем передавать по каналам связи уже сжатые данные, в том числе по каналам связи с низкой скоростью передачи данных. В этом случае за счет многократного сжатия данных возможно значительно сократить время, необходимое для передачи больших объемов данных.
Также эффективно применение заявляемого способа для сжатия данных в режиме реального времени. В этом случае сжимаемый поток данных может быть разделен на отрезки известной длины, для сжатия которых заявляемым способом потребуется приемлемое время с учетом использования конкретных вычислительных мощностей.
Для того чтобы ускорить процесс сжатия и восстановления данных в заявляемом способе сжатия и восстановления данных без потерь могут быть использованы алгоритмы, предусматривающие параллельную обработку данных. Применение параллельных механизмов обработки данных также позволит использовать заявляемый способ сжатия и восстановления данных без потерь для сжатия и последующего восстановления данных в режимах реального времени, например, при передаче голосового или видеотрафика в сетях связи.