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

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

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

Одним из основных показателей эффективности сжатия является коэффициент сжатия - К_с, который определяется как:

К_с = Размер выходного потока/размер входного потока.

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

Известны статистические способы сжатия и восстановления данных, которые используют статистические свойства сжимаемых данных (Д. Сэломон, «Сжатие данных, изображений и звука«, М.: Техносфера, 2004, стр.25). Под статистическими свойствами понимают вероятность каждого символа в потоке данных. Для нахождения статистических свойств считают количество каждого символа в потоке данных.

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

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

- максимальное сжатие достигается, если вероятности символов равны отрицательным степеням числа 2;

- различные длины кодовых слов приводят к неравномерным задержкам при восстановлении данных;

- способ неэффективен, если символы алфавита имеют близкие вероятности;

- способ неприменим в случае использования двухсимвольного алфавита.

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

- сбор статистики о сжимаемом потоке данных, то есть подсчет в сжимаемом потоке данных количества каждого символа;

- задание «текущего интервала» [0, 1);

- повторение следующих действий для каждого символа входного потока данных;

- разделение текущего интервала на части пропорционально вероятностям каждого символа;

- выбор подинтервала, соответствующего символу, и назначение его новым текущим интервалом.

Когда весь входной поток данных будет обработан, выходом алгоритма объявляется любая точка, которая однозначно определяет текущий интервал и будет записана в виде конечного цифрового кода.

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

Способ сжатия и восстановления данных без потерь под названием арифметическое кодирование позволяет сжимать данные до теоретического предела (Д. Сэломон, "Сжатие данных, изображений и звука", М.: Техносфера, 2004, стр.76). Недостатком известного способа является:

- метод неэффективен, если вероятности символов в сжимаемом потоке данных равны или имеют близкие значения, то есть в случаях, когда энтропия потока данных стремится к максимальному значению.

Техническим результатом заявляемого изобретения является:

- повышение степени сжатия данных;

- возможность сжатия данных, ранее подвергнутых сжатию.

Указанный технический результат достигается тем, что в способе сжатия и восстановления данных без потерь, включающем подсчет количества в сжимаемом потоке данных, состоящем из р различных символов, каждого символа и обозначение через n₁, n₂…n_p, согласно изобретению выбирают алгоритм присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из произвольного количества символов и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, затем присваивают конкретному потоку данных из р различных символов в количестве n₁, n₂…n_p в соответствии с выбранным алгоритмом конкретный цифровой код N_c, после чего присвоенный цифровой код N_c и количество каждого символа n₁, n₂…n_p сохраняют, а для восстановления потока данных в соответствии с выбранным алгоритмом, присвоенным цифровым кодом N_c и значениями n₁, n₂…n_p находят конкретную перестановку с повторениями из р различных символов в количестве n₁, n₂…n_p, которая соответствует исходному потоку данных.

Указанный технический результат достигается также тем, что в способе сжатия и восстановления данных без потерь в сжимаемом потоке данных, состоящем из р различных символов, считают количество каждого символа в потоке данных и обозначают через n₁, n₂…n_p, согласно изобретению выбирают алгоритм А присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из произвольного количества символов и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, затем присваивают конкретному потоку данных из р различных символов в количестве n₁, n₂…n_p в соответствии с выбранным алгоритмом А конкретный цифровой код N_c, после чего считают общее количество символов в цифровом коде N_c и обозначают его через n_c, затем выбирают алгоритм В определения значений n₁, n₂…n_p через значение n_c и новые значения d₁, d₂…d_p и нахождения значений n₁, n₂…n_p через значения n_c, d₁, d₂…d_p, затем присвоенный цифровой код N_c и значения d₁, d₂…d_p сохраняют, а для восстановления потока данных считают общее количество символов в цифровом коде N_c и обозначают его через n_c, затем в соответствии с выбранным алгоритмом В и значениями d₁, d₂…d_p находят значения n₁, n₂…n_p, после чего в соответствии с выбранным алгоритмом А, кодом N_c и значениями n₁, n₂…n_p находят конкретную перестановку с повторениями из р различных символов в количестве n₁, n₂…n_p, которая соответствует исходному потоку данных. Способ осуществляют следующим образом.

