Файл: Методы кодирования данных (позволяющие выполнять шифрование).pdf

После десятилетия внедрения tar формат ZIP также появился в мире MS-DOS в качестве формата архива, поддерживающего сжатие. Самым распространенным методом сжатия, используемым в ZIP, является deflate, который представляет собой не что иное, как реализацию алгоритма LZ77. Но формат ZIP-файла, разработанный PKWARE для коммерческих целей, годами сталкивался с препятствиями для патентов. Формат gzip был создан для реализации алгоритма LZ77 в свободном программном обеспечении без нарушения каких-либо патентов PKWARE, который использовался только для сжатия файлов. Таким образом, чтобы создать сжатый архивный файл, сначала необходимо создать архивный файл, используя, например, утилиту tar, затем сжать этот архивный файл и получить файл tar.gz (иногда сокращенно .tgz).

tar-файл – это обычный архивный файл, в котором данные находятся не в сжатом виде. Другими словами, при создании tar из 100 файлов размером 50 КБ можно получить архив, размер которого составит около 5000 КБ. Единственный выигрыш, который можно ожидать при использовании только формата tar, – это предотвращение потери используемой памяти файловой системой, поскольку большинство из них выделяют пространство с определенной степенью детализации (например, в некоторых системах однобайтовый файл использует 4 КБ дискового пространства, 1000 из них потребуют 4 МБ, но соответствующий архив tar просто требует 1 МБ) [17.].

По мере развития компьютерных наук было разработано еще несколько алгоритмов для достижения более высокой степени сжатия. Например, алгоритм Барроуза-Уилера, используемый в bzip2 (сокращение с tar.bz2 архива), или популярный в последнее время Timesxz, который реализует алгоритм LZMA, используемый в утилите 7zip.

Tar поддерживает множество программ сжатия, таких как gzip, bzip2, lzip, lzma, lzop, xz. Из них gzip, вероятно, наиболее широко используемый инструмент хранения, используемый в системах Unix и Linux. Для сжатия данных используется алгоритм Лемпеля-Зива (LZ77).

Формат gzip использует технику сжатия, известную как Deflate. Этот алгоритм также используется в некоторых других популярных технологиях, таких как формат файла изображения PNG, веб-протокол HTTP и протокол защищенной оболочки SSH. Одним из главных его преимуществ является скорость. Он может сжимать, а также распаковывать данные с гораздо большей скоростью, чем другие конкурирующие технологии, особенно при сравнении самых компактных форматов сжатия этих утилит. Он также очень эффективен с точки зрения использования памяти во время сжатия и распаковки, и не требует памяти при оптимизации для наилучшего сжатия. В то время как gzip использует алгоритм Deflate, bzip2 является реализацией алгоритма Берроуза-Уилера.

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

Утилиты сжатия xz влияют на алгоритм сжатия [11.], известный как LZMA2. Этот алгоритм имеет большую степень сжатия по сравнению с двумя приведенными выше примерами, и это предпочтительный формат, когда требуется хранить данные на ограниченном дисковом пространстве. Он дает сравнительно меньшие файлы, что снова приводит к тем же нюансам, которые есть у bzip2. В то время как сжатые файлы, которые создает xz, меньше, чем у других инструментов, для сжатия требуется значительно больше времени. У утилиты сжатия xz также больше требований к памяти, иногда она на порядок выше, чем у других утилит. При работе в системе с достаточным объемом памяти, это может не быть значительной проблемой, но стоит подумать над этим нюансом.

Основное отличие между этими форматами состоит в том, что bzip2 использует алгоритм сжатия текста с сортировкой блоков алгоритмом Берроуза-Уилера в сочетании с кодированием Хаффмана вместо алгоритма LZ77, который используется в gzip. Техника сжатия bzip2 дает более эффективное сжатие, чем gzip, однако метод сжатия bzip2 обычно является более сложным и занимает больше времени (т.е. использует больше циклов ЦП), чем сжатие gzip [17.].

Формат RAR использует необязательное шифрование AES, которое является типом блочного шифра и задействует алгоритм, который шифрует данные в каждом блоке. Существуют различные типы стандартов AES и реализаций, используемых RAR, которые меняются в зависимости от версии. RAR5 (текущая версия) использует AES-256, а не AES-128, используемый в RAR4 [18.]. Формат RAR стал более популярным с годами по сравнению с конкурирующими форматами архивов, такими как 7Z, zip и т. д., поскольку он имеет более высокую скорость сжатия данных, чем ZIP, и использует метод сжатия без потерь [19.].

