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

Описание патента на изобретение RU2497277C2

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

Известен способ сжатия (см. Лэнгсам И., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ: Пер. с англ. - М.: Мир, 1989), в котором положение блока закодированных данных относительно начала входного потока информации постоянно меняется, блок скользит по входному потоку информации. При этом используются указатели, которые позволяют делать ссылки на любой элемент в блоке закодированных данных установленного размера, который предшествует текущему элементу входного потока. Если соответствие найдено, текущий элемент заменяется указателем на соответствующий элемент блока закодированных данных. Указатель включает в себя смещение в блоке закодированных данных и длину элемента. Дополнительно в выходной поток записывается непосредственно следующий за совпавшим элементом символ. Затем блок закодированных данных смещается на длину совпавшего элемента плюс один символ и выполняется новый цикл кодирования. Способ позволяет сжимать только сравнительно длинные последовательности.

Недостатком указанного способа является отсутствие существенных результатов при сжатии структурированных информационных блоков. Например, перестановку из 24 символов с использованием данного способа сжатия можно представить в виде 112-битной строки.

Известен способ сжатия (см. Лэнгсам И., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ: Пер. с англ. - М.: Мир, 1989), использующий только частоту появления одинаковых байтов во входном блоке данных и базирующийся на структуре данных бинарного дерева. Часто встречающимся символам входного потока данных ставится в соответствие цепочка битов меньшей длины, а встречающимся редко - цепочка большей длины. За счет применения этого метода для сжатия очень длинных сообщений, которые содержат встречающиеся чрезвычайно редко символы, достигается существенная экономия: степень сжатия может достигать 8. Сказанное справедливо в большей части для текстовых сообщений и сообщений с неравномерной плотностью распределения символов. Указанный способ взят в качестве наиболее близкого аналога заявляемого изобретения.

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

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

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

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

На фиг.1 представлена схема способа сжатия двоичных данных в виде структурированных информационных блоков.

На фиг.2 представлена зависимость длины сжатого информационного блока от количества элементов в структурированном блоке (Ls - длина информационного блока без сжатия, Lpdk - длина информационного блока, сжатого с использованием наиболее близкого аналога разработанного способа сжатия двоичных данных, Lmak - длина информационного блока, сжатого с использованием разработанного способа сжатия двоичных данных в виде структурированных информационных блоков).

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

По существу предлагается для сжатия двоичных данных в виде структурированных информационных блоков использовать факториальную систему счисления. Структурированные информационные блоки, таким образом, описываются аналитически и представляются в виде однозначно соответствующих им натуральных чисел P = C ( x i m ) ( ( N 1 ) i ) ! , 0≤i<N, где C ( x m ) - двоичный код хm, | C ( x i m ) | = log 2 x i m .

Длина информационного блока L соответствующего дискретного представления структурированного информационного блока равна

L = | P | = | C ( x i m ) i ! | = log 2 N ! , 0≤i≤N.

Сжатое численное представление Р структурированного информационного блока из N элементов может принимать N! значений от 0 для случая, когда блок представлен минимальными численными значениями элементов из допустимых множеств, т.е. нулями 0, 0,…, 0, 0

Р=0·(N-1)!+0·(N-2)!+…+0·1!+0·0!=0,

до (N!-1) для случая, когда блок представлен максимальными численными значениями элементов из допустимых множеств, т.е. (N-1), (N-2),…, 1, 0

