×
27.10.2013
216.012.7b7f

СПОСОБ СЖАТИЯ ДВОИЧНЫХ ДАННЫХ В ВИДЕ СТРУКТУРИРОВАННЫХ ИНФОРМАЦИОННЫХ БЛОКОВ

Вид РИД

Изобретение

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

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

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

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

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

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

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

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

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

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

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

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

По существу предлагается для сжатия двоичных данных в виде структурированных информационных блоков использовать факториальную систему счисления. Структурированные информационные блоки, таким образом, описываются аналитически и представляются в виде однозначно соответствующих им натуральных чисел 0≤i<N, где - двоичный код хm,

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

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 элементов будет иметь длину бит, которая является минимально необходимой длиной для дискретного представления структурированного информационного блока заданного вида.

Способ (фиг.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), представляющие исходный структурированный информационный блок вычислением где - целая часть числа а (наибольшее целое число, не большее а).

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

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

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

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

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

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

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

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

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

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

Способ сжатия двоичных данных в виде структурированных информационных блоков, заключающийся в том, что для входного потока двоичных данных, который содержит символы, представленные битовыми последовательностями одинакового фиксированного размера, производят подсчет частоты повторяемости символов, затем для обозначения часто и редко встречающихся символов входного потока двоичных данных производят соответственно выработку более короткой и более длинной битовых последовательностей, которые объединяют в совокупную битовую последовательность переменного размера, отличающийся тем, что из совокупной битовой последовательности исключают битовые последовательности, соответствующие повторяющимся символам входного потока двоичных данных.
СПОСОБ СЖАТИЯ ДВОИЧНЫХ ДАННЫХ В ВИДЕ СТРУКТУРИРОВАННЫХ ИНФОРМАЦИОННЫХ БЛОКОВ
СПОСОБ СЖАТИЯ ДВОИЧНЫХ ДАННЫХ В ВИДЕ СТРУКТУРИРОВАННЫХ ИНФОРМАЦИОННЫХ БЛОКОВ
СПОСОБ СЖАТИЯ ДВОИЧНЫХ ДАННЫХ В ВИДЕ СТРУКТУРИРОВАННЫХ ИНФОРМАЦИОННЫХ БЛОКОВ
Источник поступления информации: Роспатент

Показаны записи 1-10 из 110.
20.09.2013
№216.012.6d5a

Генератор акустических шумов

Изобретение относится к электронным устройствам и может быть использовано для защиты информации по акустическим каналам. Достигаемым техническим результатом является возможность формирования низкочастотного сигнала с расширенным частотным диапазоном и улучшенными характеристиками...
Тип: Изобретение
Номер охранного документа: 0002493645
Дата охранного документа: 20.09.2013
10.02.2014
№216.012.9fdd

Устройство хранения данных (варианты)

Изобретение относится к вычислительной технике, в частности к средствам защиты от несанкционированного доступа к информации. Технический результат заключается в повышении надежности устройства хранения данных и обеспечении более высокой степени безопасности хранения информации. Устройство...
Тип: Изобретение
Номер охранного документа: 0002506633
Дата охранного документа: 10.02.2014
20.02.2014
№216.012.a3c6

Ампульный химический источник тока

Предложенное техническое решение относится к области электротехники, а именно к резервным химическим источникам тока ампульного типа (АХИТ). Повышение уровня разрядных характеристик АХИТ при безопасности работы и удобстве монтажа является техническим результатом заявленного изобретения....
Тип: Изобретение
Номер охранного документа: 0002507641
Дата охранного документа: 20.02.2014
20.02.2014
№216.012.a3dc

Магнитная система статора

Изобретение относится к области электротехники, в частности к магнитным системам статоров электрических машин постоянного тока и магнитных приводов. Технический результат: повышение магнитного потока магнитной системы статора в заданных габаритах. Магнитная система статора содержит радиально...
Тип: Изобретение
Номер охранного документа: 0002507663
Дата охранного документа: 20.02.2014
10.03.2014
№216.012.aab3

Формирователь кольцевого кода

Изобретение относится к кодирующим устройствам помехоустойчивого кода, обеспечивающим восстановление передаваемой по каналу связи информации после ее искажений под действием помех. Технический результат - формирование на выходе устройства систематического кода, в котором информационные элементы...
Тип: Изобретение
Номер охранного документа: 0002509414
Дата охранного документа: 10.03.2014
10.04.2014
№216.012.b5fa

Способ получения раствора ферроцианида лития

Изобретение может быть использовано для получения растворов ферроцианида лития, который применяется в синтезе нормальных ферроцианидов переходных металлов (Cu, Ni, Co, Zn, Fe и др.) общей формулы Ме[Fe(CN)]. Способ получения раствора ферроцианида лития заключается в использовании сильнокислого...
Тип: Изобретение
Номер охранного документа: 0002512310
Дата охранного документа: 10.04.2014
20.04.2014
№216.012.b921

Радиоэлектронный блок

Изобретение относится к радиоэлектронным блокам пакетного типа, в которых металлические рамки электронных модулей являются частью корпуса радиоэлектронного блока, и может быть использовано при изготовлении радиоэлектронной аппаратуры, реализуемой на основе однотипных электронных модулей,...
Тип: Изобретение
Номер охранного документа: 0002513121
Дата охранного документа: 20.04.2014
27.05.2014
№216.012.cb39

Способ ограничения интенсивности лазерного излучения

