Способ восстановления искаженных сжатых файлов



Способ восстановления искаженных сжатых файлов
Способ восстановления искаженных сжатых файлов

 


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

Государственное казенное образовательное учреждение высшего профессионального образования Академия Федеральной службы охраны Российской Федерации (Академия ФСО России) (RU)

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

 

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

Формат архива Deflate разработан Филипом В.Кацом и широко используется на практике, например в протоколе HTTP, форматах PNG, ZIP, GZIP и т.д. и является комбинацией метода словарного сжатия LZ77 (Ziv J., Lempel A., «A Universal Algorithm for Sequential Data Compression», IEEE Transactions on Information Theory, Vol.23, No. 3, pp.337-343.) и кодирования Хаффмана (Huffman, D.A., «A Method for the Construction of Minimum Redundancy Codes», Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Number 9, pp.1098-1101).

Известен способ сжатия информации (см. Патент США №5051745, опубл. 24.09.1991), заключающийся в том, что кодируемые строки заменяют ссылками на последовательность символов, расположенных в скользящем окне фиксированной длины, хранящем предыдущий текст сообщения, затем полученные ссылки кодируют по методу Хаффмана или Шеннона-Фано.

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

Известна спецификация формата архива Deflate (см. Deutsch, P., «Deflate Compressed Data Format Specification version 1.3», Aladdin Enterprises, Network Working Group, May 1996, 16 pages), в которой описан способ компрессии и декомпрессии данных.

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

Известно устройство декомпрессии архивов Deflate «Deflate decompressor», осуществляющее декодирование потоков сжатой информации согласно спецификации формата архива Deflate (см. Патент США №8125357 В1, опубл. 22.02.2012).

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

Известен также способ восстановления данных из поврежденных архивов (см. Патент США №76033390 В2, опубл. 13.10.2009), заключающийся в том, что из архива, являющегося хранилищем множества сжатых файлов (напр. Zip-архив), осуществляют восстановление файлов, содержащихся в неповрежденной области архива.

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

Наиболее близким по технической сущности к заявляемому изобретению (прототипом) является способ декомпрессии информации (см. Патент США №7538696 В2, опубл. 26.05.2009), заключающийся в том, что производят считывание сжатых файлов, выделяют сегменты кода LZ77 из входного битового потока посредством их сравнения с заранее заданными кодовыми значениями, вычисляют индекс таблицы поиска по значению сегмента кода LZ77, производят декодирование сегмента кода LZ77 по таблице поиска.

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

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

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

- после выделения сегментов кода LZ77 из входного битового потока осуществляют поиск ошибок в текущем сегменте кода LZ77;

- производят коррекцию последующих сегментов кода LZ77;

- после декодирования сегмента кода LZ77 формируют контекстную модель декодированных данных;

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

- корректируют искажения декодированных данных.

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

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

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

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

Заявленный способ поясняется чертежами, на которых показано:

фиг.1 - обобщенная блок-схема алгоритма способа восстановления искаженных сжатых файлов;

фиг.2 - сравнение результатов имитационного моделирования для способа-прототипа и предлагаемого способа;

Реализация заявленного способа заключается в следующем (Фиг.1). Перед процедурой считывания сжатых файлов осуществляют ввод информации для формирования общей контекстной модели данных (ОКМД) и формируют ОКМД на основе априорной информации или предположениях о типе данных, которые могут содержаться в архивах, например тексты на различных естественных языках, с целью последующих проверок корректности декомпрессии сжатых данных (блоки 1 и 2). Входной блок сжатых данных записывают в буфер входных данных (БВхД) для последующей декомпрессии (блоки 3, 4 и 5). Процедура декомпрессии осуществляется согласно изобретению-прототипу (блоки 6, 8, 9, 10, 12 и 13) за исключением того, что при несоответствии бит сегмента кода LZ77 (СК LZ77) с одним из заранее заданных значений указатель чтения последовательности бит в БВхД смещается на один бит вправо относительно текущей позиции с целью коррекции последующих сегментов кода LZ77 (блоки 7 и 15). Декодированную (разжатую) информацию записывают в буфер восстановления декодированных данных (БВДД) с целью определения наличия, местоположения и коррекции искажения в декодированных данных (блок 11). На основе информации, содержащейся в БВДД (блок 16), формируют контекстную модель декодированных данных (КМДД) (блок 17). Наличие и местоположение искажения (МНИ) определяют согласно формулам (1) и (2) (блок 18):

P = n g n b ,                                                        ( 1 )

I = arg ( max ( i = 0 N P ( i ) ) ) ,                                  ( 2 )

