[P&AM Lab] LZW simple in-memory compression library

[Grigoriy A. Sitkarev]

Приветствую всех.

Я давно забыл, что у нас появилась весьма компактная и простая 
библиотечка алгоритма сжатия LZW, про который мы однажды говорили на 
нашей лаборатории в связи с обсуждением онлайн-алгоритмов.

Код можно взять или через svn

$ svn co http://wiki.syktsu.ru/svn/libslzw

или смотреть на нашем websvn через HTTP

http://wiki.syktsu.ru/websvn/listing.php?repname=libslzw&path=%2F&sc=0

Большинство известных реализаций LZW не работают in-memory, а 
предназначены для сжатия/распаковки файлов. Нам нужна была компактная 
версия алгоритма, который мог бы распаковывать и запаковывать поток 
данных онлайн, по мере их поступления.

Примеры использования даны в encode.c и decode.c. Функции сжатия и 
распаковки весьма похожи на семантику iconv(3). Обе функции принимают 5 
аргументов: контекст, указатель на буфер с входными данными и указатель 
на из размер, указатель на буфер с выходными данными и указатель на его 
размер.

Такой псевдо-пример, иллюстрирующий сжатие:


#define BUFSIZE	2048

unsigned char buffer[BUFSIZE];
unsigned char buffer2[2*BUFSIZE];
const unsigned char *in;
unsigned char *out;
size_t insz, outsz;
int count, rc;

...

while ((count = read(0, buffer, sizeof(buffer))) > 0) {

	in = buffer;
	insz = count;

	while (insz > 0) {

		out = buffer2;
		outsz = sizeof(buffer2);

		rc = lzw_encode(&enc, &in, &insz, &out, &outsz);

		if (rc == LZW_OK || rc == LZW_NOSPACE) {
			
			/* Здесь buffer2 содержит (buffer2 - out)
			 * сжатых байт, которые можно отсылать.
			 */
			...
		} else {

			if (rc == LZW_NOMEM) {
				/* Не хватило памяти. */
				...
			} else {
				/* Какое-то другое безобразие... */
				...
			}
		}
	}

	...
}


Финальная посылка сжатых данных должна заканчиваться вызовом 
lzw_end_of_data():


	rc = lzw_end_of_data(&enc, &out, &outsz);
	assert(rc == LZW_OK);

	/* В буфер теперь добавлена завершающая последовательность. */


С распаковкой всё проще, пример decode.c в помощь. Кому интересны детали 
реализации: исходники снабжены достаточно подробными комментариями. В 
любом случае следует сначала разобрать как работает LZW. Дальше всё 
встаёт на свои места.

Алгоритм проверялся на наборе данных Calgary и показал результат 
коэффициента сжатия ~2.11. Это, безусловно, не самый лучший результат, 
но нас он практически устраивал, учитывая простоту реализации и 
незамысловатый алгоритм сброса словаря. Сценарий тестовой программы 
приведен в test.sh.

Всего наилучшего,
--
Г.А.