Способ сжатия данных Российский патент 2017 года по МПК H03M7/30 

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

Известен способ сжатия данных [RU 2386210, С2, Н03М 7/40, Н03М 7/46, 10.04.2010], который осуществляется с помощью кодера, причем, в первом блоке памяти кодера хранятся предварительно записанные кодовые комбинации (KK₁) с числом разрядов n, где n=2, 3, 4…, представляющие собой полный набор возможных входных кодовых комбинаций (КК), во втором блоке памяти кодера хранятся предварительно записанные кодовые комбинации КК₂, однозначно соответствующие KK₁, с числом разрядов, меньшим или таким же, как в КК₁, входной поток данных разделяют на КК с одинаковым числом разрядов n, KK последовательно вводят в кодер, идентифицируют путем сравнения с КК₁, отображают соответствующей выходной кодовой комбинацией КК₂, которые представляют собой последовательность групп с одинаковым числом разрядов n в каждой, совокупное число кодовых комбинации КК₂-mⁿ, где m=2, 3, 4…, n=1, 2, 3…, число последовательных групп КК₂ определяют как m^n-1, m^n-2 разрядность КК₂ в группе выравнивают за счет добавления незначащего нуля перед кодовой комбинацией.

Недостатком способа является его относительно высокая сложность.

Кроме того, известен способ сжатия данных [RU 2450441, C1, Н03М 7/30, 10.05.2012], заключающийся в том, что в память целевого устройства записывают промежуточные сжатые данные, извлекают данные из памяти целевого устройства для последующей распаковки, при этом, данные принимают и отдают 128-битными блоками, используют 16 независимых блоков памяти для хранения кэшированных кодирующих структур размером 15-байтной длины и конфигурируют размер кэш-таблицы посредством задания числа ячеек числами, равными степени 2 в пределах от 16 до 4096, при этом предсказывают кодирующие структуры с использованием двух связных буферов упреждающей выборки для построения словаря, кодируют от двух до пятнадцати байт входного потока в один упакованный символ за один такт, используют количество упакованных байт в качестве обратной связи для логики, отвечающей за сдвиг входного потока, выбирают кодирующую структуру за один такт путем поиска кэшированной строки с наиболее длинной совпадающей с входной строкой последовательностью символов, упаковывают данные в 32-байтные группы, выровненные по два байта, упаковывают совпадающие строки в 2-байтный кодирующий символ, состоящий из длины строки, номера блока памяти и значения хэш-функции, определяющего адрес этой строки в блоке памяти.

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

Наиболее близким по технической сущности к предложенному является способ сжатия информации [RU 2431918, С2, Н03М 7/30, 20.10.2011], заключающийся в формировании алфавита сообщения и кодового представления его элементов, при этом, при наличии в сообщении группы нескольких последовательно расположенных символов, находящихся на одной строке или на одном столбце матрицы, данная группа символов образует общий код, состоящий из кода общей строки и кодов столбцов или из кода общего столбца и кодов строк, причем, элементы общего кода группы символов располагают последовательно с выделением кода строки от кодов столбцов или кода столбца от кодов строк по тому или иному признаку: изменение полярности, амплитуды, частоты, фазы электрических сигналов.

Для реализации этого способа предварительно формируют кодовое представление символов исходного сообщения, для чего кодируемые символы размещают в узлах матрицы размерностью m×n при максимальном числе кодируемых символов N=m⋅n, после чего порядковые номера строк и столбцов матрицы представляют в двоичном виде: 000, 001, 010… и т.д. Совокупность кода строки и кода столбца, на пересечении которых расположен символ, есть кодовое представление данного символа.

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

Кроме того, способ предполагает предварительное определение максимального числа кодируемых символов, что ограничивает его применение в общем случае.

Отмеченные недостатки препятствуют оперативному проведению восстановления данных после сжатия.

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

Требуемый технический результат заключается в упрощении способа и повышении универсальности.

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

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

Способ сжатия данных осуществляют следующим образом.

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

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

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

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

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

После этого в регистр сдвига заносится информация, размещаемая непосредственно за последним совпадением в исходном массиве данных.

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

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

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

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

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

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

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