способ сжатия данных

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

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

комбинаций КК₂ формируют как последовательность групп с полным набором из mⁿ m-ичных кодовых комбинаций с одинаковым числом разрядов n в каждой группе, где основание кода m=2, 3, 4, , а n=1, 2, 3, ; число разрядов в кодах группы выравнивают за счет добавления незначащих символов «0» перед кодовыми комбинациями с числом разрядов меньше n', n'=2, 3, , за исключением группы с выбранным максимальным значением n, которая может быть неполной и в которой число разрядов может быть таким же, как в кодовых комбинациях КК₁; в результате каждая кодовая комбинация

КК₂ характеризуется двумя параметрами - числом разрядов и численным значением; при числе кодовых комбинаций КК₁, равном mⁿ , число кодовых комбинаций КК₂ с таким же основанием m, но меньшим, чем n, числом разрядов определяют по формуле



где основание кода m=2, 3, 4 , число разрядов n=2, 3, 4 , n>i; а число кодовых комбинаций КК₂ с таким же, как у кодовых комбинаций КК₁, числом разрядов n, определяют соответственно по формуле

,

где также основание кода m=2, 3, 4 , число разрядов n=2, 3, 4 , n>i; при этом каждое слагаемое в правой части (1) равно числу кодовых комбинаций в соответствующей группе и, кроме последнего слагаемого (m), может быть представлено в форме (1).

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

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

Изобретение относится к технике передачи и хранения информации (в цифровом виде) и может использоваться в банках данных и в системах электросвязи, когда необходимо уменьшить время передачи данных по каналу или увеличить длительность элементарных посылок - носителей данных (с целью повышения помехоустойчивости передачи) при сохранении или увеличении скорости создания цифровой информации в источнике сообщений; когда необходимо сократить объём памяти некоторой базы данных или, наоборот, увеличить объём цифровой информации, предназначенной для хранения в существующем устройстве памяти; когда необходимо сжать ширину спектра передаваемых сигналов для уменьшения полосы частот проводного или радиоканала; когда требуется обеспечить скрытность передаваемой или хранящейся в устройстве памяти цифровой информации.

Известно много разных способов сжатия данных (СД). Наиболее близким техническим решением (прототипом) можно считать использование статического словаря в словарных методах СД /1, 2, 3/. Суть этого метода заключается в том, что некоторые последовательности символов - слова (создающие избыточность в сообщениях) - сохраняют в словаре и взаимно однозначно отображают метками (индексами, адресами и т.п.), которые состоят из меньшего числа символов, чем исходные последовательности, и наделены индивидуальными данными, позволяющими при необходимости восстановить конкретную последовательность символов в словаре. Каждое слово (последовательность символов) входного файла, объём (размер) которого предполагается уменьшить (сжать), ищется в словаре. Если этот поиск оказывается успешным, то в выходной файл вместо слова записывается соответствующая словарная метка (индекс, адрес). В противном случае в выходной файл записывается не индекс, а само слово без сжатия.

Статический словарь по составу обычно понимается как постоянный, хотя в него иногда добавляют новые последовательности, но из словаря последовательности никогда не удаляют /2, 3/ (в отличие от динамического (адаптивного) словаря, в котором разрешается и добавление, и удаление данных).

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