Что касается .jpg, .mp3, .mp4 и подобных им форматов, то практически общеизвестно, что это сжатые файлы данных. Менее известным является тот факт, что все они используют деструктивное сжатие. Это означает, что невозможно воспроизвести точно такое же изображение после технологии сжатия JPEG. Из-за этого обстоятельства сжатие изображений JPEG или файлов MP3 / MP4 не принесет значительных результатов.

На сегодняшний день есть возможность свободно использовать любой формат файла архива как в Linux, так и в Windows. Но формат файла zip имеет встроенную поддержку в Windows, и это особенно используется в кроссплатформенных средах. Также можно обнаружить формат файла zip в разных местах. Например, он также использовался Sun для JAR-архивов при распространении скомпилированных программ Java или для файлов Open Document (.odf, .odp и т.д.), используемых LibreOffice и некоторыми другими офисными пакетами. Все эти форматы файлов являются ничем иным, как zip-архивами.

Все еще в пользу формата архива tar говорит тот факт, что формат файла zip в полной мере не поддерживает все метаданные файловой системы Unix. По некоторым причинам следует иметь в виду, что формат файла ZIP определяет только ограниченный набор обязательных атрибутов файла: имя файла, дата изменения, разрешения [19.]. Помимо этих основных атрибутов, архиватор может хранить некоторые дополнительные метаданные в дополнительных полях заголовка ZIP-файла, но эти дополнительные поля зависят от реализации, и даже у эффективных архиваторов нет гарантий хранения или извлечения одного и того же набора метаданных.

Алгоритмы сжатия данных

Алгоритм RLE (Run Length Encoding). Основная идея алгоритма RLE состоит в выявления повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения. Несмотря на то, что кодер RLE, как правило, дает очень незначительное сжатие, он может работать очень быстро. А скорость работы декодера RLE вообще близка к скорости простого копирования блока информации. К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

Алгоритмы группы KWE (KeyWord Encoding). В основу алгоритма сжатия по ключевым словам положен принцип кодирования лексических единиц группами байт фиксированной длины. Примером лексической единицы может быть обычное слово. На практике на роль лексических единиц выбираются повторяющиеся последовательности символов, которые кодируются цепочкой символов (кодом) меньшей длины. Результат кодирования помещается в таблице, образовывая так называемый словарь. Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов небольших размеров (за счет необходимости сохранение словаря).

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

Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования.

Сравнение алгоритмов приведено в таблице ниже.

Сравнение алгоритмов сжатия данных

Сравнение алгоритмов сжатия данных (продолжение таблицы)

Теория циклических избыточных кодов

Основные положения

Теория циклических избыточных кодов, несмотря на свое давнее появление (конец 60-х годов XX столетия) по-прежнему остается актуальной. Циклические избыточные коды широко использовались на протяжении десятилетий в компьютерной индустрии для того, чтобы можно было гарантировать правильную запись блоков на дисках и магнитных лентах. Они также широко используются для кодирования и декодирования пакетных ошибок канала связи, где временный сбой может вызвать сразу несколько смежных ошибок данных. Кроме того, циклические избыточные коды принимают участие в механизме встроенного самотестирования (англ. built-in self-testing – BIST) и для тестирования ПЗУ памяти.

Циклический избыточный код (англ. Cyclic Redundancy Check, CRC) – это код проверки ошибок, который широко используется в системах передачи данных и других системах последовательной передачи. CRC представляет собой алгоритм нахождения контрольной суммы, проверяющий целостность данных. Он основан на полиномиальных манипуляциях с использованием модульной арифметики. Некоторыми из распространенных стандартов проверки циклическим избыточным кодом являются CRC-8, CRC-12, CRC-16, CRC-32 и CRC-CCIT.

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

Под контрольной суммой CRC (Cyclic Redundancy Check) понимается некоторое значение, рассчитанное по набору данных путем применения математических алгоритмов, обеспечивающих устойчивость к хэш-коллизиям [7.]. Под хэш-коллизией понимается равенство контрольных сумм для различных входных данных. Контрольные суммы широко применяются для осуществления контроля правильности хранимой и передаваемой информации.

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

Циклические избыточные коды (CRC) являются подклассом блочных кодов и применяются в протоколах HDLC, Token Ring, Token Bus, в семействах протоколов Ethernet и других протоколах канального уровня. Популярность CRC-кодов обусловлена тем, что процедуры кодирования и декодирования достаточно просты и не требуют больших вычислительных ресурсов.

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