mtf.cpp

bwt压缩方式的源码

//
//  MTF.CPP
//
//  Mark Nelson
//  March 8, 1996
//  http://web2.airmail.net/markn
//
// DESCRIPTION
// -----------
//
//  This program performs a Move To Front encoding function on an
//  input file/stream, and sends the result to an output file
//  or stream.  An MTF encoder encodes each character using the
//  count of distinct previous characters seen since the characters
//  last appearance.  This is implemented by keeping an array of
//  characters.  Each new input character is encoded with its
//  current position in the array.  The character is then moved to
//  position 0 in the array, and all the higher order characters
//  are moved down by one position to make roon.
//
//  Both the encoder and decoder have to start with the order array
//  initialized to the same values.
//
//  This program takes two arguments: an input file and an output
//  file.  You can leave off one argument and send your output to
//  stdout.  Leave off two arguments and read your input from stdin
//  as well.
//
//  This program accompanies my article "Data Compression with the
//  Burrows-Wheeler Transform."
//
// Build Instructions
// ------------------
//
//  Define the constant unix for UNIX or UNIX-like systems.  The
//  use of this constant turns off the code used to force the MS-DOS
//  file system into binary mode.  g++ already does this, your
//  UNIX C++ compiler might also.
//
//  Borland C++ 4.5 16 bit    : bcc -w mtf.cpp
//  Borland C++ 4.5 32 bit    : bcc32 -w mtf.cpp
//  Microsoft Visual C++ 1.52 : cl /W4 mtf.cpp
//  Microsoft Visual C++ 2.1  : cl /W4 mtf.cpp
//  g++                       : g++ -o mtf mtf.cpp
//
// Typical Use
// -----------
//
//  rle < raw-file | bwt | mtf | rle | ari > compressed-file
//
//

#include <stdio.h>
#if !defined( unix )
#include <io.h>
#endif
#include <fcntl.h>

main( int argc, char *argv[] )
{
    fprintf( stderr, "Performing MTF encoding on " );
    if ( argc > 1 ) {
        freopen( argv[ 1 ], "rb", stdin );
        fprintf( stderr, "%s", argv[ 1 ] );
    } else
        fprintf( stderr, "stdin" );
    fprintf( stderr, " to " );
    if ( argc > 2 ) {
        freopen( argv[ 2 ], "wb", stdout );
        fprintf( stderr, "%s", argv[ 2 ] );
    } else
        fprintf( stderr, "stdin" );
    fprintf( stderr, "\n" );
#if !defined( unix )
    setmode( fileno( stdin ), O_BINARY );
    setmode( fileno( stdout ), O_BINARY );
#endif

    unsigned char order[ 256 ];
    int i;
    for ( i = 0 ; i < 256 ; i++ )
        order[ i ] = (unsigned char) i;
    int c;
    while ( ( c = getc( stdin ) ) >= 0 )  {
//
// Find the char, and output it
//
        for ( i = 0 ; i < 256 ; i++ )
            if ( order[ i ] == ( c & 0xff ) )
                break;
        putc( (char) i, stdout );
//
// Now shuffle the order array
//
        for ( int j = i ; j > 0 ; j-- )
            order[ j ] = order[ j - 1 ];
        order[ 0 ] = (unsigned char) c;
    }
    return 1;
}