Реализация LZW алгоритма сжатия с использованием возможностей современных GPU
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? уже просто некуда добавить. Но построенная таблица нужна только для той части файла, по которой она была построена. Оставшиеся части файла могут иметь другие характеристики и в действительности нужна уже несколько отличная таблица.
Обычным способом решения этой проблемы является контроль степени сжатия. После того, как таблица строк заполнена, упаковщик следит за поведением коэффициента сжатия. После определенной степени его ухудшения таблица строк очищается и начинает строиться заново.
Процедура распаковки определяет этот момент тем, что упаковщик записывает в свой выходной поток специальный код. Альтернативным способом является определение наиболее часто встречающихся строк и чистка остальных. Адаптивная техника, подобная этой, может, однако, встретить трудности реализации в программах разумного размера.
И, наконец, можно брать вырабатываемые LZW-методом коды и пропускать их через адаптирующийся кодирующий фильтр Хаффмана. Это дает несколько большую степень сжатия, но стоимость такой работы более высока, также как и время обработки.
Приведенная программа была написана и тестирована на MS-DOS машине и успешно скомпилирована и выполнена с использованием обычного компилятора "C". Она должна работать на любой машине, поддерживающей 16-битный целые и 32-битные длинные целые языка "C".
Реализация компиляторов "C" для MS-DOS обычно создает сложности при использовании массивов больших, чем 64К байт, не позволяя использовать 15- или 16-битные коды в программе. На машинах с другими процессорами, таких как VAX, эти сложности преодолеваются, и облегчается использование кодов большей длины.
Отметим, что перевод этого кода на язык ассемблера любой машины, поддерживающей 16- и 32-битную математику, не встретит затруднений и позволит улучшить некоторые характеристики.
Различие между обычным LZW и LZW для GIF заключаются в наличии двух дополнительных специальных кодов и переменном размере сжатия.
Учитывая архитектуру сегодняшних систем, возможно, продолжить повторно проектировать библиотеку Vorbis, чтобы взять дальнейшее преимущество доступного GPU. Однако, осуществление перенесения, вовлеченное в преобразование всех частей этот алгоритм в формат, который является более способствующим векторной обработке, является трудоёмким, утомительным, трудным к отладьте и вовлекает удаление многих интуитивных элементов, достижимых арифметикой указателя.
Совместное управление алгоритмом между системным центральным процессором и доступным GPU - эффективный метод для исполнительного усовершенствования, когда соответствующие силы этих двух наборов микросхем сохранены в памяти.
Список используемой литературы
1. Ватолин Д.С., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002.
. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC.- М.:Унитех, 1992.
. Семенюк В. В. Экономное кодирование дискретной информации. - СПб.: СПбГИТМО (ТУ), 2001.
4.
.
Приложение
/*Демонстрационная программа для LZW-алгоритма сжатия/распаковки данных.*/
/* Mark R. Nelson*/
#include
#define BITS 12 /* Установка длины кода равной 12, 13 */
#define HASHING_SHIFT BITS-8 /* или 14 битам. */
#define MAX_VALUE (1 << BITS) -1/* Отметим, что на MS-DOS-машине при */
#define MAX_CODE MAX_VALUE - 1 /* длине кода 14 бит необходимо компилировать, используя large-модель. */
#if BITS == 14
#define TABLE_SIZE 18041 /* Размер таблицы строк должен быть */
#endif /* простым числом, несколько большим, */
#if BITS == 13 /* чем 2**BITS. */
#define TABLE_SIZE 9029
#endif
#if BITS <= 12
#define TABLE_SIZE 5021
#endif*malloc();
/* Это массив для значений кодов */*code_value;
/* Этот массив содержит префиксы кодов */int *prefix_code;
/* Этот массив содержит добавочные символы */char *append_character;
/* Этот массив содержит декодируемые строки */char decode_stack[4000];
/*Эта программа получает имя файла из командной строки. Она упаковывает файл, посылая выходной поток в файл test.lzw. Затем распаковывает test.lzw в test.out. Test.out должен быть точной копией исходного файла.*/
main(int argc, char *argv[])
{*input_file;*output_file;*lzw_file;input_file_name[81];
/*Эти три буфера необходимы на стадии упаковки.*/
code_value=malloc(TABLE_SIZE*sizeof(unsigned int));_code=malloc(TABLE_SIZE*sizeof(unsigned int));_character=malloc(TABLE_SIZE*sizeof(unsigned char));(code_value==NULL || prefix_code==NULL || append_character==NULL)
{("Fatal error allocating table space!\n");
exit();
}
/*Получить имя файла, открыть его и открыть выходной lzw-файл.*/
if (argc>1)(input_file_name,argv[1]);
{("Input file name? ");("%s",input_file_name);
}_file=fopen(input_file_name,"rb");_file=fopen("test.lzw","wb");(input_file==NULL || lzw_file==NULL)
{("Fatal error opening files.\n");();
};
/*Сжатие файла.*/(input_file,lzw_file);(input_file);(lzw_file);
free(code_value);
/*Сейчас открыть файлы для распаковки.*/
lzw_file=fopen("test.lzw","rb");_file=fopen("test.out","wb");(lzw_file==NULL || output_file==NULL)
{("Fatal error opening files.\n");();
};
/*Распаковка файла.*/(lzw_file,output_file);(lzw_file);(output_file);(prefix_code);(append_character);
}
/*Процедура сжатия.*/(FILE *input,FILE *output)
{int next_code;int character;int string_code;int index;
int i;_code=256; /* Next_code - следующий доступный код строки */(i=0;i<TABLE_SIZE;i++)/*Очистка таблицы строк перед стартом */
code_value[i]=-1;=0;("Compressing...\n");_code=getc(input); /* Get the first code*/
/*Основной цикл. Он выполняется до тех пор, пока возможно чтение входного потока. Отметим, что он прекращает заполнение таблицы строк после того, как все возможные коды были использованы.*/
while ((character=getc(input)) != (unsigned)EOF)
{(++i==1000) /* Печатает * через к