IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
  Ответить  Открыть новую тему 
> архиватор по методу Хаффмана, на чистом Си
сообщение
Сообщение #1


Гость
всем доброго времени суток.
Такое дело, преподаватель наш сначало зотел сагитировать нас на написание архиваторпо методу Хаффмана, но потом понял, что для специальностей оооочень далёких от информационных это видимо для первог окурса слишком и скзаал найти исходники и разобраться, типо поспрашивате на понимание и, заставит чего нить дописать самим. Во таткие вот дела. Нижек я предоставлю найденый мной исходник, очень прошу каждого кто имеет время и знания закомментировать, объяснить его работу или может предложить другой исходник, который более понятен и т.п.... Ещё мне кажется, что это тисходник не содержит декодера, это действительно так? Сложно ли его реализовать, если нет, то оочень прошу помочь 0 для нас это просто неподнимаемо....

header файл
#define END_OF_STREAM	256	
#define ESCAPE				257	
#define SYMBOL_COUNT		258	
#define NODE_TABLE_COUNT	((SYMBOL_COUNT * 2) - 1)
#define ROOT_NODE				0
#define MAX_WEIGHT			0x8000 
#define TRUE				1
#define FALSE				0

typedef struct bit_file
{
	FILE *file;
	unsigned char mask;
	int rack;
	int pacifier_counter;
}
COMPRESSED_FILE;


typedef struct tree
{
	int leaf[ SYMBOL_COUNT ];  
	int next_free_node;		
							   
	struct node
	{
		unsigned int weight;   
		int parent;			
		int child_is_leaf;	  
		int child;
	}
	nodes[ NODE_TABLE_COUNT ];
}
TREE;

extern char *Usage;
extern char *CompressionName;


void	usage_exit		(void);
void	print_ratios	(char *input, char *output);
long	file_size		(char *name);
void	fatal_error		(char *fmt, ...);


COMPRESSED_FILE	*OpenInputCompressedFile(char *name);
COMPRESSED_FILE	*OpenOutputCompressedFile(char *name);
void					OutputBit  (COMPRESSED_FILE *, int bit);
void					OutputBits (COMPRESSED_FILE *bit_file, unsigned long code, int count);
int					InputBit   (COMPRESSED_FILE *bit_file);
unsigned long		InputBits  (COMPRESSED_FILE *bit_file, int bit_count);
void					CloseInputCompressedFile (COMPRESSED_FILE *bit_file);
void					CloseOutputCompressedFile (COMPRESSED_FILE *bit_file);


void CompressFile		(FILE *input, COMPRESSED_FILE *output);
void ExpandFile		(COMPRESSED_FILE *input, FILE *output);
void InitializeTree	(TREE *tree);
void EncodeSymbol		(TREE *tree, unsigned int c, COMPRESSED_FILE *output);
int  DecodeSymbol		(TREE *tree, COMPRESSED_FILE *input);
void UpdateModel		(TREE *tree, int c);
void RebuildTree		(TREE *tree);
void swap_nodes		(TREE *tree, int i, int j);
void add_new_node		(TREE *tree, int c);


main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdarg.h>
#include "header.h"


int main (int argc, char *argv[])
{
	COMPRESSED_FILE *output;
	FILE *input;

	setbuf(stdout, NULL);
	if (argc < 3)
	usage_exit(argv[ 0 ]);
	input = fopen(argv[ 1 ], "rb");
	if (input == NULL)
		fatal_error("ЌҐ ¬®Јг ®вЄалвм д ©« %s ¤«п з⥭Ёп\n", argv[ 1 ]);
	output = OpenOutputCompressedFile(argv[ 2 ]);
	if (output == NULL)
		fatal_error("ЌҐ ¬®Јг ®вЄалвм ўл室­®© д ©« %s\n", argv[ 2 ]);
	printf("\n‘¦Ё¬ о д ©« %s ў %s,\n", argv[ 1 ], argv[ 2 ]);
	printf("ЁбЇ®«м§гп %s\n", CompressionName);
	CompressFile(input, output);
	CloseOutputCompressedFile(output);
	fclose(input);
	print_ratios(argv[ 1 ], argv[ 2 ]);
	return(0);
}