В сжимаемом потоке данных, состоящем из р различных символов, считают количество каждого символа в потоке данных и обозначают через n₁, n₂…n_p. Затем выбирают алгоритм присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из произвольного количества символов и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, после чего присваивают конкретному потоку данных из р различных символов в количестве n₁, n₂…n_p в соответствии с выбранным алгоритмом конкретный цифровой код N_с, присвоенный цифровой код N_c и количество каждого символа n₁, n₂…n_p сохраняют.

Возможны различные алгоритмы нахождения N_c и восстановления исходного потока данных по значениям N_c, n₁, n₂…n_p, при этом наиболее оптимальным будет алгоритм, которому для нахождения N_c и для восстановления исходного потока данных по значениям N_c, n₁, n₂…n_p требуется выполнение наименьшего количества перестановок с повторениями, либо наименьшее количество вычислительных операций. Сжатие данных в заявляемом способе достигается за счет того, что для записи количества перестановок с повторениями из р различных символов в количестве n₁, n₂…n_p, определяемого формулой (n₀+n₁…+n_p)!/n₀!n₁!…n_p! (М. Холл, «Комбинаторика», М.: Мир, 1970, стр.13), требуется всегда меньшее количество информации, например бит, в случае использования двухсимвольного алфавита, чем для записи несжатого потока данных, то есть log_k[(n₀+n₁…+n_p)!/n₀!n₁!…n_p!]<[n₀+n₁…+n_p], где n₀…n_p - количество каждого символа от l до р, log_k - логарифм по основанию k.

В случае когда для хранения или передачи значений N_c и n₁, n₂…n_p требуется меньшее количество информации, чем для хранения или передачи исходного потока данных, достигается указанный технический результат.

Для восстановления потока данных в соответствии с выбранным алгоритмом, присвоенным цифровым кодом N_c и значениями n₁, n₂…n_p находят конкретную перестановку с повторениями из р различных символов в количестве n₁, n₂…n_p, которая соответствует исходному потоку данных.

Для реализации способа сжатия и восстановления данных без потерь для сжатия данных, ранее подвергнутых сжатию и имеющих высокую энтропию, в сжимаемом потоке данных, состоящем из р различных символов, считают количество каждого символа в потоке данных и обозначают через n₁, n₂…n_p, затем выбирают алгоритм А присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из произвольного количества символов и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, после чего присваивают конкретному потоку данных из р различных символов в количестве n₁, n₂…n_p в соответствии с выбранным алгоритмом А конкретный цифровой код N_c.

Возможны различные алгоритмы нахождения N_c и восстановления исходного потока данных по значениям N_c, n₁, n₂…n_p, при этом наиболее оптимальным будет алгоритм, которому для нахождения N_c и для восстановления исходного потока по значениям N_c, n₁, n₂…n_p требуется выполнение наименьшего количества перестановок с повторениями либо наименьшее количество вычислительных операций. Сжатие данных в заявляемом способе достигается за счет того, что для записи количества перестановок с повторениями из р различных символов в количестве n₁, n₂…n_p, определяемого формулой (n₀+n₁…+n_p)!/n₀!n₁!…n_p! (М. Холл, «Комбинаторика», М.: Мир, 1970, стр.13), требуется всегда меньшее количество информации, например бит, в случае использования двухсимвольного алфавита, чем для записи несжатого потока данных, то есть log_k[(n₀+n₁…+n_p)!/n₀!n₁!…n_p!]<[n₀+n₁…+n_p], где n₀…n_p - количество каждого символа от l до р, log_k - логарифм по основанию k.

Далее считают общее количество символов в цифровом коде N_c и обозначают его через n_c, затем выбирают алгоритм В определения значений n₁, n₂…n_p через значение n_c и новые значения d₁, d₂…d_p и нахождения значений n₁, n₂…n_p через значения n_c, d₁, d₂…d_p, затем присвоенный цифровой код N_c и значения d₁, d₂…d_p сохраняют.