Изобретение относится к оптической технике. В способе ограничения интенсивности лазерного излучения (ЛИ), включающем подачу потока лазерного излучения на вход устройства, ограничивающего мощность лазерного излучения, подачу потока ЛИ ведут путем последовательного пропускания потока ЛИ через...
Тип: Изобретение
Номер охранного документа: 0002517791
Дата охранного документа: 27.05.2014
27.05.2014
№216.012.cb3e

Устройство для формирования объемного самостоятельного разряда

Изобретение относится к квантовой электронике. Устройство для формирования объемного самостоятельного разряда (ОСР) содержит разрядную камеру, в которой установлены подключенные к источнику накачки три электродные пары, каждая из которых состоит из пластинчатых профилированных электродов....
Тип: Изобретение
Номер охранного документа: 0002517796
Дата охранного документа: 27.05.2014
20.07.2014
№216.012.de0b

Способ приготовления многокомпонентных газовых смесей

Изобретение относится к приготовлению многокомпонентных газовых смесей и может быть использовано в лазерной технике, химической промышленности, в частности для приготовления смеси из перфторалкилиодида и буферных газов и последующего заполнения различных рабочих емкостей. Способ включает напуск...
Тип: Изобретение
Номер охранного документа: 0002522629
Дата охранного документа: 20.07.2014
Показаны записи 1-10 из 117.
20.09.2013
№216.012.6d5a

Генератор акустических шумов

Изобретение относится к электронным устройствам и может быть использовано для защиты информации по акустическим каналам. Достигаемым техническим результатом является возможность формирования низкочастотного сигнала с расширенным частотным диапазоном и улучшенными характеристиками...
Тип: Изобретение
Номер охранного документа: 0002493645
Дата охранного документа: 20.09.2013
10.02.2014
№216.012.9fdd

Устройство хранения данных (варианты)

Изобретение относится к вычислительной технике, в частности к средствам защиты от несанкционированного доступа к информации. Технический результат заключается в повышении надежности устройства хранения данных и обеспечении более высокой степени безопасности хранения информации. Устройство...
Тип: Изобретение
Номер охранного документа: 0002506633
Дата охранного документа: 10.02.2014
20.02.2014
№216.012.a3c6

Ампульный химический источник тока

Предложенное техническое решение относится к области электротехники, а именно к резервным химическим источникам тока ампульного типа (АХИТ). Повышение уровня разрядных характеристик АХИТ при безопасности работы и удобстве монтажа является техническим результатом заявленного изобретения....
Тип: Изобретение
Номер охранного документа: 0002507641
Дата охранного документа: 20.02.2014
20.02.2014
№216.012.a3dc

Магнитная система статора

Изобретение относится к области электротехники, в частности к магнитным системам статоров электрических машин постоянного тока и магнитных приводов. Технический результат: повышение магнитного потока магнитной системы статора в заданных габаритах. Магнитная система статора содержит радиально...
Тип: Изобретение
Номер охранного документа: 0002507663
Дата охранного документа: 20.02.2014
10.03.2014
№216.012.aab3

Формирователь кольцевого кода

Изобретение относится к кодирующим устройствам помехоустойчивого кода, обеспечивающим восстановление передаваемой по каналу связи информации после ее искажений под действием помех. Технический результат - формирование на выходе устройства систематического кода, в котором информационные элементы...
Тип: Изобретение
Номер охранного документа: 0002509414
Дата охранного документа: 10.03.2014
10.04.2014
№216.012.b5fa

Способ получения раствора ферроцианида лития

Изобретение может быть использовано для получения растворов ферроцианида лития, который применяется в синтезе нормальных ферроцианидов переходных металлов (Cu, Ni, Co, Zn, Fe и др.) общей формулы Ме[Fe(CN)]. Способ получения раствора ферроцианида лития заключается в использовании сильнокислого...
Тип: Изобретение
Номер охранного документа: 0002512310
Дата охранного документа: 10.04.2014
20.04.2014
№216.012.b921

Радиоэлектронный блок

Изобретение относится к радиоэлектронным блокам пакетного типа, в которых металлические рамки электронных модулей являются частью корпуса радиоэлектронного блока, и может быть использовано при изготовлении радиоэлектронной аппаратуры, реализуемой на основе однотипных электронных модулей,...
Тип: Изобретение
Номер охранного документа: 0002513121
Дата охранного документа: 20.04.2014
27.05.2014
№216.012.cb39

Способ ограничения интенсивности лазерного излучения

Изобретение относится к оптической технике. В способе ограничения интенсивности лазерного излучения (ЛИ), включающем подачу потока лазерного излучения на вход устройства, ограничивающего мощность лазерного излучения, подачу потока ЛИ ведут путем последовательного пропускания потока ЛИ через...
Тип: Изобретение
Номер охранного документа: 0002517791
Дата охранного документа: 27.05.2014
27.05.2014
№216.012.cb3e

Устройство для формирования объемного самостоятельного разряда

Изобретение относится к квантовой электронике. Устройство для формирования объемного самостоятельного разряда (ОСР) содержит разрядную камеру, в которой установлены подключенные к источнику накачки три электродные пары, каждая из которых состоит из пластинчатых профилированных электродов....
Тип: Изобретение
Номер охранного документа: 0002517796
Дата охранного документа: 27.05.2014
20.07.2014
№216.012.de0b

Способ приготовления многокомпонентных газовых смесей

Изобретение относится к приготовлению многокомпонентных газовых смесей и может быть использовано в лазерной технике, химической промышленности, в частности для приготовления смеси из перфторалкилиодида и буферных газов и последующего заполнения различных рабочих емкостей. Способ включает напуск...
Тип: Изобретение
Номер охранного документа: 0002522629
Дата охранного документа: 20.07.2014
+ добавить свой РИД