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



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

 


Владельцы патента RU 2497277:

Российская Федерация, от имени которой выступает государственный заказчик-Государственная корпорация по атомной энергии "Росатом" (RU)
Федеральное государственное унитарное предприятие "Российский Федеральный ядерный центр-Всероссийский научно-исследовательский институт экспериментальной физики"-ФГУП "РФЯЦ-ВНИИЭФ" (RU)

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

 

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

Известен способ сжатия (см. Лэнгсам И., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ: Пер. с англ. - М.: Мир, 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 элементов, и достигает, таким образом, максимально теоретически возможного сжатия дискретных информационных блоков.

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

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

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

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

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

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

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

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

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



 

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

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

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

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

Изобретение относится к области кодирования/декодирования символа и более конкретно к способу энтропийного кодирования/декодирования, основанному на кодировании по способу Хаффмана и который использует многомерные кодовые слова.

Изобретение относится к вычислительной технике. .
Изобретение относится к вычислительной технике. .

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

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

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

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

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

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

Изобретение относится к технологии кодирования/декодирования звука и, в частности, к способу кодирования/декодирования звука и системе векторного квантования решетчатого типа. Способ включает: разделение коэффициентов звукового сигнала в частотном домене, для которого в множестве поддиапазонов кодирования выполняется модифицированное дискретное косинусное преобразование (МДКП), квантование и кодирование значения огибающей амплитуды в каждом поддиапазоне кодирования для получения кодированных битовых значений этих амплитуд; выполнение распределения битов в каждый поддиапазон кодирования, осуществление нормализации, квантования и кодирования соответственно для векторов в поддиапазоне кодирования малых битовых значений с пирамидальным решетчатым квантованием и для векторов в поддиапазоне кодирования больших битовых значений со сферическим решетчатым квантованием, с целью получения кодированных битовых значений коэффициентов частотного домена; мультиплексирование и упаковку кодированных битовых значений амплитуд и кодированных битовых значений коэффициентов в каждом поддиапазоне кодирования частотного домена и затем их передачу на сторону декодирования. Технический результат - обеспечение хорошего качества кодирования источника голосовой информации путем совмещенного решетчатого векторного квантования с использованием пирамидального решетчатого векторного квантования и сферического решетчатого векторного квантования. 4 н. и 21 з.п. ф-лы, 7 табл., 9 ил.

Изобретение относится к области техники обработки и сжатия цифрового файла, в частности, типа изображения, видео и/или аудио. Техническим результатом является обеспечение высокого качества и меньшего сжатия цифрового файла. Указанный технический результат достигается тем, что предложен способ обработки цифрового файла типа изображений, видео и/или аудио, который содержит фазу для размещения в строку на каждый цветовой слой и/или на каждый аудиоканал цифровых данных любого файла аудио, изображения и видео, фазу сжатия, использующую алгоритм, в котором каждое сжатое значение VCn положения N получается посредством вычитания из значения Vn этого же положения N исходного файла предварительно определенного количества последовательных сжатых значений (VCn-1, VCn-2, …), вычисленных предварительно, и фазу восстановления, использующую алгоритм, в котором каждое восстановленное значение VDn положения N получается посредством добавления к значению VCn этого же положения сжатого файла предварительно определенного количества последовательных сжатых значений (VCn-1 VCn-2, …). 6 з.п. ф-лы, 7 ил.

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

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

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

Группа изобретений относится к обработке данных для выполнения сжатия видео. Технический результат заключается в улучшении способности манипулировать аудио- и видеоносителями, а также в сокращении времени загрузки. В способе осуществляют кодирование множества видеокадров или их частей согласно первому формату кодирования, причем этот первый формат кодирования является оптимизированным для передачи в клиентское устройство по текущему каналу связи, передачу этого множества и его одновременное кодирование согласно второму формату кодирования, причем этот второй формат кодирования имеет сжатое видео относительно более высокого качества и/или меньший коэффициент сжатия, чем первый формат кодирования, сохранение первого множества видеокадров, закодированных во втором формате кодирования, на запоминающем устройстве с обеспечением возможности доступа и воспроизведения к первому множеству видеокадров, закодированных во втором формате кодирования на клиентском устройстве. 3 н. и 15 з. п. ф-лы, 57 ил.

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

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