void usage_exit (char *prog_name)
{
	char *short_name;
	char *extension;

	short_name = strrchr(prog_name, '\\');
	if (short_name == NULL)
		short_name = strrchr(prog_name, '/');
	if (short_name == NULL)
		short_name = strrchr(prog_name, ':');
	if (short_name != NULL)
		short_name++;
	else
		short_name = prog_name;
	extension = strrchr(short_name, '.');
	if (extension != NULL)
		*extension = '\0';
	printf("\n€бЇ®«м§®ў ­ЁҐ:  %s %s\n", short_name, Usage);
	exit(0);
}


#ifndef SEEK_END
#define SEEK_END 2
#endif

long file_size (char *name)
{
	long eof_ftell;
	FILE *file;

	file = fopen(name, "r");
	if (file == NULL)
		return(0L);
	fseek(file, 0L, SEEK_END);
	eof_ftell = ftell(file);
	fclose(file);
	return(eof_ftell);
}



void print_ratios (char *input, char *output)
{
	long input_size;
	long output_size;
	int ratio;

	input_size = file_size(input);
	if (input_size == 0)
		input_size = 1;
	output_size = file_size(output);
	ratio = 100 - (int) (output_size * 100L / input_size);
	printf("\nђ §¬Ґа ­Ґб¦ в®Ј® д ©« :\t%ld\n", input_size);
	printf("ђ §¬Ґа б¦ в®Ј® д ©« :\t%ld\n", output_size);
	if (output_size == 0)
		output_size = 1;
	printf("‘⥯Ґ­м б¦ вЁп:\t\t%d%%\n", ratio);
}



void fatal_error (char *fmt, ...)
{
	va_list argptr;

	va_start(argptr, fmt);
	printf("” в «м­ п ®иЁЎЄ : ");
	vprintf(fmt, argptr);
	va_end(argptr);
	exit(-1);
}


#define PACIFIER_COUNT 2047




COMPRESSED_FILE *OpenOutputCompressedFile (char *name)
{
	COMPRESSED_FILE *compressed_file;

	compressed_file = (COMPRESSED_FILE *) calloc(1, sizeof(COMPRESSED_FILE));
	if (compressed_file == NULL)
		return(compressed_file);
	compressed_file->file = fopen(name, "wb");
	compressed_file->rack = 0;
	compressed_file->mask = 0x80;
	compressed_file->pacifier_counter = 0;
	return(compressed_file);
}



COMPRESSED_FILE *OpenInputCompressedFile (char *name)
{
	COMPRESSED_FILE *compressed_file;

	compressed_file = (COMPRESSED_FILE *) calloc(1, sizeof(COMPRESSED_FILE));
	if (compressed_file == NULL)
		return(compressed_file);
	compressed_file->file = fopen(name, "rb");
	compressed_file->rack = 0;
	compressed_file->mask = 0x80;
	compressed_file->pacifier_counter = 0;
	return(compressed_file);
}


void CloseOutputCompressedFile(COMPRESSED_FILE *compressed_file)
{
	if (compressed_file->mask != 0x80)
		if (putc(compressed_file->rack, compressed_file->file) != compressed_file->rack)
			fatal_error("” в «м­ п ®иЁЎЄ  ЇаЁ Ї®ЇлвЄҐ § Єалвм б¦ вл© д ©«!\n");
	fclose(compressed_file->file);
	free((char *) compressed_file);
}



void CloseInputCompressedFile(COMPRESSED_FILE *compressed_file)
{
	fclose(compressed_file->file);
	free((char *) compressed_file);
}



void OutputBit(COMPRESSED_FILE *compressed_file, int bit)
{
	if (bit)
		compressed_file->rack |= compressed_file->mask;
	compressed_file->mask >>= 1;
	if (compressed_file->mask == 0)
	{
		if (putc(compressed_file->rack, compressed_file->file) != compressed_file->rack)
			fatal_error("” в «м­ п ®иЁЎЄ  ў Їа®жҐ¤гॠOutputBit!\n");
		else if ((compressed_file->pacifier_counter++ & PACIFIER_COUNT) == 0)
			putc('.', stdout);
		compressed_file->rack = 0;
		compressed_file->mask = 0x80;
	}
}



