Алгоритм RLE. Алгоритмы архивации без потерь

Алгоритмы архивации без потерь.

Критерии сравнения алгоритмов.

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

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

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

Суть алгоритма состоит в том, что сначала вытягивается по строкам растра, а потом повторяющиеся пиксели заменяются парой (счетчик, значение).

В формате PCX это реализовано следующим образом: в выходной поток пишется либо непосредственно значение пикселя (если в двух его старших разрядах не единицы):

[ XX значение ]

либо пара

[ 11 счетчик ] [ что повторять ]

причем повторяемый символ повторяется число раз, на единицу большую счетчика (не имеет смысл повторять 0 раз). Например, строку из 64 повторяющихся байтов мы превратим в два байта. С другой стороны, если в двух старших разрядах пикселя – единицы, и он не повторяется, то мы будем вынуждены записать:

[ 11 000000 ] [ значение ]

то есть, в худшем случае увеличим размер файла в два раза.

Данный алгоритм рассчитан на изображения с большими областями, залитыми одним цветом. В основном на черно-белые.

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

Например цепочка (04,50,00,03,F1,30,60,03,11) распакуется в следующую цепочку (50,50,50,50,F1,30,60,11,11,11). Это позволяет значительно сократить размеры изображений, которые плохо пакуются предыдущим алгоритмом.