Возможны различные алгоритмы определения значений n₁, n₂…n_p через значение n_c и новые значения d₁, d₂…d_p и нахождения значений n₁, n₂…n_p через значения n_c, d₁, d₂…d_p. Задача этого алгоритма - сократить затраты информации на хранение и передачу значений n₁, n₂…n_p. Поскольку ранее сжатые данные имеют более высокую неупорядоченность по сравнению с несжатыми данными, то есть более высокую энтропию, то во многих случаях n₁, n₂…n_p имеют близкие значения и могут быть сохранены более эффективно, например в случае использования двухсимвольного алфавита значения n₀, n₁, где n₀ - количество нулей в потоке данных, n₁ - количество единиц в потоке данных, могут отличаться от n_c на близкие величины, и хранение новых значений вместо n₁, n₂…n_p будет более оптимальным.

Для восстановления потока данных считают общее количество символов в цифровом коде N_c и обозначают его через n_c, затем в соответствии с выбранным алгоритмом В и значениями n_c, d₁, d₂…d_p находят значения n₁, n₂…n_p, после чего в соответствии с выбранным алгоритмом А, кодом N_c и значениями n₁, n₂…n_p находят конкретную перестановку с повторениями из р различных символов в количестве n₁, n₂…n_p, которая соответствует исходному потоку данных.

Пример 1 конкретного выполнения способа.

В качестве примера выполнения заявляемого способа сжатия и восстановления данных без потерь с целью наглядности и простоты выбираем двоичный алфавит, состоящий из символов нуль и единица. В сжимаемом двоичном потоке данных, например 000100000000, подсчитывают количество нулей и обозначают это количество через n₀, подсчитывают количество единиц и обозначают это количество через n₁. В данном случае n₀ равно одиннадцати, а n₁ равно единице. Затем в соответствии с выбранным алгоритмом конкретному двоичному потоку 000100000000, состоящему из нулей в количестве одиннадцать и одной единицы, присваивают только один неповторяющийся двоичный код N_c, который не используют для кодирования других двоичных чисел, состоящих из такого же количества нулей и единиц.

Для нахождения двоичного числа N_c могут быть использованы различные алгоритмы, например составляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем вначале помещают все нули, а затем все единицы и этой перестановке присваивают первый порядковый номер - нуль, далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы, результаты перестановок с повторениями и присвоенные порядковые номера в порядке возрастания сохраняют, а перестановки с повторениями осуществляют до тех пор, пока результат перестановок не совпадет с исходным несжатым двоичным потоком данных, или составляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем вначале помещают все единицы, а затем все нули и этой перестановке присваивают первый порядковый номер - нуль, далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы, результаты перестановок с повторениями и присвоенные порядковые номера в порядке убывания сохраняют, а перестановки с повторениями осуществляют до тех пор, пока результат перестановок не совпадет с исходным несжатым двоичным потоком данных.

Для данного примера 1 выполнения заявляемого способа сжатия и восстановления данных без потерь выбран следующий алгоритм нахождения числа N_c. Составляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем вначале помещают все нули, а затем все единицы и этой перестановке присваивают первый порядковый номер - нуль. Далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы. Результаты перестановок с повторениями и присвоенные порядковые номера в порядке возрастания заносят в Таблицу 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

Далее сохраняют значения n₀, которое равно в двоичном виде 1011 и занимает четыре бита, n₁, которое равно в двоичном виде 1 и занимает один бит, а также двоичное число N_c длиной четыре бита, которое равно в двоичном виде 1000 и содержится в графе 3 строке 9 Таблицы 1 и соответствует порядковому номеру числа перестановок с повторениями из нулей в количестве одиннадцать и одной единицы в потоке данных 000100000000.

Таким образом, для записи исходного несжатого потока данных длиной двенадцать бит необходимо девять бит.

Для восстановления первоначального потока данных составляют перестановку длиной n₀ плюс n₁ бит, то есть 12 бит, причем вначале помещают все нули, в данном случае одиннадцать нулей, а затем все единицы, в данном случае одну. Таким образом получают перестановку 000000000001. Далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем результаты перестановок рассматривают как двоичные числа и осуществляют перестановки в порядке их возрастания, а число таких перестановок равно N_c, результат последней перестановки под номером N_c будет соответствовать несжатому потоку данных. Восстановленный поток данных представлен в графе 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. Перестановки с повторениями осуществляют до тех пор, пока результат перестановок не совпадет с исходным несжатым двоичным потоком данных.