void OutputBits(COMPRESSED_FILE *compressed_file, unsigned long code, int count)
{
	unsigned long mask;

	mask = 1L << (count - 1);
	while (mask != 0)
	{
		if (mask & code)
			compressed_file->rack |= compressed_file->mask;
		compressed_file->mask >>= 1;
		if (compressed_file->mask == 0)
		{
			if (putc(compressed_file->rack, compressed_file->file) != compressed_file->rack)
				fatal_error("” в «м­ п ®иЁЎЄ  ў Їа®жҐ¤гॠOutputBits!\n");
			else if ((compressed_file->pacifier_counter++ & PACIFIER_COUNT) == 0)
				putc('.', stdout);
			compressed_file->rack = 0;
			compressed_file->mask = 0x80;
		}
		mask >>= 1;
	}
}



int InputBit (COMPRESSED_FILE *compressed_file)
{
	int value;

	if (compressed_file->mask == 0x80)
	{
		compressed_file->rack = getc(compressed_file->file);
		if (compressed_file->rack == EOF)
			fatal_error("” в «м­ п ®иЁЎЄ  ў Їа®жҐ¤гॠInputBit!\n");
		if ((compressed_file->pacifier_counter++ & PACIFIER_COUNT) == 0)
			putc('.', stdout);
	}
	value = compressed_file->rack & compressed_file->mask;
	compressed_file->mask >>= 1;
	if (compressed_file->mask == 0)
		compressed_file->mask = 0x80;
	return(value ? 1 : 0);
}


unsigned long InputBits (COMPRESSED_FILE *compressed_file, int bit_count)
{
	unsigned long mask;
	unsigned long return_value;

	mask = 1L << (bit_count - 1);
	return_value = 0;
	while (mask != 0)
	{
		if (compressed_file->mask == 0x80)
		{
			compressed_file->rack = getc(compressed_file->file);
			if (compressed_file->rack == EOF)
				fatal_error("” в «м­ п ®иЁЎЄ  ў Їа®жҐ¤гॠInputBits!\n");
			if ((compressed_file->pacifier_counter++ & PACIFIER_COUNT) == 0)
				putc('.', stdout);
		}
		if (compressed_file->rack & compressed_file->mask)
			return_value |= mask;
		mask >>= 1;
		compressed_file->mask >>= 1;
		if (compressed_file->mask == 0)
			compressed_file->mask = 0x80;
	}
	return (return_value);
}



char *CompressionName = "Ђ¤ ЇвЁў­®Ґ Љ®¤Ёа®ў ­ЁҐ • д䬥­ ";
char *Usage		   = "зв®_б¦Ё¬ вм Єг¤ _б¦Ё¬ вм";


TREE Tree;



void CompressFile(FILE *input, COMPRESSED_FILE *output)
{
	int c;

	InitializeTree(&Tree);
	while ((c = getc(input)) != EOF)
	{
		EncodeSymbol(&Tree, c, output);
		UpdateModel(&Tree, c);
	}
	EncodeSymbol(&Tree, END_OF_STREAM, output);
}



void ExpandFile (COMPRESSED_FILE *input, FILE *output)
{
	int c;

	InitializeTree(&Tree);
	while ((c = DecodeSymbol(&Tree, input)) != END_OF_STREAM)
	{
		if (putc(c, output) == EOF)
			fatal_error("ЌҐ ¬®Јг ЇЁб вм ў ўл室­®© д ©« ЇаЁ а бЇ Є®ўЄҐ");
		UpdateModel(&Tree, c);
	}
}


void InitializeTree (TREE *tree)
{
	int i;

	tree->nodes[ ROOT_NODE ].child			 = ROOT_NODE + 1;
	tree->nodes[ ROOT_NODE ].child_is_leaf	 = FALSE;
	tree->nodes[ ROOT_NODE ].weight			= 2;
	tree->nodes[ ROOT_NODE ].parent			= -1;

	tree->nodes[ ROOT_NODE + 1 ].child		 = END_OF_STREAM;
	tree->nodes[ ROOT_NODE + 1 ].child_is_leaf = TRUE;
	tree->nodes[ ROOT_NODE + 1 ].weight		= 1;
	tree->nodes[ ROOT_NODE + 1 ].parent		= ROOT_NODE;
	tree->leaf[ END_OF_STREAM ]				= ROOT_NODE + 1;

	tree->nodes[ ROOT_NODE + 2 ].child		 = ESCAPE;
	tree->nodes[ ROOT_NODE + 2 ].child_is_leaf = TRUE;
	tree->nodes[ ROOT_NODE + 2 ].weight		= 1;
	tree->nodes[ ROOT_NODE + 2 ].parent		= ROOT_NODE;
	tree->leaf[ ESCAPE ]					   = ROOT_NODE + 2;

	tree->next_free_node					   = ROOT_NODE + 3;

	for (i = 0; i < END_OF_STREAM; i++)
		tree->leaf[ i ] = -1;
}



