package lz78ok;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.nio.file.Path;
import java.nio.file.Paths;
public class LZ78OK {
public static void main(String[] args) {
LZ78 lz78 = new LZ78();
InputStream is, isDecompress;
OutputStream os, osDecompress;
String filename = "file3MB.txt";
Path currentRelativePath = Paths.get("");
String s = currentRelativePath.toAbsolutePath().toString();
System.out.println("Current relative path is: " + s);
String filePath = s+"/doc/"+filename;
try {
is = new FileInputStream(filePath);
os = new FileOutputStream(new String(filePath + ".lz78"));
lz78.compress(is, os);
isDecompress = new FileInputStream(new String(filePath + ".lz78"));
osDecompress = new FileOutputStream(new String(filePath + ".lz78.decompressed.txt"));
lz78.decompress(isDecompress, osDecompress);
System.out.println("Done");
System.out.println(new String(filePath));
} catch (Exception e) {
}
}
}
======================
package lz78ok;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
public class LZ78 implements Compression {
boolean stopped = false;
public class Code {
Code(int code, int ch) {
this.ch = ch;
this.code = code;
}
int ch;
int code;
};
Dictionary dict;
byte[] buf;
public final ByteArray emptyBA = new ByteArray();
ByteArray w = emptyBA;
public LZ78() {
int numOfBits = 12;
buf = new byte[numOfBits];
dict = new LimitedSizeDictionary(1 << numOfBits);
dict.add(emptyBA);
}
public int encodeOneChar(int n) {
byte c = (byte) n;
ByteArray nw = w.conc(c);
int code = dict.numFromStr(nw);
if (code != -1) {
w = nw;
return -1;
} else {
dict.add(nw);
nw = w;
w = emptyBA;
return dict.numFromStr(nw);
}
}
public Code encodeLast() {
if (w.size() == 0)
return null;
byte bt = w.getLast();
w = w.dropLast();
return new Code(dict.numFromStr(w), (int) bt);
}
public final void writeCode(OutputStream os, Code c) throws IOException {
writeCode(os, c.ch, 8);
writeCode(os, c.code, 12);
}
public final void writeCode(OutputStream os, int num, int bits) throws IOException {
for (int i = 0; i < bits; ++i) {
os.write(num & 1);
num = num / 2;
}
}
public final Code readCode(InputStream is) throws IOException {
int ch = readInt(is, 8);
if (ch < 0)
return null;
int cd = readInt(is, 12);
if (cd < 0)
return null;
return new Code(cd, ch);
}
public final int readInt(InputStream is, int bits) throws IOException {
int num = 0;
for (int i = 0; i < bits; ++i) {
int next = is.read();
if (next < 0)
return -1;
num += next << i;
}
return num;
}
public void compress(InputStream is, OutputStream os) throws IOException {
os = new BitOutputStream(os);
int next;
int code;
while ((next = is.read()) >= 0) {
if (stopped) {
break;
}
code = encodeOneChar(next);
if (code >= 0) {
writeCode(os, new Code(code, next));
}
}
Code c = encodeLast();
if (c != null) {
writeCode(os, c);
}
os.flush();
}
public ByteArray decodeOne(Code c) {
ByteArray str = dict.strFromNum(c.code);
dict.add(str.conc((byte) c.ch));
return str;
}
@SuppressWarnings("unused")
public void decompress(InputStream is, OutputStream os) throws IOException {
is = new BitInputStream(is);
ByteArray str;
Code c;
while ((c = readCode(is)) != null) {
if (stopped) {
break;
}
if (c == null) {
break;
}
str = decodeOne(c);
os.write(str.getBytes());
os.write(c.ch);
}
}
public void stop() {
stopped = true;
}
}
=================
public class ByteArray {
final byte[] arr;
ByteArray(byte[] b) {
arr = (byte[]) b.clone();
}
ByteArray() {
arr = new byte[0];
}
ByteArray(byte b) {
arr = new byte[] { b };
}
public boolean equals(Object o) {
ByteArray ba = (ByteArray) o;
return java.util.Arrays.equals(arr, ba.arr);
}
public int hashCode() {
int code = 0;
for (int i = 0; i < arr.length; ++i)
code = code * 2 + arr[i];
return code;
}
public int size() {
return arr.length;
}
byte getAt(int i) {
return arr[i];
}
public ByteArray conc(ByteArray b2) {
int sz = size() + b2.size();
byte[] b = new byte[sz];
for (int i = 0; i < size(); ++i)
b[i] = getAt(i);
for (int i = 0; i < b2.size(); ++i)
b[i + size()] = b2.getAt(i);
return new ByteArray(b);
}
public ByteArray conc(byte b2) {
return conc(new ByteArray(b2));
}
public byte[] getBytes() {
return (byte[]) arr.clone();
}
public boolean isEmpty() {
return size() == 0;
}
public byte getLast() {
return arr[size() - 1];
}
public ByteArray dropLast() {
byte[] newarr = new byte[size() - 1];
for (int i = 0; i < newarr.length; ++i)
newarr[i] = arr[i];
return new ByteArray(newarr);
}
public String toString() {
return new String(arr);
}
}
=======================
package lz78ok;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
public interface Compression {
public void compress(InputStream inp, OutputStream out) throws IOException;
public void decompress(InputStream inp, OutputStream out) throws IOException;
}
=======================
package lz78ok;
import java.io.FilterInputStream;
import java.io.IOException;
import java.io.InputStream;
public class BitInputStream extends FilterInputStream {
/**
* Constructor creates a new instance of BitInputStream, A decarotor to
* InputStream, via FilterInputStream
*/
public BitInputStream(InputStream is) {
super(is);
}
class BitManager {
// Buffer to keep max of 7 bits (one byte)
private int[] buf = new int[8];
// Counter showing the bit number we are reading now
private int cnt = -1;
// If we are at the end of the stream
boolean atTheEnd() {
return ((buf[7] == 1) && (cnt < 0));
}
// Set the flag for the end of stream
void setTheEnd() {
buf[7] = 1;
cnt = -1;
}
// No more buffer, means we need to read the next byte
boolean noMoreBuffer() {
return cnt < 0;
}
// set the buffer
void setNext(int next) { // put the bits of the byte into the array
for (cnt = 0; cnt < 8; ++cnt) {
buf[cnt] = next % 2;
next /= 2;
}
// if this was the last byte
if (buf[7] == 1) {
for (cnt = 7; cnt >= 0; cnt--)
if (buf[cnt] == 0)
break;
cnt--;
} else {
cnt = 6;
}
}
// get the next bit
int getNext() {
return buf[cnt--];
}
// how many left
int left() {
return cnt + 1;
}
};
BitManager bitManager = new BitManager();
byte[] tempBuf = null;
int tempBufPtr = 0;
int tempBufLen = 0;
private int readNextByte() throws IOException {
int val = -1;
if (tempBufPtr == tempBufLen)
val = super.read();
else {
byte b = tempBuf[tempBufPtr++];
if ((b & 0x80) > 0)
val = ((int) (b & 0x7F)) | 0x80;
else
val = b;
}
return val;
}
/**
* Reads a single bit from the included stream. Returns either 1 or 0, and
* at the end of stream returns -1.
*/
public int read() throws IOException {
// If we are already at the end, return -1
if (bitManager.atTheEnd())
return -1;
// If we are in the last bit, then refill the buffer
if (bitManager.noMoreBuffer()) {
int i = readNextByte();
if (i < 0)
bitManager.setTheEnd();
else
bitManager.setNext(i);
return read();
}
// Return the specific bit
return bitManager.getNext();
}
/** Reads a list of bits given in the byte array as 0's and 1's */
public int read(byte[] arr) throws IOException {
return read(arr, 0, arr.length);
}
public int read(byte[] arr, int off, int len) throws IOException {
int bytelen = ((len - bitManager.left()) / 7);
tempBuf = new byte[bytelen];
tempBufLen = in.read(tempBuf);
tempBufPtr = 0;
for (int i = 0; i < len; ++i) {
int next = read();
if (next < 0)
return i;
arr[off + i] = (byte) next;
}
return len;
}
}
============================
package lz78ok;
import java.io.FilterOutputStream;
import java.io.IOException;
import java.io.OutputStream;
public class BitOutputStream extends FilterOutputStream {
class BitManager {
int buf = 0;
int cnt = 0;
int writeOne(int next) {
int ret = -1;
buf = buf * 2 + next;
cnt++;
if (cnt == 7) {
cnt = 0;
ret = buf;
buf = 0;
} else {
ret = -1;
}
return ret;
}
//
int writeLast() {
int x = 0;
for (int i = 0; i < 7 - cnt; ++i)
x = x * 2 + 1;
for (int i = 7 - cnt; i < 8; ++i)
x = x * 2;
return buf | x;
}
}
BitManager bitManager = new BitManager();
public BitOutputStream(OutputStream os) {
super(os);
}
public void write(int i) throws IOException {
int x = bitManager.writeOne(i >= 1 ? 1 : 0);
if (x >= 0)
out.write(x);
}
public void write(byte[] arr) throws IOException {
write(arr, 0, arr.length);
}
public void write(byte[] arr, int off, int len) throws IOException {
int clen = 0;
for (int i = 0; i < len; ++i) {
int x = bitManager.writeOne(arr[off + i]);
if (x >= 0)
arr[off + (clen++)] = (byte) x;
}
out.write(arr, off, clen);
}
public void flush() throws IOException {
out.write(bitManager.writeLast());
super.flush();
}
}
==================================
Tidak ada komentar:
Posting Komentar