Р=(N-1)·(N-1)!+(N-2)·(N-2)!+…+1·1!+0·!=(N!-(N-1)!)+((N-1)!-(N-2!)+…+(2·2!-1·1!)=N!-1.

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

Способ (фиг.1) включает в себя следующие процедуры преобразования:

- упаковка произвольного структурированного информационного блока (x0, x1,…, хN-1) (процедура преобразования несжатого блока в сжатую форму);

- распаковка предварительно упакованного структурированного информационного блока Р (процедура преобразования сжатой формы блока в несжатую).

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

Структурированные информационные блоки представляются последовательностью модифицированных численных значений одинакового фиксированного размера (хm0, xm1,…, xmN-1). Затем производят подсчет частоты повторяемости символов, при этом для обозначения часто и редко встречающихся символов входного потока двоичных данных производят соответственно выработку более короткой и более длинной битовых последовательностей вида Si=xim·((N-1)-i)!. Полученные последовательности объединяют в совокупную битовую последовательность переменного размера структурированного информационного блока Р суммированием слагаемых Si. При этом исключаются битовые последовательности, соответствующие повторяющимся символам входного потока двоичных данных.

Процедура распаковки предварительно упакованного структурированного информационного блока осуществляется следующим образом.

Формируются остатки от деления вида Di=Di-1mod(N-i)!, D0=P, представляющие собой более короткую и более длинную битовые последовательности, соответствующие часто и редко встречающимся символам входного потока двоичных данных, из которых формируются фиксированные последовательности модифицированных численных значений (xm0, xm1,…, xmN-1), представляющие исходный структурированный информационный блок вычислением x i m = ( D i / ( N 1 ) i ) ! , где a - целая часть числа а (наибольшее целое число, не большее а).

На фиг.2 и фиг.3 представлены соответственно графики зависимостей длины сжатого информационного блока от количества элементов в структурированном информационном блоке и достигаемой степени сжатия от количества элементов в структурированном информационном блоке.

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

Важными свойствами способа являются:

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

- относительно высокая скорость сжатия и восстановления, связанная с невысокой сложностью этих процедур;

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

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

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

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

Реализация данного способа сжатия подтвердила осуществимость и практическую ценность заявляемого способа.

Похожие патенты RU2497277C2

название год авторы номер документа
Способ неадаптивного непрерывного сжатия кадров телеметрических данных 2023
  • Богачев Илья Владимирович
  • Левенец Алексей Викторович
  • Чье Ен Ун
RU2823120C1
СПОСОБ ФОРМИРОВАНИЯ ИДЕНТИФИКАЦИОННЫХ ПРИЗНАКОВ ДЛЯ ГРУППЫ ОБЪЕКТОВ 2019
  • Волков Константин Олегович
  • Мартынов Александр Петрович
  • Мартынова Инна Александровна
  • Николаев Дмитрий Борисович
  • Николаева Ирина Александровна
  • Фомченко Виктор Николаевич
RU2700401C1
СПОСОБ ДИНАМИЧЕСКОГО ПРЕОБРАЗОВАНИЯ ДАННЫХ ПРИ ХРАНЕНИИ И ПЕРЕДАЧЕ 2019
  • Волков Константин Олегович
  • Мартынов Александр Петрович
  • Мартынова Инна Александровна
  • Николаев Дмитрий Борисович
  • Николаева Ирина Александровна
  • Фомченко Виктор Николаевич
RU2699589C1
УСТРОЙСТВО ДЛЯ МНОГОУРОВНЕВОГО КОДИРОВАНИЯ 2019
  • Исджан, Онурджан
  • Бенке, Рональд
  • Сюй, Вэнь
RU2801163C1
Способ сжатия телеметрических кадров данных 2018
  • Богачев Илья Владимирович
  • Левенец Алексей Викторович
  • Чье Ен Ун
RU2697794C1
СПОСОБ АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ С ШИФРОВАНИЕМ 2017
  • Агеева Нина Сергеевна
  • Дворников Сергей Викторович
  • Оков Игорь Николаевич
  • Устинов Андрей Александрович
RU2656713C1
СПОСОБ АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ С ШИФРОВАНИЕМ 2015
  • Васильев Владимир Борисович
  • Оков Игорь Николаевич
  • Стрежик Юрий Николаевич
  • Устинов Андрей Александрович
  • Швецов Николай Валерьевич
RU2595953C1
СПОСОБ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ЦИФРОВОЙ ИНФОРМАЦИИ В ВИДЕ УЛЬТРАСЖАТОГО НАНОБАР-КОДА (ВАРИАНТЫ) 2013
  • Пряхин Евгений Иванович
  • Ларионова Екатерина Владимировна
  • Захаренко Евгений Анатольевич
RU2656734C2
СПОСОБ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ИНФОРМАЦИИ НА ОСНОВЕ ЗАПРЕТА ОПРЕДЕЛЕННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДАННЫХ 2012
  • Скидин Антон Сергеевич
  • Федорук Михаил Петрович
RU2491716C1
СПОСОБ СЖАТИЯ ПОСЛЕДОВАТЕЛЬНОСТИ ИНФОРМАЦИОННЫХ СИГНАЛОВ 1993
  • Железцов Д.А.
  • Железцов А.В.
RU2080738C1

Иллюстрации к изобретению RU 2 497 277 C2

Реферат патента 2013 года СПОСОБ СЖАТИЯ ДВОИЧНЫХ ДАННЫХ В ВИДЕ СТРУКТУРИРОВАННЫХ ИНФОРМАЦИОННЫХ БЛОКОВ

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

Формула изобретения RU 2 497 277 C2

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

Документы, цитированные в отчете о поиске Патент 2013 года RU2497277C2

US 7224293 B2, 29.05.2007
RU 2007127167 A, 27.01.2009
RU 2008139888 A, 20.04.2010
Станок для изготовления деревянных ниточных катушек из цилиндрических, снабженных осевым отверстием, заготовок 1923
  • Григорьев П.Н.
SU2008A1
СИСТЕМА КОДИРОВАНИЯ/ДЕКОДИРОВАНИЯ ВИДЕОИНФОРМАЦИИ 1995
  • Синити Кикути
  • Тетсуя Китамура
  • Хидеки Мимура
  • Казухико Таира
RU2158487C2

RU 2 497 277 C2

Авторы

Мартынов Александр Петрович

Николаев Дмитрий Борисович

Даты

2013-10-27Публикация

2010-07-29Подача