compress.cpp

来自「一本全面剖析C++数据结构算法的书籍」· C++ 代码 · 共 128 行

// LZW compression

// note changes needed to compile with g++

#include <fstream.h>
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "chash.h"

// constants
const D = 4099,
      codes = 4096,  // 2^12
      ByteSize = 8,
      excess = 4,    // 12 - ByteSize
      alpha = 256,   // 2^ByteSize
      mask1 = 255,   // alpha - 1
      mask2 = 15;    // 2^excess - 1

class element {
   friend void Compress();
   public:
      operator long() const {return key;}
      element& operator =(long y)
      {key = y; return *this;}
   private:
      int code;
      long key;
};

// globals
int LeftOver, status = 0; 
ifstream in;
ofstream out;

void SetFiles(int argc, char* argv[])
{// Create input and output streams.
   char OutputFile[50], InputFile[50];
   // see if file name provided
   if (argc >= 2) strcpy(InputFile,argv[1]);
   else {// name not provided, ask for it
         cout << "Enter name of file to compress"
              << endl;
         cout << "File name should have no extension"  
              << endl;
         cin >> InputFile;}

   // name should not have an extension
   if (strchr(InputFile,'.')) {
       cerr << "File name has extension" << endl;
       exit(1);}

   // open files in binary mode
   // in.open(InputFile,ios::binary);
   in.open(InputFile); // for g++
   if (in.fail()) {cerr << "Cannot open " << InputFile 
                        << InputFile << endl;
                   exit(1);}
   strcpy(OutputFile,InputFile);
   strcat(OutputFile, ".zzz");
   // out.open(OutputFile,ios::binary);
    out.open(OutputFile); // for g++
}

void output(long code);

void Compress()
{// Lempel-Ziv-Welch compressor.
   ChainHashTable<element, long> h(D);
   element e;
   for (int i = 0; i < alpha; i++) {// initialize
      e.key = i;
      e.code = i;
      h.Insert(e);
   }
   int used = alpha; // codes used

   // input and compress
   unsigned char c;
   in.get(c);
   long pcode = c; // prefix code
   if (!in.eof()) {// file length is > 1
      do {// process rest of file
          in.get(c);
          if (in.eof()) break;  // finished
          long k = (pcode << ByteSize) + c;
          // see if code for k in dictionary
          if (h.Search(k, e)) pcode = e.code;  // yes
          else {// k not in table
                output(pcode);
                if (used < codes) // create new code
                {e.code = used++;
                 e.key = (pcode << ByteSize) | c;
    				 h.Insert(e);}
                pcode = c;}
   	} while(true);

      output(pcode);
      if (status) {c = LeftOver << excess;
                   out.put(c);}
      }
   out.close();
   in.close();
}

void output(long pcode)
{// Output 8 bits, save rest in LeftOver.
   unsigned char c,d;
   if (status) {// 4 bits remain
      d = pcode & mask1; // right ByteSize bits
      c = (LeftOver << excess) | (pcode >> ByteSize);
      out.put(c);
      out.put(d);
      status = 0;}
   else {
      LeftOver = pcode & mask2; // right excess bits
      c = pcode >> excess;
      out.put(c);
      status = 1;}
}

void main(int argc, char* argv[])
{
   SetFiles(argc, argv);
   Compress();
}