辅导Huffman压缩算法、C辅导：CS226 Data Compress辅导asp、asp语言程序解析

Introduction

You’re trying to take something that can be described in many, many sentences and pages of prose, but you can convert it into a couple lines of poetry and you still get the essence, so that’s compression. The best code is poetry.
– Satya Nadella

When David Huffman was a graduate student in a class at MIT, the professor gave the class an unsolved problem: How to construct an optimal static encoding of information. The young Huffman came back a few days later with his solution, and that solution changed the world. Data compression is now used in all aspects of communication. David Huffman joined the faculty of MIT in 1953, and in 1967 he joined the faculty of University of California, Santa Cruz as one of its earliest members and helped to found its Computer Science Department, where he served as chairman from 1970 to 1973. He retired in 1994, and passed away in 1999.

The key idea is called entropy, originally defined by Claude Shannon in 1948. Entropy is a measure of the amount of information in a, say, set of symbols. If we define I (x) = log2 Pr[x] to be the information content of a symbol, then the entropy of the set X = {x 1 , . . . , x n } is

It should be easy to see that the optimal static encoding will assign the least number of bits to the most common symbol, and the greatest number of bits to the least common symbol.

Your task will be to find a Huffman encoding for the contents of a file, and use it to compress that file. You must also be able to reconstruct the original file from its compressed encoding.

In order to do this, you will need to:

Compute a histogram of the file, in other words, count the number of occurrences of each byte in the file.
Construct the Huffman tree that represents this histogram, in order to do this you will use a priority queue.
Construct the code for each symbol, in order to do this you will use a stack and perform a traversal of the Huffman tree.
Emit an encoding of the Huffman tree to a file, in order to do this you will perform a post-order traversal of the Huffman tree.
Emit an encoding of the original file to the compressed file, in order to do this you will use bit vectors with two additional operations: append and optionally concatenate.
Read the tree from the compressed file, in order to do this you will use a stack.
Decode the compressed bit stream into an identical copy of the original file. In order to do this, you will use the bits (0 means left, 1 means right) to guide your traversal of a reconstructed Huffman tree.

Stacks

I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.
– Linus Torvalds

You will be using stacks in at least two instances in this assignment, consequently you will need several different types of nodes. You may, for example, want a stack of treeNode and a stack of uint32_t, or even better a stack of bits if you are trying to be extra clever (so, let me give you some code for that).
Below is the generic interface for a stack.

#ifndef _STACK_H
#define _STACK_H
#include lt;stdint.hgt;
#include lt;stdbool.hgt;

typedef uint32_t item; // You will need to change this

typedef struct stack
#123;
  uint32_t size; // How big?
  uint32_t top;  // Where's the top?
  item *entries; // Array to hold it (via calloc)
#125; stack;

stack *newStack();        // Constructor
void   delStack(stack *); // Destructor

item pop (stack *);       // Returns the top item
void push(stack *, item); // Adds an item to the top

bool empty(stack *);      // Is it empty
bool full (stack *);      // Is it full?

#endif

The code for each type of stack will be identical, except for the type of items being operated on. Unlike some languages with templates or generics, you will need to have code for each type. You could try to be exceedingly clever and use (void *), but again, I caution you against that approach.

Priority Queues

Data dominates. If you’ve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.
– Rob Pike

In order to construct the Huffman tree, you will want to use a data structure called a priority queue. A priority queue is like a regular queue in that you remove items from the tail, but differs in that when you remove an item it is always the smallest (or largest) item. This implies that the enqueue operation does not simply insert at the head. Of course, the dequeue operation could search for the smallest item each time, but that is a bad idea. Note that the definition does not say what the order in the rest of the queue must be, only that the dequeue operation will return the smallest item.

#ifndef _QUEUE_H
#define _QUEUE_H
#include lt;stdint.hgt;
#include lt;stdbool.hgt;

typedef treeNode item; // treeNode defined in huffman.h

typedef struct queue
#123;
  uint32_t size;       // How big is it?
  uint32_t head, tail; // Front and rear locations
  item *Q;             // Array to hold it (via calloc)
#125; queue;

queue *newQueue(uint32_t size); // Constructor
void   delQueue(queue *q);      // Destructor

bool empty(queue *q);           // Is it empty?
bool full (queue *q);           // Is it full?

bool enqueue(queue *q, item  i); // Add an item
bool dequeue(queue *q, item *i); // Remove from the rear

#endif

Huffman Trees

It’s easy to make mistakes that only come out much later, after you’ve already implemented a lot of code. You’ll realize “Oh I should have used a different type of data structure.” Start over from scratch.
– Guido van Rossum

