We help IT Professionals succeed at work.

Need code for run length encoding(compression) in java

sriramvemaraju2000
sriramvemaraju2000 asked
on

I need to use run length encoding for compressing data. For a given input byte stream, I need to compute the output by tagging each byte with the number of time the particular byte appears consecutively in the intput stream modulo 255. Examples:
Input                                Output
abbc                                        1a2b1c
a(repeated 500 times)      255a245a
Note that in the examples above, the number preceding the character is a byte, not multiple bytes. For example, when we write the output for the second input above, we will write four bytes to the output: the first byte with the value 255, the second byte with the value ord(a), the third byte with the value 245, and finally the fourth byte with the value ord(a). That is four bytes, and not 8 bytes like what it appears in the text representation.

Comment
Watch Question

Awarded 2011
Awarded 2011

Commented:
Is this a homework ?

Author

Commented:
Its a very minor part of my homework .... I need to complete that by today ...

Author

Commented:
I think.. we can find that code easily because its a basic compression right?
Awarded 2010
Top Expert 2013
Commented:
It would be easier to write the code yourself in this case given how simple it is. Here's the pseudo code to show how easy it is.

set index = 0
while index < size
{
  c = character at index
  set count = 1
  set go = true
  while go and index < size
  {
    look at character at index + count
    if it is the same as c, count ++ else go = false
  }
  encode count
  encode c
}

Author

Commented:
Its a basic algoirthm right.. can you provide me any good links for the implementation in java
Awarded 2011
Awarded 2011
Commented:
check this:

http://algs4.cs.princeton.edu/55compression/RunLength.java.html

/*************************************************************************
 *  Compilation:  javac RunLength.java
 *  Execution:    java RunLength - < input.txt   (compress)
 *  Execution:    java RunLength + < input.txt   (expand)
 *  Dependencies: BinaryIn.java BinaryOut.java
 *
 *  Compress or expand binary input from standard input using
 *  run-length encoding.
 *
 *  % java BinaryDump 40 < 4runs.bin 
 *  0000000000000001111111000000011111111111
 *  40 bits
 *
 *  This has runs of 15 0s, 7 1s, 7 0s, and 11 1s.
 *
 *  % java RunLength - < 4runs.bin | java HexDump
 *  0f 07 07 0b
 *  4 bytes
 *
 *************************************************************************/

public class RunLength {
    private static final int R   = 256;
    private static final int lgR = 8;

    public static void expand() { 
        boolean b = false; 
        while (!BinaryStdIn.isEmpty()) {
            int run = BinaryStdIn.readInt(lgR);
            for (int i = 0; i < run; i++)
                BinaryStdOut.write(b);
            b = !b;
        }
        BinaryStdOut.close();
    }

    public static void compress() { 
        char run = 0; 
        boolean old = false;
        while (!BinaryStdIn.isEmpty()) { 
            boolean b = BinaryStdIn.readBoolean();
            if (b != old) {
                BinaryStdOut.write(run, lgR);
                run = 1;
                old = !old;
            }
            else { 
                if (run == R-1) { 
                    BinaryStdOut.write(run, lgR);
                    run = 0;
                    BinaryStdOut.write(run, lgR);
                }
                run++;
            } 
        } 
        BinaryStdOut.write(run, lgR);
        BinaryStdOut.close();
    }


    public static void main(String[] args) {
        if      (args[0].equals("-")) compress();
        else if (args[0].equals("+")) expand();
        else throw new RuntimeException("Illegal command line argument");
    }

}

Open in new window

Author

Commented:
didnt provided the complete code....
Awarded 2010
Top Expert 2013

Commented:
for_yan did provide a complete code, and he really shouldn't have anyway since it's for homework.