Специальные методы эффективного кодирования

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

Методы эффективного кодирования числовых последовательностей. Различают два метода – разностное кодирование и кодирование повторений.

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

2 14 18 27 34

Первый способ даст последовательность:

2 12 4 9 7.

Этот метод эффективен для медленно меняющихся последовательностей. Его недостаток состоит в том, что для получения значения n-го члена последовательности надо декодировать все предыдущие (n-1) членов.

Второй способ порождает последовательность:

-17 -5 -1 8 15,

поскольку среднее значение для исходной последовательности - 19.

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

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

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

Кодирование повторений заключается в замене цепочки одинаковых цифровых символов самим символом и числом повторений (возможно включение разделителей). Например, для последовательности:

применение этого способа даст последовательность:

5(4)6(4)8(6),

где круглые скобки играют роль разделителей.

Данный метод может быть использован для эффективного кодирования растровых форматов изображений. Растровыми называются форматы изображений, которые получаются во время ввода изображения путем кодирования каждой точки – пиксела (pixel – PIсture ELement) – двумерного пространства, на котором расположено исходное изображение, даже если эта точка не содержит самого изображения. Например, на рисунке

пространство изображения – воображаемый прямоугольник, включающий само изображение функции вместе с осями координат и введенными обозначениями. Очевидно, изображение занимает не все пространство. Тем не менее, кодированию подлежат и «пустоты», при этом те точки, которые содержат изображение, в простейшем случае кодируются двоичной 1, точки без изображения кодируются двоичным 0 (подробнее о восприятии изображений см. далее). В результате получаются числовые последовательности, подобные следующей:

00000000000000000000000000000000000000000000000010000000000000000000.

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

00000000000080000.

Очевидно, к таким последовательностям можно применить метод кодирования повторений. В результате для нашего случая получим (круглые скобки используем как разделители):

0(С)8000,

что означает: 0 повторяется 12 раз (С16 = 12), для остальных символов число повторений не вводится.

Поскольку результирующая последовательность должна также быть шестнадцатеричной, полученное выражение преобразуем следующим образом: заменим круглые скобки соответствующими ASCII-кодами. Тогда открывающей скобке соответствует код 2816, закрывающей – 2916. Получим:

028С2980000.

Длина результата меньше исходной последовательности (11 символов против 17), поэтому получен эффект в 6 символов.

Методы эффективного кодирования словарей. Словари очень часто применяются в современных прикладных программных продуктах, например, при проверке орфографии в текстовом процессоре WinWord. Для их рационального хранения применяются рассмотренные ниже методы.

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

Пусть есть фрагмент словаря со словами:

вычислитель,

вычислительный,

вычислять.

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

вычислитель,

11ный,

6ять,

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

Недостаток данного подхода заключается в необходимости декодировать все (n-1) слов, начиная с базового слова, для декодирования n-го слова словаря.

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

Для нашего примера будут сформированы два словаря:

основной вспомогательный

12ь 1 - вычисл

12ьный 2 - ител

1ять

Методы эффективного кодирования естественно-языковых текстов. Наиболее распространенным и эффективным является адаптивный алгоритм, который в литературе называется также алгоритмом Зива (по имени его разработчика) или алгоритмом с указателями назад (или вперед).

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

Например, пусть задан исходный текст:

«информатика изучает способы обработки информации».

В этом тексте дважды повторяются фрагменты «информа» длиной 7 символов (они выделены жирным стилем). Построим эффективно закодированный текст:

а) с указателями назад. Текст просматривается от начала к концу и специальный механизм определяет, что повторно встречается указанный выше фрагмент. Алгоритм строит адресный указатель взамен этого фрагмента со структурой: количество символов, которые надо отсчитать в обратном направлении к началу первого вхождения фрагмента, и длина фрагмента. Таким образом, для нашего примера имеем текст размером 38 символов:

«информатика изучает способы обработки 38/7ции»,

где знак / играет роль разделителя.

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

Таким образом, для нашего примера имеем текст длиной 31 символ:

«31/7тика изучает способы обработки информации».

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

Поиск по сайту: