Алгоритм KWE

Алгоритм RLE

Алгоритмы сжатия данных без потери информации

ü Метод кодирования длины серий даёт наилучшие результаты, если сжимаемые данные состоят из длинных последовательностей одних и тех же значений (алгоритмы RLE, KWE).

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

[54 слайд]

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

ü Методы кодирования Lempel-Ziv являются наиболее универсальными для сжатия данных общего назначения. Системы кодирования по методу Lempel-Ziv используют технологию кодирования с применением адаптивного словаря. В данном контексте словарь означает набора строительных блоков, из которых создаётся сжатое сообщение. Строительными блоками могут быть символы алфавита, блок данных (нулей и единиц), хранящихся в компьютере.

[55 слайд]

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

Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байтов) образуется следующий вектор:

При записи в строку он имеет вид:

0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов).

В данном примере коэффициент сжатия равен 8/10 (80 %).

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

[56 слайд]

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

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

[57 слайд]