Принципы сжатия в обратимых методах

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

Метод RLE (Run-Length Encoding). В основу метода положен принцип выявления повторяющихся последовательностей знаков и замены их простой структурой, в которой указывается код знака и коэффициент повтора. Информация просматривается последовательно знак за знаком. Если выявляется повторяющаяся последовательность знаков, она заменяется одним кодом знака и коэффициентом повторения.

Например, для последовательности знаков (полагаем, что знак хранится в 1 байте памяти), содержащих восьмеричные коды:

000 000 000 127 127 000 255 255 255 255 (всего 10 байтов),

сжатая информация примет вид:

000 003 127 002 000 001 255 004 (всего 8 байтов).

В данном примере коэффициент сжатия информации равен 8/10 = 0.8 - (80%). Т.е. в сжатом виде информация составляет 80% от исходного объема.

Метод KWE (Keyword Encoding). В основу метода положен принцип кодирования лексических единиц исходного документа группами байтов фиксированной длины. В качестве лексической единицы документа рассматривается последовательность символов, справа и слева ограниченная пробелами или символами конца абзаца. Предполагается, что выделяемые в документе в результате анализа структуры документа лексические единицы превышают по размеру комбинацию байтов соответствующего кода. Результаты структурного лексического анализа документа сводятся в таблицу, называемую словарем. Для сжатия исходного документа все выделенные лексические единицы заменяются соответствующими кодами, взятыми из словаря. Словарь добавляется в конец сжатого документа. Результат сжатия содержимого документа вместе со словарём составляет документ в сжатом виде. Для преобразования документа в исходное состояние необходимо коды заменить соответствующими лексическими единицами.

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