где Р - величина, характеризующая степень схожести контекстов ОКМД и КМДД, ng - количество совпавших контекстов КМДД с контекстами ОКМД и nb - количество не совпавших контекстов КМДД с контекстами ОКМД, i - позиция указателя чтения последовательности символов в БВДД, N - количество символов в БВДД, arg - аргумент функции (arg(f(x))=x), max - максимальное значение функции. Если I=N-1, то искажений в последовательности символов БВДД не обнаружено, содержимое БВДД копируют в буфер выходных данных (БВыхД) и осуществляют вывод информации из БВыхД (блок 25), в противном случае обнаружено искажение на позиции I в БВДД (блоки 19, 20 и 24). Коррекцию искажения осуществляют посредством выполнения следующей последовательности операций (блок 21):

- индексирование символов БВДД по словарю LZ77 (каждому символу, записываемому в БВДД из словаря LZ77, присваивают определенный индекс, который вычисляют по текущему местоположению данного символа в словаре);

- вычисление величины расстояния Евклида D по формуле (3) между каждым контекстом из ОКМД и текущим контекстом КМДД;

- выбор контекста из ОКМД, которому соответствует минимальное расстояние Евклида Dmin,

- замена всех символов в БВДД, соответствующих индексу текущего символа в БВДД, на символы контекста из ОКМД с Dmin.

D = i = 0 n ( s i ( 1 ) s i ( 2 ) ) 2 ,                                                              ( 3 )

где D - расстояния Евклида между символами контекста из ОКМД и КМДД, n - количество символов, содержащихся в контексте (порядок контекста), s(1) - символ контекста ОКМД, s(2) - символ контекста КМДД.

Если искажение в последовательности символов БВДД исправить не удалось (блок 22), то последовательность бит в БВхД сдвигают влево на один бит относительно позиции местоположения искажения (блок 23) и процесс декомпрессии осуществляют заново, в противном случае содержимое БВДД копируют в БВыхД (блок 24) и осуществляют вывод информации из БВыхД (блок 25).

Для сравнения предлагаемого способа со способом-прототипом был проведен эксперимент посредством выполнения программы «ArcRecovery» на ЭВМ, построенной согласно приведенному алгоритму в среде программирования «Visual Studio» и в среде моделирования «MatLab». Результаты проведенного эксперимента сформулированы в виде зависимости процентного соотношения декодированной информации от количества битовых ошибок в сжатых данных (Фиг.2), которая показывает, что применение предлагаемого способа дает выигрыш по минимизации потерь информации при равных условиях (одинаковые входные искаженные сжатые файлы) на 10-15% (в зависимости от выбора порядка контекстов ОКМД и КМДД и типа искажения) по сравнению со способом-прототипом.

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



 

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

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

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

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

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

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

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

Изобретение относится к кодированию параметров без потерь и, в частности, к формированию и использованию правила кодирования для эффективного сжатия параметров. .

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

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

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

Изобретение относится к технологиям кодирования и декодирования видео. Техническим результатом является повышение эффективности кодирования или декодирования за счет сокращения числа контекстов контекстно-адаптированного бинарного арифметического кодирования (CABAC), которое используется для одного или нескольких синтаксических элементов. Предложен способ кодирования видеоданных. Способ включает в себя этап, на котором определяют первый тип предсказания для блока видеоданных в Р сегменте и представляют первый тип предсказания как синтаксический элемент типа предсказания Р сегмента. Далее, согласно способу определяют второй тип предсказания для блока видеоданных в B сегменте и представляют второй тип предсказания как синтаксический элемент типа предсказания В сегмента, а также, осуществляют определение бинаризации Р сегмента для синтаксического элемента типа предсказания Р сегмента и осуществляют определение бинаризации В сегмента для синтаксического элемента типа предсказания B сегмента. 8 н. и 32 з.п. ф-лы, 10 ил., 22 табл.

Изобретение относится к области контекстно-адаптивного энтропийного кодирования видеоданных. Технический результат - обеспечение инициализации контекстов процесса кодирования посредством определения значений индексов параметров инициализации. Способ инициализации контекста, используемого для того, чтобы кодировать видеоданные в процессе контекстно-адаптивного энтропийного кодирования, содержит этапы, на которых: определяют первое значение индекса параметра инициализации в качестве x>>4, где x является 8-битовым параметром; определяют второе значение индекса параметра инициализации в качестве x&15, где x является идентичным 8-битовым параметром; определяют один или более параметров инициализации для процесса контекстно-адаптивного энтропийного кодирования на основе первого и второго значений индексов параметров инициализации и инициализируют на основе одного или более параметров инициализации состояние контекста, используемого для того, чтобы кодировать видеоданные в процессе контекстно-адаптивного энтропийного кодирования. 4 н. и 41 з.п. ф-лы, 8 ил.

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