Для сохранения сжатых данных выбирают один из возможных алгоритмов определения значений n₀, n₁ через n_c и новые значения d₁, d₂.

В данном примере для сохранения сжатых данных вместо сохранения значений N_c, n₀, n₁ сохраняют следующие значения:

N_c;

d₁=n₁+n₀-n_c;

d₂=(n₁+n₀)/2-n₁.

Для восстановления первоначального потока данных считывают общее количество символов в цифровом коде N_c и обозначают через n_c. Далее находят значения n₁ и n₀ следующим образом:

- n₁+n₀=d₁+n_c;

- n₁=(n₁+n₀)/2-d₂,

- n₀=d₁+n_c-n₁.

Затем составляют перестановку длиной n₀ плюс n₁ бит, то есть 12 бит, причем вначале помещают все нули, в данном случае одиннадцать нулей, а затем все единицы, в данном случае одну. Таким образом получают перестановку 000000000001. Далее осуществляют перестановки с повторениями из одиннадцати нулей и одной единицы, причем результаты перестановок рассматривают как двоичные числа и осуществляют перестановки в порядке их возрастания, а число таких перестановок равно N_c, результат последней перестановки под номером N_c будет соответствовать несжатому потоку данных. Восстановленный поток данных представлен в графе 3 строке 9 Таблицы 2.

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

N_c=1000, а длина двоичного числа N_c равна четыре бита;

d₁=n-n_c=12-4=8, a длина двоичного числа d₁ пять бита;

d₂=(n₁+n₀)/2-n₁=(1+11)/2-1=5; а длина двоичного числа d₂ три бита.

Таким образом, при данном варианте сохранения двоичных чисел для восстановления потока данных будет необходимо 4+5+3=12 бит, то есть для записи результатов способа сжатия потребуется столько же бит, сколько и составляет длина несжатого потока данных. Поэтому для сохранения сжатого потока данных в данном конкретном примере целесообразно хранить непосредственно значения N_c, n₁, n₁.

Таким образом, выбор варианта сохранения результатов сжатия данных зависит от конкретного потока данных и может быть легко определен для конкретного потока данных.

Сравним полученные результаты с теоретическими расчетами, которые позволяют судить о максимально возможном сжатии конкретного потока данных.

В соответствии с теорией (Д. Сэломон, "Сжатие данных, изображений и звука", М.: Техносфера, 2004, стр.26, 75) максимальное сжатие последовательности из одиннадцати нулей и одной единицы, которое теоретически может быть достигнуто с помощью способа арифметического кодирования, составляет log₂(1/12)^1*(11/12)¹¹=5 бит, также понадобится как минимум четыре бита для хранения количества нулей и один бит для хранения количества единиц, которые будут необходимы для восстановления потока данных, всего для сохранения результатов сжатия необходимо минимум 10 бит, а коэффициент сжатия К_с указанного двоичного потока данных составит:

K_{c(арифметическое кодирование)}=10/12=0,833.

В примере 1 для записи указанной последовательности потребовалось 9 бит, а коэффициент сжатия указанного потока:

K_{c(заявляемый способ)}=9/12=0,75.

Таким образом, заявляемый способ превосходит способ арифметического кодирования по степени сжатия.

Для иллюстрации преимуществ сохранения не трех двоичных чисел N_c, n₀, n₁, а сохранения значений N_c, d₁ и d₂ оценим результаты сжатия двоичного потока данных длиной 65536 бит, состоящего из 2¹⁵=32768 нулей - двоичное число n₀, и 2¹⁵=32768 единиц - двоичное число n₁. Поскольку в данном потоке данных количество единиц и количество нулей одинаково, то данный поток невозможно сжать с помощью способа арифметического кодирования.

Для записи количества перестановок с повторениями из 32768 нулей и 32768 единиц потребуется:

log₂[(n₀+n₁)!/(n₀!n₁!)]=65528 бит.

