Сжатие данных. Основы разработки обеспечивающих подсистем

Основы разработки обеспечивающих подсистем

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

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

Для повышения достоверности данных используются методы их контроля при вводе и передаче.

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

сжатия данных, используемого в архиваторах;

контроля данных при вводе и передаче по каналам связи;

шифрации данных с использованием элементов теории конечных групп и полей;

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

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

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

Обычно символы текста кодируются с помощью ASCII кода, при этом каждое кодослово имеет длину 8 бит, что позволяет представить 256 различных символов. Допустим, что в наших текстах могут встречаться только 32 различных символа. Тогда можно перейти к новому коду, длина кодослов которого составит 5 бит. В качестве кодослова при этом можно использовать двоичную запись целого числа, равного номеру символа в тексте, минус 1.

Пусть алфавит состоит из 4 символов: а, b, с, е. В этом случае можно для нового кодослова ограничиться длиной 2. Сопоставим символу а - 00, b - 01, с - 10, е - 11. Текст «аbbае» закодируем как 0001010011. Способ декодирования текста очевиден. Достаточно разбить двоичную последовательность на пары и использовать словарь для восстановления текста в первоначальном алфавите.

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

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

Серией называют последовательность нулей, которая заканчивается единицей.

Например, последовательность 001011 содержит три серии длиной 3,2 и 1. В качестве кодослова, соответствующего данной серии, выступает её длина. В нашем случае это 3,2,1 или 111001.

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

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

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

Сопоставим символам двоичные последовательности (двоичные кодослова) различной длины, причём символам, которые встречаются чаще, будем сопоставлять более короткие последовательности. Можно надеяться, что после замены символов на кодослова, их общая длина будет меньше, чем соответствующая длина, полученная при кодировании кодословами фиксированной длины. Эти предположения подтверждаются практикой.

Пусть мы имеем алфавит { a,b,c,d }, причём символ. «а» встречается в два раза чаще, чем «b», а «b» в два раза чаще, чем «с» и «d». Составим «а» - 0, «b» - 10, «с» - 110, «d» - 111. Если в кодируемом тексте символ «а» встречается 100 раз, символ «b» - 50 раз, а символы «с» и «d» по 25 раз, то после кодирования получим текст длиной 350 бит. Для кодирования символов кодом с фиксированной длиной кодослова нужно выбрать его длину равной 2. Следовательно, будем иметь при таком кодировании длину в 400 бит.

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

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

Префикс - это любая начальная часть слова. Префиксами слова «это» будут «э», «эт».

Код называется префиксным, если префикс любого кодослова не является кодословом. Код, приведённый выше, является префиксным.

Префиксный код делает процесс декодирования однозначным. Покажем, как это происходит на примере. Воспользуемся кодом, указанным выше, и закодируем текст «abaacd», получив последовательность 01000110111. Декодирование полученной последовательности начнём с первого символа 0. Этот символ декодируется в «а». Следующий символ 1 никак не декодируется. Присоединим к нему следующий символ, получим последовательность 10, которая декодируется в «b». Следующие два символа превращаются в «аа». Комбинации, следующие далее, 1 и 11 никак не декодируются, поскольку им ничего не соответствует. Последовательность 110 трансформируется в символ «с». Аналогично 111 превращается в «d».

Для заданного алфавита может существовать несколько префиксных кодов. Для алфавита из четырёх символов, { f, b, c, d } можно предложить, кроме рассмотренного, и такой префиксный код: «а» - 00, «b» - 01, «c» - 10, «d» - 11.

Естественно поставить вопрос о выборе оптимального префиксного кода. Алгоритм построения оптимального префиксного кода предложил Хаффман.

Дата добавления: 2014-01-13