[cweb-CVS] lgpl-utils/src/test/it/unimi/dsi/mg4j/compression HuffmanCodecTest.java, NONE, 1.1 TestHuTuckerCodec.java, NONE, 1.1

[Bryan T. <tho...@us...>]

Update of /cvsroot/cweb/lgpl-utils/src/test/it/unimi/dsi/mg4j/compression
In directory sc8-pr-cvs4.sourceforge.net:/tmp/cvs-serv14570/src/test/it/unimi/dsi/mg4j/compression

Added Files:
	HuffmanCodecTest.java TestHuTuckerCodec.java 
Log Message:
Commit incorporates some clases from the mg4j project that I am trying out for order preserving (alphabetic) compression.  I am in the process of writing test cases for the HuTuckerCodec that verify its use and order preserving properties.  A minimal set of classes from mg4j has been imported to support compression.  A fastutils jar has also been incorporated, but it can doubtless be prunned down even further.  The import is from the 1.x version of mg4j.  I should really re-import from 2.0 now that it has been released.

--- NEW FILE: TestHuTuckerCodec.java ---
package it.unimi.dsi.mg4j.compression;

import junit.framework.TestCase;

/**
 * Test suite for the {@link HuTuckerCodec}.
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 */
public class TestHuTuckerCodec extends TestCase {

    /**
     * 
     */
    public TestHuTuckerCodec() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param arg0
     */
    public TestHuTuckerCodec(String arg0) {
        super(arg0);
        // TODO Auto-generated constructor stub
    }

}

--- NEW FILE: HuffmanCodecTest.java ---
package it.unimi.dsi.mg4j.compression;

import it.unimi.dsi.fastutil.booleans.BooleanArrayList;
import it.unimi.dsi.fastutil.booleans.BooleanIterator;
import it.unimi.dsi.mg4j.compression.Decoder;
import it.unimi.dsi.mg4j.compression.HuffmanCodec;
import it.unimi.dsi.mg4j.compression.PrefixCodec;

import java.util.Random;

import junit.framework.TestCase;
import cern.colt.bitvector.BitVector;

public class HuffmanCodecTest extends TestCase {
	public void testOneSymbol() {
		HuffmanCodec coder = new HuffmanCodec( new int[] { 1 } );
		assertEquals( 1, coder.codeWord.length );
		assertEquals( new BitVector( 0 ), coder.codeWord[ 0 ] );
	}

	public void testTwoEquiprobableSymbols() {
		HuffmanCodec coder = new HuffmanCodec( new int[] { 1, 1 } );
		assertEquals( 2, coder.codeWord.length );
		assertEquals( new BitVector( 1 ), coder.codeWord[ 0 ] );
		BitVector v = new BitVector( 1 );
		v.set( 0 );
		assertEquals( v, coder.codeWord[ 1 ] );
	}

	public void testThreeNonequiprobableSymbols() {
		HuffmanCodec coder = new HuffmanCodec( new int[] { 1, 2, 4 } );
		assertEquals( 3, coder.codeWord.length );
		assertEquals( new BitVector( 2 ), coder.codeWord[ 0 ] );
		BitVector v = new BitVector( 2 );
		v.set( 1 );
		assertEquals( v, coder.codeWord[ 1 ] );
		v = new BitVector( 1 );
		v.set( 0 );
		assertEquals( v, coder.codeWord[ 2 ] );
	}

	public void testRandomFrequencies() {
		long seed = System.currentTimeMillis();
		System.err.println( seed );
		Random r = new Random( seed );
		int[] frequency = new int[ 100 ];
		for( int i = 0; i < frequency.length; i++ ) frequency[ i ] = r.nextInt( 1000 ); 
		HuffmanCodec codec = new HuffmanCodec( frequency );
		checkPrefixCodec( codec, r );
	}

	private void checkPrefixCodec( PrefixCodec codec, Random r ) {
		int[] symbol = new int[ 100 ];
		BooleanArrayList bits = new BooleanArrayList();
		for( int i = 0; i < symbol.length; i++ ) symbol[ i ] = r.nextInt( codec.size ); 
		for( int i = 0; i < symbol.length; i++ ) {
			BitVector word = codec.codeWord[ symbol[ i ] ];
			for( int j = 0; j < word.size(); j++ ) bits.add( word.get( j ) );
		}
	
		BooleanIterator booleanIterator = bits.iterator();
		Decoder decoder = codec.getDecoder();
		for( int i = 0; i < symbol.length; i++ ) {
			assertEquals( decoder.decode( booleanIterator ), symbol[ i ] );
		}
	}

	private void checkLengths( int[] frequency, int[] codeLength, BitVector[] codeWord ) {
		for( int i = 0; i < frequency.length; i++ ) 
			assertEquals( Integer.toString( i ), codeLength[ i ], codeWord[ i ].size() );
	}
	
	public void testRandomCodeLengths() {
		int[] frequency = { 805, 1335, 6401, 7156, 7333, 10613, 10951, 11708, 12710, 12948, 13237, 13976, 20355, 20909, 22398, 26303, 26400, 28380, 28865, 30152, 31693, };
		int[] codeLength = { 7, 7, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3 };
		HuffmanCodec codec = new HuffmanCodec( frequency );
		checkLengths( frequency, codeLength, codec.codeWord );
		checkPrefixCodec( codec, new Random() );
	}

	public void testExponentialCodeLengths() {
		int[] frequency = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824 };
		int[] codeLength = { 30, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		HuffmanCodec codec = new HuffmanCodec( frequency );
		checkLengths( frequency, codeLength, codec.codeWord );
		checkPrefixCodec( codec, new Random() );
	}
}