mtfcompression.java

是内存受限系统设计的代码。

 
/* ***************************************************
   String Compression example
   Nibble compression
   ***************************************************
   */

import  java.io.*;

class MTFCompression
    // MTFCompressions each line in a file
{

    public static void main( String args[] )
    {
        MTFCompression self=new MTFCompression();
        self.test( " Many prog");
        self.test( "Hello world" );
        self.test( "Hello worlde" );
        self.test( "Hello world!" );
        self.test( "" );
        self.test( "." );
        self.test( "I'm all right Jack!" );
        self.test( "Im all right Jack" );
        self.test( "All the world's a stage" );
        self.test( " Many programs need to store sequences or series of data - for example, sequential data such as audio files or animations, or  time series such as stock market prices, or the sequences of values read by a sensor in the outside world. All these strings can take up significant amounts of memory, increasing the program's memory requirements. Generally, this sort of streamed data is typically accessed sequentially, beginning at the first item and then processing each item in turn.  Random access into the middle of the data is required much less frequently than sequential access. Because many programs need to deal with large amounts of sequential data, their memory requirements can cause problems even when they are  stored in Read-Only Memory or Secondary Storage.. Even if the raw memory capacity is sufficient to store the data, you may prefer to allocate it to other uses. Sequential data can also cause problems when they have to be transmitted over slow communication links" );
        try { 
            char[] buf = new char[100000];
            int nChars = (new FileReader( "CompressionChapter.txt"
                                          )).read( buf, 0, buf.length );
            self.test( new String( buf, 0, nChars ) );
        }
        catch (IOException e)
            {
                assert( false, e.toString() );
            }
    }

    public static void assert (boolean  assertion, String excuse) {
        if  (!assertion) { throw new RuntimeException(excuse);}
    }

    private void stringCheck( String a, String b ) {
        assert(a.length() == b.length(), "Different lengths: " +
               a.length() + " and " + b.length() );
        for (int i=0; i<a.length(); i++)
            assert( a.charAt(i) == b.charAt(i), "Strings differ at char " + i + 
                    ", char " + a.charAt(i) + " != " + b.charAt(i) ); 
    }

    protected void test(String input) {
        byte[] intermediate = encodeString(input);
        for ( int i=0; i< Math.min( intermediate.length, 25 ); i++ )
            System.out.print( " " + Integer.toString( intermediate[i] & 0xff, 16 ) );
        System.out.println( "" );
        String output = decodeString(intermediate);
        String inPrint = input.substring( 0, Math.min(20, input.length()) );
        String outPrint = output.substring( 0,Math.min(20, output.length()) );
        System.out.println( inPrint + "->" + outPrint + " " + 
                            intermediate.length + "/" + input.length() + " " + 
                            (float) intermediate.length * 8.0 /
                            input.length() + " bpc");
        stringCheck( output, input );
    }
    
    protected final String NibbleChars = " etoasrinclmhdu";
    protected String currentChars;
    protected final int NibbleEscape = 0xf;
    protected int lastNibble;
    protected ByteArrayOutputStream outStream;
    protected ByteArrayInputStream inStream;
    
    protected byte[] encodeString(String s) {
        outStream = new ByteArrayOutputStream();
        currentChars = NibbleChars;
        lastNibble = -1;
        for (int i = 0; i < s.length(); i++) {
            encodeChar(s.charAt(i));
        }
        if (lastNibble != -1) { // We've one left over
            putNibble( NibbleEscape );
        }
        byte [] result = outStream.toByteArray();
        outStream = null;
        return result;
    }

    protected void encodeChar(char c) {
        int p = currentChars.indexOf(c);     
        if (p != -1) {
            putNibble(p);
        } else {
            putNibble(NibbleEscape);
            putNibble( c >>> 4);   
            putNibble(c & 0xf);
        }
        updateCurrent( c );
    }

    protected void updateCurrent( char c )
    {
        int p = currentChars.indexOf(c);     
        if (p != -1) {
            currentChars = "" + c + currentChars.substring(0,p) +
                currentChars.substring( p+1 );
        } else {
            currentChars = "" + c + currentChars.substring(0, 14);
        }
    }

    protected int decodeChar() {
        char result;
        int s = getNibble();
        if (s == -1) return -1;
        if (s != NibbleEscape) {
            result = currentChars.charAt(s);
        } else {
            s = getNibble();    
            if (s == -1) return -1;
            result = (char)((s << 4) + getNibble()); 
        }
        updateCurrent( result );
        return result;
    }

    protected String decodeString(byte [] s) {
        inStream = new ByteArrayInputStream(s);
        currentChars = NibbleChars;
        StringBuffer outString = new StringBuffer();
        lastNibble = -1;
        int charRead;
        while ((charRead = decodeChar()) != -1) {
            outString.append( (char)charRead );
        }
        return outString.toString();
    }


    protected void putNibble(int n) {
        if (lastNibble == -1) 
            {lastNibble = n;} 
        else {
            outStream.write((lastNibble << 4) + n); 
            lastNibble = -1;
        };
    }
    
    protected int getNibble() {
        int result;
        int byteRead;
        if (lastNibble == -1) {
            byteRead = inStream.read();
            if (byteRead == -1) { return -1;}
            lastNibble = byteRead & 0xff;
            result = lastNibble >>> 4;
        } else {
            result = lastNibble & 0xf; 
            lastNibble = -1; 
        }
        return result;
    }
};