Для записи двоичного числа d₁=n₁+n₀-n_c=32768+32768-65528=8 потребуется, включая случай, когда двоичное число d₁ равно нулю, log₂(8+1)=4 бита. Для записи двоичного числа d₂=(n₁+n₀)/2-n₁=0 потребуется один бит. Таким образом, для записи исходного потока данных потребуется 65528+4+1=65533 бита, что на 3 бита короче, чем исходный несжатый поток данных. Если для записи результатов сжатия сохранять значения N_c, n₀, n₁, то потребуется log₂(N_c)+log₂(n₀)+log₂(n₁)=65528+15+15=65558, что на 22 бита больше, чем исходный поток данных.

Необходимо отметить, что заявляемый способ сжатия и восстановления данных без потерь, учитывая его высокую эффективность с точки зрения степени сжатия данных, в том числе и данных с высокой энтропией, может быть использован для сжатия данных, которые уже подвергались сжатию другими способами. Кроме этого заявляемый способ позволяет многократно сжимать уже сжатые этим же способом данные и в случае, когда затраты на хранение сжатых данных будут меньше, чем исходный несжатый поток данных, применение заявляемого способа будет эффективным.

Заявляемый способ сжатия и восстановления данных без потерь может быть применим для сжатия и последующего восстановления без потерь любых типов данных, например графических файлов, видеофайлов, файлов баз данных и других типов данных. Особенно актуальным может быть применение заявляемого способа в случаях, когда данные необходимо предварительно сжать, причем время, необходимое на сжатие, не является критически важным, а затем передавать по каналам связи уже сжатые данные, в том числе по каналам связи с низкой скоростью передачи данных. В этом случае за счет многократного сжатия данных возможно значительно сократить время, необходимое для передачи больших объемов данных.

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

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

Изобретение относится к области, связанной с сокращением избыточности передаваемой и хранимой информации, и может быть использовано для сжатия и восстановления без потерь цифровых данных в информационных системах и системах электросвязи. Техническим результатом является повышение степени сжатия данных и возможность сжатия данных, ранее подвергнутых сжатию. Указанный технический результат достигается тем, что в сжимаемом потоке данных считают количество нулей n₀ и количество единиц n₁, выбирают алгоритм присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из n₀ нулей и n₁ единиц и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, присваивают конкретному потоку данных из n₀ нулей и n₁ единиц в соответствии с выбранным алгоритмом цифровой код N_c, считают общее количество символов в цифровом коде N_c n_c, определяют значение d₁, которое равно сумме n₁ и n₀ минус значение n_c, а также значение d₂, которое равно половине разницы значений n₀ и n₁, после чего присвоенный цифровой код N_c и значения d₁ и d₂ сохраняют, а для восстановления потока данных выполняют обратные операции и в соответствии с выбранным алгоритмом по значениям n₀, n₁ и N_c находят конкретную перестановку с повторениями из n₀ нулей и n₁ единиц, которая соответствует исходному потоку данных. 2 табл.

Способ сжатия и восстановления двоичных данных без потерь, согласно которому в сжимаемом потоке данных считают количество нулей и обозначают через n₀ и количество единиц и обозначают через n₁, затем выбирают алгоритм присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из n₀ нулей и n₁ единиц и нахождения в соответствии с присвоенным цифровым кодом и количеством каждого символа соответствующей перестановки с повторениями, затем присваивают конкретному потоку данных из n₀ нулей и n₁ единиц в соответствии с выбранным алгоритмом конкретный цифровой код N_c, отличающийся тем, что считают общее количество символов в цифровом коде N_c и обозначают его через n_c, определяют значения d₁, которое равно сумме n₁ и n₀ минус значение n_c, а также значение d₂, которое равно половине разницы значений n₀ и n₁, после чего присвоенный цифровой код N_c и значения d₁ и d₂ сохраняют, а для восстановления потока данных вначале в соответствии с сохраненными значениями d₁ и d₂, а также вычисляемым значением n_c, которое равно длине цифрового кода N_c, находят значение n₁, которое равно половине суммы значений d₁ и n_c минус значение d₂ и значение n₀, которое, в свою очередь, равно сумме значений d₁ и n_c минус значение n₁, а затем в соответствии с выбранным алгоритмом по значениям n₀, n₁ и N_c находят конкретную перестановку с повторениями из n₀ нулей и n₁ единиц, которая соответствует исходному потоку данных.