Статьи

Алгоритм недели: сжатие данных с помощью растровых изображений

Февраль 7, 2019

В моем предыдущем посте мы видели, как сжимать данные, состоящие из очень длинных серий повторяющихся элементов. Этот тип сжатия известен как «кодирование длин серий» и может быть очень удобным при передаче данных без потерь. Проблема в том, что данные должны соответствовать определенному формату. Таким образом, строка «aaaaaaaabbbbbbbb» может быть сжата как «a8b8» . Теперь строка длиной 16 может быть сжата как строка длиной 4, что составляет 25% от ее начальной длины без потери какой-либо информации. Будет проблема в случае, если символы (элементы) были распределены по-другому. Что произойдет, если символы будут одинаковыми, но они не образуют длинных трасс? Что если строка «abababababababab»? Та же длина, те же символы, но мы не можем использовать кодирование длины строки! Действительно, используя этот алгоритм, мы получим в лучшем случае одну и ту же строку.

В этом случае, однако, мы можем видеть другой факт. Строка состоит из слишком большого количества повторяющихся элементов, хотя и не расположенных один за другим. Мы можем сжать эту строку с помощью растрового изображения. Это означает, что мы можем сохранить позиции вхождений данного элемента с последовательностью битов, которые могут быть легко преобразованы в десятичное значение. В приведенном выше примере строка «abababababababab» может быть сжата как «1010101010101010» , что составляет 43690 в десятичных числах , и даже лучше AAAAв шестнадцатеричном формате. Таким образом, длинная строка может быть сжата. При распаковке (декодировании) сообщения мы можем снова преобразовать десятичное / шестнадцатеричное в двоичное и сопоставить вхождения символов. Что ж, приведенный выше пример слишком прост, но, скажем, повторяется только один из символов, а остальная часть строки состоит из разных символов, таких как «abacadaeafagahai» . Тогда мы можем использовать растровое изображение только для символа «a» — «1010101010101010» и сжать его как «AAAA bcdefghi» . Как вы можете видеть, все примеры строк ровно 16 символов, и это ограничение. Использовать растровые изображения с переменной длиной данных немного сложно, и не всегда легко (если возможно) распаковать их.

 

Сжатие растровых изображений

Basically bitmap compression saves the positions of an element that is repeated very often in the message!


In the other hand bitmap compression is not only applicable on strings. We can compress also arrays, objects or any kind of data. The example from my previous post is very suitable. Then we had to transfer a large array from a server to the client (browser) using JSON. The data then was very suitable for “run-length encoding”. Now let’s assume we have the same data – a set of different years, which this time are dispersed in a different way.

$data = array(
	0 	=> 1991,
	1 	=> 1992,
	2 	=> 1993,
	3 	=> 1994,
	4 	=> 1991,
	5 	=> 1992,
	6 	=> 1993,
	7 	=> 1992,
	8 	=> 1991,
	9 	=> 1991,
	10 	=> 1991,
	11 	=> 1992,
	12 	=> 1992,
	13 	=> 1991,
	14 	=> 1991,
	15 	=> 1992,	
	...
);

The JSON will encoded message will be the following (a simple but yet very large javascript array).

[1991,1992,1993,1994,1991,1992,1993,1992,1991,1991,1991,1992,1992,1991,1991,1992, ...]

However if we use bitmap compression we’ll get a “shorter” array.

$data = array(
	0 => array(1991, '1000100011100110'),
	1 => array(1992, '0100010100011001'),
	2 => array(1993, '0010001000000000'),
	3 => array(1994, '0001000000000000'),
);

Now the JSON is:

[[1991,"1000100011100110"],[1992,"0100010100011001"],[1993,"0010001000000000"],[1994,"0001000000000000"]]

It is obvious that the compression ratio is getting better and better as the uncompressed data grows. In fact, most of us know bitmap compression from images, because this algorithm is largely used for image compression. We can imagine how successful it can be when compressing black and white images (as black and white can be represented as 0 and 1s). Actually it is used for more than two colors (256 for instance) and again the level of compression is very high.

Implementation

The following implementation on PHP aims only to illustrate the bitmap compressing algorithm. As we know this algorithm can be applicable for any kind of data structures.

// too many repeating "a" characters
$msg = 'aazahalavaatalawacamaahakafaaaqaaaiauaacaaxaauaxaaaaaapaayatagaaoafaawayazavaaaazaaabararaaaaakakaaqaarazacajaazavanazaaaeanaaoajauaaaaaxalaraaapabataaavaaab';
 
function bitmap($message) 
{
	$i = 0;
	$bits = $rest = '';
 
	while ($v = $message[$i]) {
		if ($v == 'a') {
			$bits .= '1';
		} else {
			$bits .= '0';
			$rest .= $v;
		}
		$i++;
	}
 
	return number_format(bindec($bits), 0, '.', '') . $rest;;
}
 
echo bitmap($msg);
 
// uncompressed: 
acaaaaadaaaabalaaeaaaaganaaxakaavawamaasavajawaaaayaauaaadalanagaeaeamaarafalaazaaaiasaanaahaaazaraxaalaahaaawaaajasamahaajaakarapanaakaoakaanawalaacamauaamaal
// compressed:
152299251941730035874325065523548237677352452096zhlvtlwcmhkfqiucxuxpytgofwyzvzbrrkkqrzcjzvnzenojuxlrpbtvb

Application

This algorithm is very useful when there is an element in our data that repeats very often, so you need to investigate the nature of the data you want to compress. Actually because of this fact this algorithm is used for image compression as PNG8 or GIF.

 

Source: http://www.stoimen.com/blog/2012/01/16/computer-algorithms-data-compression-with-bitmaps/

 

34
Share: