СПОСОБ СЖАТИЯ ДАННЫХ
METHOD FOR DATA COMPRESSION

Изобретение относится к технике передачи и хранения информации (в цифровом виде) и может использоваться в банках данных и в системах электросвязи, когда необходимо уменьшить время передачи данных по каналу или увеличить длительность элементарных посылок - носителей данных (с целью повышения помехоустойчивости передачи) при сохранении или увеличении скорости создания цифровой информации в источнике сообщений; когда необходимо сократить объём памяти некоторой базы данных или, наоборот, увеличить объём цифровой информации, предназначенной для хранения в существующем устройстве памяти; когда необходимо сжать ширину спектра передаваемых сигналов для уменьшения полосы частот проводного или радиоканала; когда требуется обеспечить скрытность передаваемой или хранящейся в устройстве памяти цифровой информации.
Известно много разных способов сжатия данных (СД). Наиболее близким техническим решением (прототипом) можно считать использование статического словаря в словарных методах СД /1, 2, 3/. Суть этого метода заключается в том, что некоторые последовательности символов - слова (создающие избыточность в сообщениях) - сохраняют в словаре и взаимно однозначно отображают метками (индексами, адресами и т.п.), которые состоят из меньшего числа символов, чем исходные последовательности, и наделены индивидуальными данными, позволяющими при необходимости восстановить конкретную последовательность символов в словаре. Каждое слово (последовательность символов) входного файла, объём (размер) которого предполагается уменьшить (сжать), ищется в словаре. Если этот поиск оказывается успешным, то в выходной файл вместо слова записывается соответствующая словарная метка (индекс, адрес). В противном случае в выходной файл записывается не индекс, а само слово без сжатия.
Статический словарь по составу обычно понимается как постоянный, хотя в него иногда добавляют новые последовательности, но из словаря последовательности никогда не удаляют /2, 3/ (в отличие от динамического (адаптивного) словаря, в котором разрешается и добавление, и удаление данных).
Недостатками разработанных словарных способов СД с применением статического словаря являются их сложная реализация, относительно невысокая эффективность (степень сжатия), привязанность каждого словаря к одному типу (характеру) текста, сравнительно низкая скорость кодирования и декодирования. Словарные методы с использованием динамических словарей обеспечивают несколько более высокую эффективность сжатия, но значительно сложнее в реализации и имеют другие недостатки.
1
1
1
2
1
2
1
cp
cp
Предлагаемый способ сжатия данных (В литературе о сжатии данных в настоящее время имеется множество терминов-«синонимов», вносящих некоторую неоднозначность в те или иные понятия, например: компрессор - кодер, символ - буква, слово - последовательность символов - кодовая комбинация, метки - индексы и т.д. Поэтому в рассматриваемом здесь процессе сжатия и восстановления данных для определённости примем следующее: поток (или некоторый объём) данных разделяется на блоки - входные кодовые комбинации (КК) - с числом разрядов n и основанием кода m, последовательно, один за другим поступающие в кодер (компрессор), в памяти (в статическом словаре) которого содержатся кодовые комбинации КК, представляющие собой полный набор возможных (разных) КК (для современной техники это вполне реально даже при больших значениях n); каждая из входных КК идентифицируется с той или иной КК, а все КК отображаются метками - кодовыми комбинациями КК с меньшим, чем в КК, или таким же числом разрядов. При восстановлении данных в декодере (декомпрессоре) входные КК последовательно преобразуются в КК, выходные КК - блоки, из которых далее формируется требуемый поток (или некоторый объём) данных.) (СД) прост в реализации; повышает скорость кодирования и декодирования; обеспечивает сжатие без потерь; имеет высокую эффективность даже на начальной стадии разработки (при любой реальной последовательности разных двоичных кодовых комбинаций (КК) длиной n, общее число которых равно двум в целой степени n (n=2, 3, 4,…), всегда только две из них оказываются несжатыми, и ими могут быть самые маловероятные последовательности из одних «0» или одних «1»; отношение средней длины n неравномерных кодов в выходном файле к одинаковой длине (n) равномерных кодов во входном файле n/n<1; после реализации любого известного способа СД или нескольких последовательно выполненных таких известных способов, если в результате будет получен поток (объём) данных, допускающий разделение на блоки одинаковой или разной длины, то предлагаемый способ СД всегда может обеспечить дополнительное СД.
Техническим результатом предлагаемого изобретения является: простота в реализации и повышение скорости кодирования и декодирования; уменьшение времени передачи данных по каналу связи при сохранении или увеличении скорости создания цифровой информации в источнике сообщений, что позволяет в том же канале или повысить скорость передачи данных, или увеличить длительность элементарных сигналов и тем самым получить выигрыш в помехоустойчивости передачи; сокращение необходимого объёма памяти некоторой базы данных или, наоборот, увеличение объёма цифровой информации, предназначенной для хранения в существующем устройстве памяти; сжатие ширины спектра передаваемых сигналов (без уменьшения скорости передачи информации) для уменьшения полосы частот проводного или радиоканала; обеспечение скрытности передаваемой или хранящейся в устройстве памяти цифровой информации.
1
2
2
1
2
1
1
1
1
2
2
1
2
1
2
n
Сущность предлагаемого изобретения заключается в том, что, как и в способе-прототипе /1, 2, 3/, последовательности символов (слова, кодовые комбинации КК), предварительно записанные в статическом словаре (в первом блоке памяти кодера), заменяют специальными метками (кодовыми комбинациями КК) из второго блока памяти кодера, но в отличие от указанного способа /1, 2, 3/ эти метки не содержат индивидуальных данных об отображаемых ими конкретных последовательностях символов (до процесса сжатия любой метке КК может быть поставлена в соответствие любая последовательность символов КК, лишь бы в декодере была зафиксирована такая же связь метка - последовательность символов (КК-КК), как и в кодере); кроме того, число таких разных меток может быть столь большим и так мало отличаться от числа разных последовательностей символов, что теряется смысл различать в кодере две категории - метки и слова (КК) без сжатия; поэтому в первый блок памяти кодера предварительно записывают (под именем КК) все (без исключения) возможные (разные) последовательности символов (КК), которые могут возникнуть на входе кодера, и все поступающие при СД в кодер последовательности символов (КК) идентифицируют с одной из КК; в свою очередь каждой КК ставится в соответствие одна из меток - кодовая комбинация КК, совокупность которых представляет собой последовательность групп с полным набором из m m-ичных кодовых комбинаций одинаковой длины n в каждой группе (m - основание кода, m=2, 3, 4,…; число разрядов n=1, 2, 3, …; разрядность кода в группе выравнивается за счёт добавления незначащих символов «0» перед кодовыми комбинациями с числом разрядов меньше n, n=2, 3,…) за исключением последней группы (с выбранным максимальным значением n), которая может быть неполной и в КК которой число разрядов может быть таким же, как в КК; кодовые комбинации КК в разных группах различаются числом разрядов, но могут отличаться или совпадать в численном выражении; в памяти и кодера, и декодера хранятся одинаковые наборы последовательностей символов (или КК) и КК.
2
2
2
1
2
2
2
2
2
2
Поскольку каждая КК характеризуется двумя параметрами - числом раз рядов и численным значением, процесс декодирования (декомпрессии, идентификации входной КК и КК, а затем и КК в памяти декодера) может проводиться в два этапа: 1) выбор в памяти декодера группы из КК с числом разрядов, равным числу разрядов входной КК, 2)определение внутри установленной группы кодовой комбинации КК с численным значением, таким же, как у входной КК. Так как в этом случае отпадает необходимость идентификации входной КК с КК других групп, записанных в памяти декодера, скорость декодирования соответственно повышается.
1
1
Скорость кодирования по сравнению с аналогичной операцией в способе-прототипе тоже увеличивается, так как, во-первых, для каждой метки (в способе-прототипе в случае, например, радикального изменения характера текста метки приходится обновлять) не требуются выбор и анализ соответствующей последовательности символов (создающей избыточность в сообщениях), а также формирование индивидуальных данных; во-вторых, для ускорения процесса идентификации очередной КК с КК в памяти кодера цепь подачи КК в кодер можно разветвить на несколько цепей и соединить их с разными участками, на которые целесообразно разбить всю память КК.
1
2
Если не раскрывать посторонним связи КК-КК в кодере и декодере (а эти связи не сложно время от времени изменять), то можно обеспечить скрытность передаваемой или хранящейся в устройстве памяти цифровой информации.
В /4/ рассмотрен способ сжатия ширины спектра информационных электрических сигналов с ограниченной полосой частот, в основе которого лежит объединение нескольких отсчётов сигнала в один групповой отсчёт. При этом исходные отсчёты представляются двоичными кодовыми комбинациями, и если с помощью предлагаемого способа СД обеспечить сжатие последовательности указанных кодовых комбинаций, то можно объединить в один больше исходных отсчётов и увеличить тем самым сжатие ширины спектра передаваемых сигналов для уменьшения полосы частот проводного или радиоканала.
1
2
Если все кодовые комбинации (КК) на входе кодера, как и все КК, имеют одинаковую длину k, то суммарное число кодовых комбинаций КК с меньшим, чем k, числом разрядов определяется алгоритмом
где основание кода m=2, 3, 4,…, число разрядов k=2, 3, 4… - неотрицательные целые значения, k>i. Если, например, m=2 и k=10, то (см. (1) и табл.1)
10
(2-2)/(2-1)=512+256+128+64+32+16+8+4+2=1022.
1
Это означает, например, что для 1024 последовательностей символов (КК), записанных в словаре, существует 1022 метки с выигрышем в числе символов.
2
Каждое слагаемое в правой части (1) равно числу КК в соответствующей группе и, кроме последнего слагаемого (m), может быть представлено в форме (1).
1
2
Если все КК на входе кодера, как и все КК, имеют одинаковую длину k, то суммарное число кодовых комбинаций КК с таким же числом разрядов k определяется алгоритмом
где основание кода m=2, 3, 4,…, число разрядов k=2, 3, 4… - неотрицательные целые значения. Если, например, m=2 и k=10, то (см. (1) и табл.1)
10
10
2-(2-2)/(2-1)=1024-1022=2.
1
1
1
1
2
1
1
2
2
1
2
1
2
10
10
10
Пример 1. Все кодовые комбинации (КК) на входе кодера, как и КК в памяти кодера, имеют одинаковую длину и состоят из n=10 двоичных разрядов (m=2), т.е. общее число таких КК равно 2=1024; эти КК в произвольном порядке размещены в колонке 1 таблицы 1 (выбран один из [(2)!] возможных вариантов); в колонке 2 приведены десятичные номера КК от 1 до 2=1024; в колонке 3 содержатся двоичные кодовые комбинации КК (метки, индексы, адреса и т.п.) разной длины, взаимно однозначно отображающие соответствующие КК с назначенными им десятичными номерами (заметим, что в отличие от некоторых словарных методов СД роль этих номеров здесь весьма второстепенна: они лишь напоминают, что общее число как КК, так и КК в рассматриваемом примере равно 1024, и ни коим образом не влияют на формирование КК); в колонке 4 указан выигрыш в числе двоичных разрядов - как разность в длине соответствующих КК и КК; в предположении, что все разные 10-разрядные блоки данных поступают на вход устройства СД (кодера) с одинаковой вероятностью Р=1/1024, в колонке 5 указаны суммарные вероятности P выбора КК одинаковой длины (эти же вероятности характеризуют и соответствующие значения выигрыша в числе двоичных разрядов).
cp
2
cp
1
1
2
Для примера 1, когда n=10, определим величину среднего выигрыша V и отношение средней длины КК n к длине КК n. Используя приведённые в таблице 1 вероятности P, а также соответствующие значения выигрыша и размеры (в числе двоичных разрядов - дв.р.) КК имеем
1
20
Пример 2. Все условия аналогичны соответствующим условиям примера 1, но n=20 и общее число КК равно 2=1048576; результаты - в таблице 2,
1
***…* в колонке 1 символизируют «1» и «0» в кодовых комбинациях КК.
1
cp
2
cp
1
В этом примере, как и в предыдущем, когда длина входных КК и КК была вдвое меньше, лишь две комбинации из 1048576 не подверглись сжатию. Определим теперь для примера 2 средний выигрыш V и отношение средней длины КК n к длине КК n. С учётом табл.2, по аналогии с (2) и (3) имеем
2
cp
cp
2
2
Даже если с целью более надёжного разделения комбинаций КК (на стороне декодера) каждую из них (в табл. 2) сопровождать специальной меткой, например паузой, равной длительности сигнала одного двоичного разряда, то n=19,00004, а (n/n)=0,950002<1. Хотя, очевидно, разделение комбинаций КК можно целиком построить на различии сигналов, отображающих следующие один за другим соседние КК.
cp
1
cp
Из сравнения средних выигрышей V в примерах 1 и 2 следует, что вариант, когда длина КК и КК n=10, предпочтительнее, т.к. в этом случае V≈2 приходится на 10, а не на 20 двоичных разрядов.
1
2
1
2
2
В таблицах 1, 2 и в формулах (2)…(5) учтено, что все KK на входе каждого из кодеров равновероятны. В реальных ситуациях указанные КК поступают с разными вероятностями, и если эти вероятности известны или находятся и уточняются в процессе передачи данных, то размещение комбинаций КК относительно КК в табл. 1 и 2 надо изменить так, чтобы, следуя известному методу Хаффмана [1, 2, 3], наиболее вероятным входным КК и соответствующим комбинациям КК назначались самые короткие комбинации КК, а наименее вероятным - самые длинные КК.
1
1
2
4
Пример 3. В отличие от табл.1 и табл.2 в табл.3 принято, что n=4 (т.е. число разных 4-разрядных КК равно 2=16) и выбор (источником) таких комбинаций в одном случае производится с одинаковой вероятностью P=1/16, а в другом случае (P) - согласно методу Хаффмана.
2
При равновероятных входных кодах средняя длина неравномерных кодов КК в выходном файле
отношение
средний выигрыш
2
При разных вероятностях Р:
Таким образом, при учёте разных вероятностей поступления кодовых комбинаций на вход кодера все показатели сжатия данных улучшаются.
Пример 4. Рассмотрим алгоритм и код Хаффмана для английского алфавита /3/ - чертёж.
Средняя длина кода на чертеже (сумма произведений числа разрядов в i-й кодовой комбинации, отображающей соответствующую букву, на вероятность её появления; i = 1, 2, …, 26)
2
2
cp
4
5
В табл.4 указаны те же 26 букв английского алфавита и длины кодов Хаффмана с соответствующими вероятностями их появления (как на чертеже). Но вместо кода Хаффмана использован способ СД с применением КК (см. табл.1, табл.2 и табл.3). Так как число 26 не является целой степенью числа 2 (4<n<5 и соответственно 2<26<2 ), правило (1) не применимо. Расчёт средней длины КК (n) по данным табл.4 выполняется аналогично (9).
Это примерно в 1,8 раз меньше, чем при кодировании по Хаффману (см. (12)).
2
В колонке 5 таблицы 4 приведены значения выигрыша в числе двоичных разрядов (дв.р.) при переходе от кодовых комбинаций Хаффмана (чертёж) к соответствующим КК. С учётом указанных вероятностей выбора букв средняя величина такого выигрыша
cp
V=1·(0,065+0,02+0,02+0,02+0,015+0,015+0,015+0,01)+2·(0,13+0,08++0,08+0,07+0,065+0,06+0,06+0,04+0,035+0,03+0,03+0,03+0,005+0,005+0,005)+3·(0,09+0,0025+0,0025)=0,18+1,51+0,285=1,975 дв.р.
2
Таким образом, выигрыш за счёт применения КК получается как при равномерных, так и при неравномерных входных кодах. При этом средние величины таких выигрышей в обоих случаях очень близки.
Пример 5. Выражения (1) и (1') допускают ситуации, когда m>2.
2
Примем, что m=4, а n=10. Из (1) следует, что в этом случае суммарное число кодовых комбинаций КК с меньшим чем 10 числом разрядов равно
2
Из (1') находим суммарное число кодовых комбинаций КК с числом разрядов, равным 10 (без выигрыша):
1
2
2
1
2
2
В таблице 5 приведены в произвольном порядке 10-разрядные 4-ичные числа - КК (колонка 1), порядковые номера, чтобы ориентироваться в этом множестве чисел (колонка 2), четверичные КК (колонка 3), выигрыш в числе четверичных разрядов при замене входных 10-разрядных КК на КК - эффект при СД (колонка 4) и суммарные вероятности P выбора одной из КК в соответствующей группе КК (колонка 5) при одинаковых (так принимаем) вероятностях Р появления разных КК на входе кодера.
cp
2
cp
1
Данные табл.5 подтверждают результаты, приведённые в (14) и (15). Если при m=2 (см. табл.1, 2 и 3) только две входные КК оказывались после кодера без выигрыша (без сжатия), то при m=4, n=10 (см. (15) и табл.5) число таких КК выросло до 699052, что составляет более 66% от всех КК (1048576). С учётом данных таблицы 5 по аналогии с (2) и (3) определим величину среднего выигрыша V и отношение средней длины КК n к длине КК n:
cp
V=(1/1048576)·(9·4+8·16+7·64+6·256+5·1024+4·4096+3·16384+2·65536+1·262144+0·699052)=(1/1048576)·(36+128+448+1536+5120+16384+49152+131072+262144)=466020/1048576≈0,444 четверичного разряда,
cp
n/n=(1/10)·(1/1048576)·(1·4+2·16+3·64+4·256+5·1024+6·4096+7·16384+8·65536+9·262144+10·699052)=(1/10485760)·(36+192+1024+5120+24576+114688+524288+2359296+6990520)=10019740/10485760≈0,955.
cp
cp
Если полученный средний выигрыш (V>0!) перевести в двоичные разряды, он всё равно оказывается меньше, чем средний выигрыш при m=2 (см. примеры 1…3), но n/n<1 и при m>2.
Источники информации
1. Теория электрической связи: Учебник для вузов. / А.Г.Зюко, Д.Д.Кловский, В.И.Коржик, М.В.Назаров. / Под ред. Д.Д.Кловского. - М.: Радио и связь, 1998. - 432 с.: 204 ил.
2. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: Диалог - МИФИ, 2002.
3. Д.Сэломон. Сжатие данных, изображений и звука. Москва: Техносфера, 2004. - 368 с.
4. Патент на изобретение №2192708. Способ сжатия ширины спектра информационных электрических сигналов с ограниченной полосой частот. Автор: Дороднов Игорь Ливериевич. Москва, 10 ноября 2002 г.
Таблица 3
Иллюстрация сжатия данных при m=2, n=4, одинаковых (P<sub>1</sub>) и разных (Р<sub>2</sub>) вероятностях КК
№№
КК<sub>1</sub>
КК<sub>2</sub>
Выигрыш
P<sub>1</sub>
Р<sub>2</sub>
1
2
3
4
5
6
1
1010
0
3
1/16
0,195
2
0101
1
3
1/16
0,194
3
1011
00
2
1/16
0,098
4
0100
01
2
1/16
0,095
5
1100
10
2
1/16
0,089
6
0111
11
2
1/16
0,087
7
1101
000
1
1/16
0,045
8
0011
001
1
1/16
0,045
9
0110
010
1
1/16
0,035
10
1110
011
1
1/16
0,029
11
1001
100
1
1/16
0,028
12
0010
101
1
1/16
0,025
13
0001
110
1
1/16
0,015
14
1000
111
1
1/16
0,015
15
0000
0000
0
1/16
0,003
16
1111
0001
0
1/16
0,002
Таблица 4
Иллюстрация сжатия данных для английского алфавита
Буквы/дв.р.
Вероят. P<sub>1</sub>
№№
КК2
Выигрыш
1
2
3
4
5
Е/3
0,1300
1
0
2
Т/4
0,0900
2
1
3
А/4
0,0800
3
00
2
O/4
0,0800
4
01
2
N/4
0,0700
5
10
2
R/4
0,0650
6
11
2
I/4
0,0650
7
000
1
Н/5
0,0600
8
001
2
S/5
0,0600
9
010
2
D/5
0,0400
10
011
2
L/5
0,0350
11
100
2
С/5
0,0300
12
101
2
U/5
0,0300
13
110
2
М/5
0,0300
14
111
2
F/5
0,0200
15
0000
1
Р/5
0,0200
16
0001
1
Y/5
0,0200
17
0010
1
R/5
0,0150
18
0011
1
W/5
0,0150
19
0100
1
G/5
0,0150
20
0101
1
V/5
0,0100
21
0110
1
J/6
0,0050
22
0111
2
К/6
0,0050
23
1000
2
Х/6
0,0050
24
1001
2
Q/7
0,0025
25
1010
3
Z/7
0,0025
26
1011
3