A Huffman tree is a full binary tree where the leaves represent the symbols to be encoded, and the interior nodes provide a path from the root to the leaves. The path is labeled with 0 for left, and 1 for right. The most common symbol (the one with the highest count in the histogram) should have the shortest path; the least common symbol the longest path.

The process of creating a Huffman tree is surprisingly simple. First, compute your histogram. Next, using treeNode *newNode(uint8_t s, bool l, uint64_t c) enqueue a node for each entry in the histogram into the priority queue.

Third, repeat until the priority queue is empty: dequeue two nodes from the priority queue. Join them under a new node, and insert that node into the priority queue. If there is only one node remaining in the priority queue, then that is the root of the Huffman tree.

#ifndef _HUFFMAN_H
#define _HUFFMAN_H
#include lt;stdint.hgt;
#include lt;stdbool.hgt;

#ifndef NIL
#define NIL (void *) 0
#endif

typedef struct DAH treeNode;

struct DAH
#123;
  uint8_t  symbol;
  uint64_t count;
  bool     leaf;
  treeNode *left, *right;
#125;;

// New node, with symbols, leaf or not, a count associated with it
treeNode *newNode(uint8_t s, bool l, uint64_t c);

// Dump a Huffman tree onto a file
void dumpTree(treeNode *t, int file);

// Build a tree from the saved tree
treeNode *loadTree(uint8_t savedTree[], uint16_t treeBytes);

// Step through a tree following the code
int32_t stepTree(treeNode *root, treeNode **t, uint32_t code);

// Parse a Huffman tree to build codes
void buildCode(treeNode *t, code s, code table[256]);

// Delete a tree
void *delTree(treeNode *t);

static inline void delNode(treeNode *h) #123; free(h); return; #125;

static inline int8_t compare(treeNode *l, treeNode *r)
#123;
  return l-gt;count - r-gt;count; // l lt; r if negative, 1 = r if 0, ...
#125;

treeNode *join(treeNode *l, treeNode *r); // Join two subtrees
#endif

The function treeNode *join(treeNode *l, treeNode *r) takes two nodes, which may be either leaves or interior nodes, and creates a new internal node with its count set to the sum of the counts of the two child nodes.

When you are creating the code for each symbol, you will want to use a stack as defined in code.h, it provides a lovely little stack of bits. You will see that as you traverse the Huffman tree, you want to push 0 when you go to the left child and push 1 when you go to the right. Consequently, when you return from either child, you will want to perform a pop. As soon as you reach any leaf node during the traversal, the current state of the stack will represent the code for the symbol at the leaf node.

#ifndef _CODE_H
#define _CODE_H

#include lt;stdint.hgt;
#include lt;stdbool.hgt;

typedef struct code
#123;
  uint8_t bits[32];
  uint32_t l;
#125; code;

static inline code newCode()
#123;
  code t;
  for (int i = 0; i lt; 32; i += 1) #123; t.bits[i] = 0; #125;
  t.l = 0;
  return t;
#125;

static inline bool pushCode(code *c, uint32_t k)
#123;
  if (c-gt;l gt; 256)
  #123;
    return false;
  #125;
  else if (k == 0)
  #123;
    c-gt;bits[c-gt;l / 8] amp;= ~(0x1 lt;lt; (c-gt;l % 8));
    c-gt;l += 1;
  #125;
  else
  #123;
    c-gt;bits[c-gt;l / 8] |= (0x1 lt;lt; (c-gt;l % 8));
    c-gt;l += 1;
  #125;
  return true;
#125;

static inline bool popCode(code *c, uint32_t *k)
#123;
  if (c-gt;l == 0)
  #123;
    return false;
  #125;
  else
  #123;
    c-gt;l -= 1;
    *k = ((0x1 lt;lt; (c-gt;l % 8)) amp; c-gt;bits[c-gt;l / 8]) gt;gt; (c-gt;l % 8);
    return true;
  #125;
#125;
static inline bool emptyCode(code *c) #123; return c-gt;l ==   0; #125;
static inline bool fullCode (code *c) #123; return c-gt;l == 256; #125;
#endif

You may find it convenient to create a function appendCode for a bitVector which can take in a code * and append that code to the bit vector.

Your Task

You should construct both an encoder and a decoder. The encoder takes any file and produces a compressed file. The decoder takes a compressed file and produces an exact duplicate of the original file, down to each bit.

Specifics

You will be pulling together most of the data structures that you learned this quarter to finish this assignment. You will need at least two different stacks, a priority queue, arrays, and of course, the Huffman tree.

Encoding

Encoding is the concept of taking a source file and compressing it to reduce its size. For this section, I will refer to the source file as sFile and the output (compressed) file as oFile. To encode an sFile, follow these steps: