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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

название год авторы номер документа
Компрессионный накопитель данных и устройство для его осуществления 2019
  • Бабкин Владимир Андреевич
  • Бабкин Илья Андреевич
  • Бабкин Андрей Владимирович
  • Логачев Александр Ильич
RU2739705C1
СПОСОБ КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ И УСТРОЙСТВО ДЛЯ ЕГО РЕАЛИЗАЦИИ 2012
  • Луценко Андрей Владимирович
RU2503135C1
СПОСОБ КОМПЛЕКСНОЙ ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ ИНФОРМАЦИИ В КОМПЬЮТЕРНЫХ СИСТЕМАХ И СИСТЕМА ДЛЯ ОСУЩЕСТВЛЕНИЯ СПОСОБА 2001
  • Насыпный В.В.
RU2259639C2
Способ формирования ключей шифрования 2016
  • Луценко Андрей Владимирович
RU2656578C1
Способ обнаружения и исправления стираний при приеме дискретной информации 2015
  • Золотарев Валерий Владимирович
RU2611235C1
Система для трансляции с проблемноориентированного языка 1976
  • Сентюрин Вячеслав Михайлович
SU674028A1
СПОСОБ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ЦИФРОВОЙ ИНФОРМАЦИИ В ВИДЕ УЛЬТРАСЖАТОГО НАНОБАР-КОДА (ВАРИАНТЫ) 2013
  • Пряхин Евгений Иванович
  • Ларионова Екатерина Владимировна
  • Захаренко Евгений Анатольевич
RU2656734C2
Устройство для обработки выражений языков программирования 1974
  • Адельсон-Вельский Георгий Максимович
  • Арлазаров Владимир Львович
  • Асратян Рубен Эзрасович
  • Волков Альберт Федорович
  • Деза Валерий Николаевич
  • Диниц Ефим Абрамович
  • Дагурова Наталья Витальевна
  • Емельянов Николай Евгеньевич
  • Зенкина Наталья Георгиевна
  • Лысиков Виктор Тихонович
  • Фараджев Игорь Александрович
SU519715A1
СПОСОБ НАХОЖДЕНИЯ МАКСИМАЛЬНЫХ ПОВТОРЯЮЩИХСЯ УЧАСТКОВ ПОСЛЕДОВАТЕЛЬНОСТИ СИМВОЛОВ КОНЕЧНОГО АЛФАВИТА И СПОСОБ ВЫЧИСЛЕНИЯ ВСПОМОГАТЕЛЬНОГО МАССИВА 2010
  • Грузман Владимир Аронович
  • Алчинов Александр Иванович
  • Иванов Анатолий Витальевич
RU2473960C2
СПОСОБ КОДИРОВАНИЯ КОДА РАЗРЕЖЕННОГО КОНТРОЛЯ ЧЕТНОСТИ 2004
  • Йю Нам-Йюл
  • Ким Мин-Гоо
RU2308803C2

Реферат патента 2017 года Способ сжатия данных

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

Формула изобретения RU 2 628 199 C1

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

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

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

СОСТАВ ТЕПЛОЗАЩИТНОГО ПОКРЫТИЯ ЦИЛИНДРОВОЙ ВТУЛКИ 2000
  • Абачараев М.М.
  • Абачараев И.М.
  • Голубев Д.Г.
  • Хаппалаев А.Ю.
RU2236608C2
СПОСОБ НАХОЖДЕНИЯ МАКСИМАЛЬНЫХ ПОВТОРЯЮЩИХСЯ УЧАСТКОВ ПОСЛЕДОВАТЕЛЬНОСТИ СИМВОЛОВ КОНЕЧНОГО АЛФАВИТА И СПОСОБ ВЫЧИСЛЕНИЯ ВСПОМОГАТЕЛЬНОГО МАССИВА 2010
  • Грузман Владимир Аронович
  • Алчинов Александр Иванович
  • Иванов Анатолий Витальевич
RU2473960C2
СПОСОБ АКТИВАЦИИ КАТАЛИЗАТОРА СИНТЕЗА ФИШЕРА-ТРОПША 2008
  • Хайзер Иоганнес Якобус
  • Беккер Райан
  • Жанс Ван Вуурен Маттис Джозеф
  • Котзе Рино
RU2450044C2
Колосоуборка 1923
  • Беляков И.Д.
SU2009A1
US 5955976 A1, 21.09.1999
СПОСОБ КОНФИГУРИРОВАНИЯ ИНДИКАТОРА ФОРМАТА УПРАВЛЕНИЯ (CFI) МЕЖДУ НЕСУЩИМИ 2011
  • Нг Боон Лоонг
RU2530012C2
US 9100042 B2, 04.08.2015
КОНТЕЙНЕР С АНТИСТАТИЧЕСКИМ СЛОЕМ 2009
  • Дженссон Патрик
RU2530843C2

RU 2 628 199 C1

Авторы

Луценко Андрей Владимирович

Даты

2017-08-15Публикация

2016-06-07Подача