Предлагаемый способ сжатия данных (В литературе о сжатии данных в настоящее время имеется множество терминов-«синонимов», вносящих некоторую неоднозначность в те или иные понятия, например: компрессор - кодер, символ - буква, слово - последовательность символов - кодовая комбинация, метки - индексы и т.д. Поэтому в рассматриваемом здесь процессе сжатия и восстановления данных для определённости примем следующее: поток (или некоторый объём) данных разделяется на блоки - входные кодовые комбинации (КК) - с числом разрядов n и основанием кода m, последовательно, один за другим поступающие в кодер (компрессор), в памяти (в статическом словаре) которого содержатся кодовые комбинации КК₁, представляющие собой полный набор возможных (разных) КК (для современной техники это вполне реально даже при больших значениях n); каждая из входных КК идентифицируется с той или иной КК₁, а все КК ₁ отображаются метками - кодовыми комбинациями КК₂ с меньшим, чем в КК₁, или таким же числом разрядов. При восстановлении данных в декодере (декомпрессоре) входные КК₂ последовательно преобразуются в КК₁ , выходные КК - блоки, из которых далее формируется требуемый поток (или некоторый объём) данных.) (СД) прост в реализации; повышает скорость кодирования и декодирования; обеспечивает сжатие без потерь; имеет высокую эффективность даже на начальной стадии разработки (при любой реальной последовательности разных двоичных кодовых комбинаций (КК) длиной n, общее число которых равно двум в целой степени n (n=2, 3, 4, ), всегда только две из них оказываются несжатыми, и ими могут быть самые маловероятные последовательности из одних «0» или одних «1»; отношение средней длины n_cp неравномерных кодов в выходном файле к одинаковой длине (n) равномерных кодов во входном файле n_cp/n<1; после реализации любого известного способа СД или нескольких последовательно выполненных таких известных способов, если в результате будет получен поток (объём) данных, допускающий разделение на блоки одинаковой или разной длины, то предлагаемый способ СД всегда может обеспечить дополнительное СД.

Техническим результатом предлагаемого изобретения является: простота в реализации и повышение скорости кодирования и декодирования; уменьшение времени передачи данных по каналу связи при сохранении или увеличении скорости создания цифровой информации в источнике сообщений, что позволяет в том же канале или повысить скорость передачи данных, или увеличить длительность элементарных сигналов и тем самым получить выигрыш в помехоустойчивости передачи; сокращение необходимого объёма памяти некоторой базы данных или, наоборот, увеличение объёма цифровой информации, предназначенной для хранения в существующем устройстве памяти; сжатие ширины спектра передаваемых сигналов (без уменьшения скорости передачи информации) для уменьшения полосы частот проводного или радиоканала; обеспечение скрытности передаваемой или хранящейся в устройстве памяти цифровой информации.

Сущность предлагаемого изобретения заключается в том, что, как и в способе-прототипе /1, 2, 3/, последовательности символов (слова, кодовые комбинации КК₁), предварительно записанные в статическом словаре (в первом блоке памяти кодера), заменяют специальными метками (кодовыми комбинациями КК₂ ) из второго блока памяти кодера, но в отличие от указанного способа /1, 2, 3/ эти метки не содержат индивидуальных данных об отображаемых ими конкретных последовательностях символов (до процесса сжатия любой метке КК₂ может быть поставлена в соответствие любая последовательность символов КК₁ , лишь бы в декодере была зафиксирована такая же связь метка - последовательность символов (КК₂-КК₁), как и в кодере); кроме того, число таких разных меток может быть столь большим и так мало отличаться от числа разных последовательностей символов, что теряется смысл различать в кодере две категории - метки и слова (КК) без сжатия; поэтому в первый блок памяти кодера предварительно записывают (под именем КК₁) все (без исключения) возможные (разные) последовательности символов (КК), которые могут возникнуть на входе кодера, и все поступающие при СД в кодер последовательности символов (КК) идентифицируют с одной из КК₁; в свою очередь каждой КК₁ ставится в соответствие одна из меток - кодовая комбинация КК ₂, совокупность которых представляет собой последовательность групп с полным набором из mⁿ m-ичных кодовых комбинаций одинаковой длины n в каждой группе (m - основание кода, m=2, 3, 4, ; число разрядов n=1, 2, 3, ; разрядность кода в группе выравнивается за счёт добавления незначащих символов «0» перед кодовыми комбинациями с числом разрядов меньше n, n=2, 3, ) за исключением последней группы (с выбранным максимальным значением n), которая может быть неполной и в КК₂ которой число разрядов может быть таким же, как в КК₁ ; кодовые комбинации КК₂ в разных группах различаются числом разрядов, но могут отличаться или совпадать в численном выражении; в памяти и кодера, и декодера хранятся одинаковые наборы последовательностей символов (или КК₁) и КК ₂.

Поскольку каждая КК₂ характеризуется двумя параметрами - числом раз рядов и численным значением, процесс декодирования (декомпрессии, идентификации входной КК₂ и КК₂, а затем и КК₁ в памяти декодера) может проводиться в два этапа: 1) выбор в памяти декодера группы из КК₂ с числом разрядов, равным числу разрядов входной КК₂, 2)определение внутри установленной группы кодовой комбинации КК₂ с численным значением, таким же, как у входной КК₂. Так как в этом случае отпадает необходимость идентификации входной КК₂ с КК₂ других групп, записанных в памяти декодера, скорость декодирования соответственно повышается.

Скорость кодирования по сравнению с аналогичной операцией в способе-прототипе тоже увеличивается, так как, во-первых, для каждой метки (в способе-прототипе в случае, например, радикального изменения характера текста метки приходится обновлять) не требуются выбор и анализ соответствующей последовательности символов (создающей избыточность в сообщениях), а также формирование индивидуальных данных; во-вторых, для ускорения процесса идентификации очередной КК с КК₁ в памяти кодера цепь подачи КК в кодер можно разветвить на несколько цепей и соединить их с разными участками, на которые целесообразно разбить всю память КК₁.

Если не раскрывать посторонним связи КК₁-КК₂ в кодере и декодере (а эти связи не сложно время от времени изменять), то можно обеспечить скрытность передаваемой или хранящейся в устройстве памяти цифровой информации.

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