void EncodeSymbol (TREE *tree, unsigned int c, COMPRESSED_FILE *output)
{
	unsigned long code;
	unsigned long current_bit;
	int code_size;
	int current_node;

	code = 0;
	current_bit = 1;
	code_size = 0;
	current_node = tree->leaf[ c ];
	if (current_node == -1)
		current_node = tree->leaf[ ESCAPE ];
	while (current_node != ROOT_NODE)
	{
		if ((current_node & 1) == 0)
			code |= current_bit;
		current_bit <<= 1;
		code_size++;
		current_node = tree->nodes[ current_node ].parent;
	}
	OutputBits(output, code, code_size);
	if (tree->leaf[ c ] == -1)
	{
		OutputBits(output, (unsigned long) c, 8);
		add_new_node(tree, c);
	}
}

int DecodeSymbol (TREE *tree, COMPRESSED_FILE *input)
{
	int current_node;
	int c;

	current_node = ROOT_NODE;
	while (!tree->nodes[ current_node ].child_is_leaf)
	{
		current_node = tree->nodes[ current_node ].child;
		current_node += InputBit(input);
	}
	c = tree->nodes[ current_node ].child;
	if (c == ESCAPE)
	{
		c = (int) InputBits(input, 8);
		add_new_node(tree, c);
	}
	return©;
}


void UpdateModel (TREE *tree, int c)
{
	int current_node;
	int new_node;

	if (tree->nodes[ ROOT_NODE].weight == MAX_WEIGHT)
		RebuildTree(tree);
	current_node = tree->leaf[ c ];
	while (current_node != -1)
	{
		tree->nodes[ current_node ].weight++;
		for (new_node = current_node; new_node > ROOT_NODE; new_node--)
			if (tree->nodes[ new_node - 1 ].weight >=
					tree->nodes[ current_node ].weight)
				break;
		if (current_node != new_node)
		{
			swap_nodes(tree, current_node, new_node);
			current_node = new_node;
		}
		current_node = tree->nodes[ current_node ].parent;
	}
}


void RebuildTree (TREE *tree)
{
	int i;
	int j;
	int k;
	unsigned int weight;

	printf("R");
	j = tree->next_free_node - 1;
	for (i = j; i >= ROOT_NODE; i--)
	{
		if (tree->nodes[ i ].child_is_leaf)
		{
			tree->nodes[ j ] = tree->nodes[ i ];
			tree->nodes[ j ].weight = (tree->nodes[ j ].weight + 1) / 2;
			j--;
		}
	}

	for (i = tree->next_free_node - 2; j >= ROOT_NODE; i -= 2, j--)
	{
		k = i + 1;
		tree->nodes[ j ].weight = tree->nodes[ i ].weight + tree->nodes[ k ].weight;
		weight = tree->nodes[ j ].weight;
		tree->nodes[ j ].child_is_leaf = FALSE;
		for (k = j + 1; weight < tree->nodes[ k ].weight; k++)
		;
		k--;
		memmove(&tree->nodes[ j ], &tree->nodes[ j + 1 ],
			(k - j) * sizeof(struct node));
		tree->nodes[ k ].weight = weight;
		tree->nodes[ k ].child = i;
		tree->nodes[ k ].child_is_leaf = FALSE;
	}

	for (i = tree->next_free_node - 1; i >= ROOT_NODE; i--)
	{
		if (tree->nodes[ i ].child_is_leaf)
		{
			k = tree->nodes[ i ].child;
			tree->leaf[ k ] = i;
		}
		else
		{
			k = tree->nodes[ i ].child;
			tree->nodes[ k ].parent = tree->nodes[ k + 1 ].parent = i;
		}
	}
}



void swap_nodes (TREE *tree, int i, int j)
{
	struct node temp;

	if (tree->nodes[ i ].child_is_leaf)
		tree->leaf[ tree->nodes[ i ].child ] = j;
	else
	{
		tree->nodes[ tree->nodes[ i ].child ].parent = j;
		tree->nodes[ tree->nodes[ i ].child + 1 ].parent = j;
	}
	if (tree->nodes[ j ].child_is_leaf)
		tree->leaf[ tree->nodes[ j ].child ] = i;
	else
	{
		tree->nodes[ tree->nodes[ j ].child ].parent = i;
		tree->nodes[ tree->nodes[ j ].child + 1 ].parent = i;
	}
	temp = tree->nodes[ i ];
	tree->nodes[ i ] = tree->nodes[ j ];
	tree->nodes[ i ].parent = temp.parent;
	temp.parent = tree->nodes[ j ].parent;
	tree->nodes[ j ] = temp;
}

void add_new_node (TREE *tree, int c)
{
	int lightest_node;
	int new_node;
	int zero_weight_node;

	lightest_node = tree->next_free_node - 1;
	new_node = tree->next_free_node;
	zero_weight_node = tree->next_free_node + 1;
	tree->next_free_node += 2;

	tree->nodes[ new_node ] = tree->nodes[ lightest_node ];
	tree->nodes[ new_node ].parent = lightest_node;
	tree->leaf[ tree->nodes[ new_node ].child ] = new_node;

	tree->nodes[ lightest_node ].child		 = new_node;
	tree->nodes[ lightest_node ].child_is_leaf = FALSE;

	tree->nodes[ zero_weight_node ].child		   = c;
	tree->nodes[ zero_weight_node ].child_is_leaf   = TRUE;
	tree->nodes[ zero_weight_node ].weight		  = 0;
	tree->nodes[ zero_weight_node ].parent		  = lightest_node;
	tree->leaf[ c ] = zero_weight_node;
}
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Иллюзия мира
***

Группа: Пользователи
Сообщений: 180
Пол: Женский

Репутация: -  4  +

Цитата
закомментировать, объяснить его работу

тебе алгоритм нужен или к каждой строке коменты повбивать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость
С алгоритмом, т.е. теорией, более или мене разобрался, желательно именно комментарии построчные, что от куда вытекает, где что происходит, в таком вот стиле... А на счёт вопроса моего про декодер - его реально нет?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость
Друзья, понимаю, что выполнить вторую мою прозьбу сложно даже для специалистов - написать декодер адаптивного Хаффмана, но хоть закоментить кодовый код можно?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +

Ты не прав насчет того, что здесь нет декодера. Смотри функция
Цитата
void CompressFile (FILE *input, COMPRESSED_FILE *output);

отвечает за кодирование информации, функция же
Цитата
void ExpandFile (COMPRESSED_FILE *input, FILE *output);

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


int main (int argc, char *argv[])
{
    COMPRESSED_FILE *output;
    FILE *input;
if (argc<4)
{
 printf("\nИспользование: <имя EXE файла> <d/e> <Входной файл> <Выходной файл>\n");
 exit(0);
}   
if (argv[1] [0] == 'e')
   CompressFile(argv[2], argv[3]);
else if (argv [1] [0] == 'd')
 ExpandFile(argv[2], argv[3]); 
    exit(0);
}


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

Сообщение отредактировано: Тёмный Эльф -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость
спосибо огромное, очень прошу некоторых комменатриеви по остальным функцим- ведь нам надо показать что мы поняли кажду строчку, а по такому сложно примеру понимать очень сложно....
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость
Тут такое дело, но плучается как будто, вот имеющйийся декодер как бы не очень то и декодирует. В чём проблема
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость
cialis generique ordonnance
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Бывалый
***

Группа: Пользователи
Сообщений: 155
Пол: Мужской

Репутация: -  0  +

Why not settling on games that is fun and at the same time your earning. Well itll make suspense because of the game as well but dude just try it and it gave me hope while pandemic is real rn. Situation of Casinos in the Philippines
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
« Предыдущая тема · Ада и другие языки · Следующая тема »
 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

Режим отображения: Стандартный · Переключить на: Линейный · Переключить на: Древовидный

Подписка на тему · Сообщить другу · Версия для печати · Подписка на этот форум



- Текстовая версия 11.01.2025 4:06
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name