Если все кодовые комбинации (КК) на входе кодера, как и все КК₁, имеют одинаковую длину k, то суммарное число кодовых комбинаций КК₂ с меньшим, чем k, числом разрядов определяется алгоритмом

где основание кода m=2, 3, 4, , число разрядов k=2, 3, 4 - неотрицательные целые значения, k>i. Если, например, m=2 и k=10, то (см. (1) и табл.1)

(2¹⁰ -2)/(2-1)=512+256+128+64+32+16+8+4+2=1022.

Это означает, например, что для 1024 последовательностей символов (КК₁), записанных в словаре, существует 1022 метки с выигрышем в числе символов.

Каждое слагаемое в правой части (1) равно числу КК₂ в соответствующей группе и, кроме последнего слагаемого (m), может быть представлено в форме (1).

Если все КК на входе кодера, как и все КК₁, имеют одинаковую длину k, то суммарное число кодовых комбинаций КК₂ с таким же числом разрядов k определяется алгоритмом

где основание кода m=2, 3, 4, , число разрядов k=2, 3, 4 - неотрицательные целые значения. Если, например, m=2 и k=10, то (см. (1) и табл.1)

2¹⁰-(2 ¹⁰-2)/(2-1)=1024-1022=2.

Пример 1. Все кодовые комбинации (КК) на входе кодера, как и КК₁ в памяти кодера, имеют одинаковую длину и состоят из n=10 двоичных разрядов (m=2), т.е. общее число таких КК₁ равно 2¹⁰ =1024; эти КК₁ в произвольном порядке размещены в колонке 1 таблицы 1 (выбран один из [(2¹⁰)!] возможных вариантов); в колонке 2 приведены десятичные номера КК₁ от 1 до 2¹⁰=1024; в колонке 3 содержатся двоичные кодовые комбинации КК₂ (метки, индексы, адреса и т.п.) разной длины, взаимно однозначно отображающие соответствующие КК₁ с назначенными им десятичными номерами (заметим, что в отличие от некоторых словарных методов СД роль этих номеров здесь весьма второстепенна: они лишь напоминают, что общее число как КК₁, так и КК₂ в рассматриваемом примере равно 1024, и ни коим образом не влияют на формирование КК ₂); в колонке 4 указан выигрыш в числе двоичных разрядов - как разность в длине соответствующих КК₁ и КК ₂; в предположении, что все разные 10-разрядные блоки данных поступают на вход устройства СД (кодера) с одинаковой вероятностью Р=1/1024, в колонке 5 указаны суммарные вероятности P₁ выбора КК₂ одинаковой длины (эти же вероятности характеризуют и соответствующие значения выигрыша в числе двоичных разрядов).

Для примера 1, когда n=10, определим величину среднего выигрыша V_cp и отношение средней длины КК₂ n_cp к длине КК₁ n. Используя приведённые в таблице 1 вероятности P₁, а также соответствующие значения выигрыша и размеры (в числе двоичных разрядов - дв.р.) КК₂ имеем

Пример 2. Все условия аналогичны соответствующим условиям примера 1, но n=20 и общее число КК₁ равно 2²⁰=1048576; результаты - в таблице 2,

*** * в колонке 1 символизируют «1» и «0» в кодовых комбинациях КК₁.

В этом примере, как и в предыдущем, когда длина входных КК и КК₁ была вдвое меньше, лишь две комбинации из 1048576 не подверглись сжатию. Определим теперь для примера 2 средний выигрыш V_cp и отношение средней длины КК₂ n_cp к длине КК₁ n. С учётом табл.2, по аналогии с (2) и (3) имеем

Даже если с целью более надёжного разделения комбинаций КК₂ (на стороне декодера) каждую из них (в табл. 2) сопровождать специальной меткой, например паузой, равной длительности сигнала одного двоичного разряда, то n _cp=19,00004, а (n_cp/n)=0,950002<1. Хотя, очевидно, разделение комбинаций КК₂ можно целиком построить на различии сигналов, отображающих следующие один за другим соседние КК₂.

Из сравнения средних выигрышей V_cp в примерах 1 и 2 следует, что вариант, когда длина КК и КК₁ n=10, предпочтительнее, т.к. в этом случае V_cp 2 приходится на 10, а не на 20 двоичных разрядов.

В таблицах 1, 2 и в формулах (2) (5) учтено, что все KK на входе каждого из кодеров равновероятны. В реальных ситуациях указанные КК поступают с разными вероятностями, и если эти вероятности известны или находятся и уточняются в процессе передачи данных, то размещение комбинаций КК₁ относительно КК₂ в табл. 1 и 2 надо изменить так, чтобы, следуя известному методу Хаффмана [1, 2, 3], наиболее вероятным входным КК и соответствующим комбинациям КК₁ назначались самые короткие комбинации КК₂, а наименее вероятным - самые длинные КК₂.

Пример 3. В отличие от табл.1 и табл.2 в табл.3 принято, что n=4 (т.е. число разных 4-разрядных КК₁ равно 2⁴=16) и выбор (источником) таких комбинаций в одном случае производится с одинаковой вероятностью P₁=1/16, а в другом случае (P₂) - согласно методу Хаффмана.

При равновероятных входных кодах средняя длина неравномерных кодов КК₂ в выходном файле

отношение

средний выигрыш

При разных вероятностях Р₂ :

Таким образом, при учёте разных вероятностей поступления кодовых комбинаций на вход кодера все показатели сжатия данных улучшаются.

Пример 4. Рассмотрим алгоритм и код Хаффмана для английского алфавита /3/ - чертёж.

Средняя длина кода на чертеже (сумма произведений числа разрядов в i-й кодовой комбинации, отображающей соответствующую букву, на вероятность её появления; i = 1, 2, , 26)

В табл.4 указаны те же 26 букв английского алфавита и длины кодов Хаффмана с соответствующими вероятностями их появления (как на чертеже). Но вместо кода Хаффмана использован способ СД с применением КК₂ (см. табл.1, табл.2 и табл.3). Так как число 26 не является целой степенью числа 2 (4<n<5 и соответственно 2⁴<26<2⁵ ), правило (1) не применимо. Расчёт средней длины КК₂ (n_cp) по данным табл.4 выполняется аналогично (9).

Это примерно в 1,8 раз меньше, чем при кодировании по Хаффману (см. (12)).

В колонке 5 таблицы 4 приведены значения выигрыша в числе двоичных разрядов (дв.р.) при переходе от кодовых комбинаций Хаффмана (чертёж) к соответствующим КК₂. С учётом указанных вероятностей выбора букв средняя величина такого выигрыша

V _cp=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 дв.р.

Таким образом, выигрыш за счёт применения КК₂ получается как при равномерных, так и при неравномерных входных кодах. При этом средние величины таких выигрышей в обоих случаях очень близки.

Пример 5. Выражения (1) и (1') допускают ситуации, когда m>2.

Примем, что m=4, а n=10. Из (1) следует, что в этом случае суммарное число кодовых комбинаций КК₂ с меньшим чем 10 числом разрядов равно

Из (1') находим суммарное число кодовых комбинаций КК₂ с числом разрядов, равным 10 (без выигрыша):

В таблице 5 приведены в произвольном порядке 10-разрядные 4-ичные числа - КК₁ (колонка 1), порядковые номера, чтобы ориентироваться в этом множестве чисел (колонка 2), четверичные КК₂ (колонка 3), выигрыш в числе четверичных разрядов при замене входных 10-разрядных КК на КК₂ - эффект при СД (колонка 4) и суммарные вероятности P₁ выбора одной из КК₂ в соответствующей группе КК₂ (колонка 5) при одинаковых (так принимаем) вероятностях Р появления разных КК на входе кодера.

Данные табл.5 подтверждают результаты, приведённые в (14) и (15). Если при m=2 (см. табл.1, 2 и 3) только две входные КК оказывались после кодера без выигрыша (без сжатия), то при m=4, n=10 (см. (15) и табл.5) число таких КК выросло до 699052, что составляет более 66% от всех КК (1048576). С учётом данных таблицы 5 по аналогии с (2) и (3) определим величину среднего выигрыша V _cp и отношение средней длины КК₂ n_cp к длине КК₁ n:

V_cp=(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 четверичного разряда,

n_cp /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.

Если полученный средний выигрыш (V _cp>0!) перевести в двоичные разряды, он всё равно оказывается меньше, чем средний выигрыш при m=2 (см. примеры 1 3), но n_cp/n<1 и при m>2.

Источники информации

1. Теория электрической связи: Учебник для вузов. / А.Г.Зюко, Д.Д.Кловский, В.И.Коржик, М.В.Назаров. / Под ред. Д.Д.Кловского. - М.: Радио и связь, 1998. - 432 с.: 204 ил.

2. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: Диалог - МИФИ, 2002.

3. Д.Сэломон. Сжатие данных, изображений и звука. Москва: Техносфера, 2004. - 368 с.

4. Патент на изобретение № 2192708. Способ сжатия ширины спектра информационных электрических сигналов с ограниченной полосой частот. Автор: Дороднов Игорь Ливериевич. Москва, 10 ноября 2002 г.

Таблица 3
Иллюстрация сжатия данных при m=2, n=4, одинаковых (P1 ) и разных (Р2) вероятностях КК
№ №	КК1	КК2	Выигрыш	P1	Р 2
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
Иллюстрация сжатия данных для английского алфавита
Буквы/дв.р.	Вероят. P1	№ №	КК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