Startseite
Informatik
Algorithmen
Sortieren
Komprimieren
RLE
Huffman
DRUCK
2004
2005
2006
2007
2008
2009
Lempel-Ziv
Suchen
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
Lempel-Ziv
Das bekannte Zip-Programm komprimiert mit Lempel-Ziv.
Das bekannte Zip-Programm komprimiert mit Lempel-Ziv.
Implementierung
Komprimier- und Dekomprimier-Algorithmen mit Java
Realisierung hier mit Java 1.4.0
Folgenden Code habe ich als Lösung einer Aufgabe während meines Studiums in
Praxis des Programmierens
abgegeben. Das Programm erfüllte alle Anforderungen und ist
voll funktionsfähig!
Allerdings komprimiert folgendes Programm nicht besonders gut.
Bei Verwendung des Programms sollten sie noch einige Verbesserungen vornehmen,
wobei ich auch noch darauf hinweisen möchte, dass der
Lempel-Ziv-Algorithmus
patentrechtlich geschützt
ist.
Hauptklasse: LempelZiv.java
import java.io.*;
import java.util.LinkedList;
/**
* Compression or Decompression with Lempel-Ziv.
*
* Compression: java LempelZiv < INPUTFILE > OUTPUTFILE
* e.g.: java LempelZiv < x.bmp > x.ziv
*
* Decompression: java LempelZiv -x < INPUTFILE > OUTPUTFILE
* e.g.: java LempelZiv -x < x.ziv > x.bmp
*/
public class LempelZiv {
/*
* MAX_NODES can be changed, if you want to optimize the compression.
* 0x0000007F-0x00000003: replace "short" in all three classes to "byte".
* 0x00007FFF-0x00000080: let all "short"-phrases.
* 0x7FFFFFFF-0x00008000: replace "short" in all three classes to "int".
*/
private static final int MAX_NODES = 0x00007FFF; // or 32767
/*
* The Lempel-Ziv algorithm 'zip'.
*/
private static void lempelZivCompress (DataInputStream input,
DataOutputStream output) throws IOException {
// to structure the bit stream to a node tree
LempelZivTree tree = new LempelZivTree(MAX_NODES);
// saves the maximum of possible nodes
output.writeInt(MAX_NODES);
// all bits of input stream will be added to node tree
while (input.available() > 0) {
byte eightBits = input.readByte();
// all bits of a byte will be added to node tree
for (int i = 7; i >= 0; i--) {
byte oneBit = (byte)((eightBits >> i) & (0x01));
if (tree.addBit(oneBit)) {
// to save the current bit-node pair = (bit, id)
short pair = tree.getPair();
output.writeShort(pair);
}
}
}
// if the last pair is uncomplete
// save the last uncomplete, neg. pair
// and terminate with '0'
if (tree.needTerminator()) {
short pair = tree.getPair();
output.writeShort(pair);
output.writeShort(0x0000);
}
} // end of lempelZivCompress
/*
* The Lempel-Ziv algorithm 'unzip'.
*/
private static void lempelZivDecompress (DataInputStream input,
DataOutputStream output) throws IOException {
if (input.available() <= 4) {
// no output!
return;
}
int maxNodes = input.readInt();
// to structure the bit stream to a node table
LempelZivTable table = new LempelZivTable(maxNodes);
LinkedList bits = new LinkedList();
while (input.available() >= 3 * 2) { // 3 * 2 = 3 * size(short)
short pair = input.readShort();
bits = table.getBitsOfPair(pair, bits);
writeBits(bits, output);
}
if (input.available() == 2 * 2) {
// the last 2 short values now!
short pairOrNode = input.readShort();
short pairOrZero = input.readShort();
if (pairOrZero == 0) {
// last pair is uncomplete
bits = table.getBitsOfNode(-pairOrNode, bits);
writeBits(bits, output);
} else {
// last two pairs are complete
bits = table.getBitsOfPair(pairOrNode, bits);
writeBits(bits, output);
bits = table.getBitsOfPair(pairOrZero, bits);
writeBits(bits, output);
}
}
} // end of lempelZivDecompress
/*
* Writes the given bits to the output as bytes and
* removes the written bits from the given bit list.
* The given bit list will contains a number of bits
* lower than '8'.
*/
private static void writeBits(LinkedList bits, DataOutputStream output)
throws IOException {
byte eightBits = 0x00;
byte bitsCount = 0;
while (bits.size() >= 8 - bitsCount) {
eightBits = (byte)(eightBits << 1);
if (((Boolean)bits.removeFirst()).booleanValue()) {
eightBits = (byte)(eightBits | 0x01);
}
bitsCount++;
if (bitsCount >= 8) {
output.writeByte((byte)eightBits);
eightBits = 0x00;
bitsCount = 0;
}
}
} // end of writeBits
/**
* The main program which realizes the compress or decompress with the
* Lempel-Ziv algorithms <u><i>zip</i></u> and <u><i>unzip</i></u>.
* @param args the parameters of command line of system.
* Use the parameter <code>-x</code> to decompress the input stream.
* @throws IOException if it happens by using in- or out-streams.
*/
public static void main (String[] args) throws IOException {
BufferedInputStream bufferedInput = new BufferedInputStream(System.in);
BufferedOutputStream bufferedOutput = new BufferedOutputStream(System.out);
DataInputStream input = new DataInputStream(bufferedInput);
DataOutputStream output = new DataOutputStream(bufferedOutput);
boolean compress = true;
// searches for '-x' in argument list.
for (int i = 0; i < args.length; i++) {
if (args[i].equals("-x")) {
compress = false;
break;
}
}
if (compress) {
lempelZivCompress(input, output);
} else {
lempelZivDecompress(input, output);
}
output.close();
input.close();
} // end of main
} // end of public class LempelZiv
Hilfsklasse: LempelZivTree.java
/**
* This class is only for Lempel-Ziv compression.
*/
public class LempelZivTree {
/* maximum of nodes */
private int maxNodes;
/* the root of nodes tree */
private Node root;
/* identity of current node */
private int currentId;
/* the current node (is never null) */
private Node currentNode;
/* the last node (null if uncomplete pair) */
private Node lastNode;
/* the last bit of last node */
private byte lastBit;
/**
* Instantiates the <code>LempelZivTree</code> object.
* @param maxNodes the maximum of nodes.
*/
public LempelZivTree (int maxNodes) {
this.maxNodes = maxNodes;
this.currentId = 1;
this.root = new Node(this.currentId);
this.currentNode = this.root;
this.lastNode = null;
this.lastBit = 0x00;
} // end of constructor LempelZipTree
/**
* Adds a bit to the internal tree.
* @param oneBit the bit.
* @return <code>true</code> if pair is complete with given bit,
* <code>false</code> otherwise.
*/
public boolean addBit (byte oneBit) {
// actualize the node references
this.lastNode = this.currentNode;
this.currentNode = this.lastNode.children[oneBit];
// store the given bit
this.lastBit = oneBit;
if (this.currentNode == null) {
// creates a new node if the maximum of nodes
// is not reached
if (this.maxNodes > this.currentId) {
this.currentId++;
this.currentNode = new Node(this.currentId);
this.lastNode.children[oneBit] = this.currentNode;
}
this.currentNode = this.root;
// save pair with getPair
return true;
} else {
this.lastNode = null;
// do not save pair
return false;
}
} // end of addBit
/**
* Returns a complete of uncomplete pair.
* @return complete pair
* if last <code>addBit</code> operation was <code>true</code>;
* uncomplete pair
* if last <code>addBit</code> operation was <code>false</code>.
*/
public short getPair () {
short result;
// chooses the right pair
if (this.lastNode == null) {
// returns the uncomplete, negative pair = (-id)
result = (short)this.currentNode.id;
result *= -1;
} else {
// returns the complete pair = (bit, id)
result = (short)this.lastNode.id;
// the bit is the sign of node
if (this.lastBit == 0x01) {
result *= -1;
}
}
return result;
}
/**
* Returns whether the compress algorithm need a special termination:
* negative node and '0'.<br>
* <u>Use it, if you adds all bits with <code>addBit</code> operation</u>.
* @return <code>true</code> if the output stream needs
* special termination (because of uncomplete pair),
* <code>false</code> otherwise.
*/
public boolean needTerminator () {
// true if the pair is uncomplete
return this.lastNode == null;
}
/* Node for the tree of nodes */
private class Node {
/* identity of node */
private int id;
/* the next two nodes */
private Node[] children;
/* instantiates a node */
private Node (int id) {
this.id = id;
// use it, with ...children[aBit]
this.children = new Node[2];
} // end of contructor Node
} // end of private class Node
} // end of public class LempelZivTree
Hilfsklasse: LempelZivTable.java
import java.util.ArrayList;
import java.util.LinkedList;
/**
* This class is only for Lempel-Ziv decompression.
*/
public class LempelZivTable {
/* maximum of nodes */
private int maxNodes;
/* identity of current node */
private int currentId;
/* list of pairs of table, the indices are the ids of nodes */
private ArrayList pairs;
/**
* Instantiates the <code>LempelZivTable</code> object.
* @param maxNodes the maximum of nodes. It must be
* lower than <code>Integer.MAX_VALUE</code>.
*/
public LempelZivTable (int maxNodes) {
this.maxNodes = maxNodes;
this.currentId = 1;
this.pairs = new ArrayList(maxNodes + 1);
// to calculate the bit string of a node,
// the first two elements must be 'null'
this.pairs.add(0, null);
this.pairs.add(1, null);
} // end of constructor LempelZivTable
/**
* Adds to the given <code>restBits</code> the bit string of
* the given complete <code>pair</code>.
* @param pair complete pair.
* @param restBits the buffered bits which could not be saved,
* because to less bits.
* @return bit string.
*/
public LinkedList getBitsOfPair (short pair, LinkedList restBits) {
LinkedList result = new LinkedList();
Pair currentPair = new Pair(pair);
if (this.maxNodes > this.currentId) {
this.currentId++;
this.pairs.add(this.currentId, currentPair);
}
do {
result.addFirst(new Boolean(currentPair.bit));
currentPair = (Pair)this.pairs.get(currentPair.predecessorId);
} while (currentPair != null);
// add the given restBits in front of the pair bit list
result.addAll(0, restBits);
return result;
} // end of getBitsOfPair
/**
* Adds to the given <code>restBits</code> the bit string of
* the given <code>nodeId</code> (last pair).
* @param nodeId positive node identity of uncomplete pair.
* @param restBits the buffered bits which could not be saved,
* because to less bits.
* @return bit string.
*/
public LinkedList getBitsOfNode (int nodeId, LinkedList restBits) {
LinkedList result = new LinkedList();
Pair currentPair = (Pair)this.pairs.get(nodeId);
while (currentPair != null) {
result.addFirst(new Boolean(currentPair.bit));
currentPair = (Pair)this.pairs.get(currentPair.predecessorId);
}
// add the given restBits in front of the pair bit list
result.addAll(0, restBits);
return result;
} // end of getBitsOfNode
/* Element for ArrayList pair */
private class Pair {
/* the own bit */
private boolean bit;
/* the predecessor of this pair */
private int predecessorId;
/* instantiates a pair element */
private Pair (short pair) {
this.bit = pair < 0;
if (this.bit) {
this.predecessorId = (int)(-pair);
} else {
this.predecessorId = (int)pair;
}
} // end of constructor Pair
} // end of private class Pair
} // end of public class LempelZivTable
Beispiel
Beispiel zu Lempel-Ziv
Bitmap-Beispiel
Das folgende Beispiel ist eine 16-Farben-Bitmap-Datei, die ein graues X auf schwarzem Hintergrund repräsentiert.
Diese Datei wird ein wenig herunterkomprimiert.
Klartext (Bitmap)
| Zeile | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 | Text |
|
000 016 032 048 064 080 096 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400 416 432 448 464 480 496 512 528 544 560 576 592 608 624 |
42 4D 76 02 00 00 00 00 00 00 76 00 00 00 28 00 00 00 20 00 00 00 20 00 00 00 01 00 04 00 00 00 00 00 00 02 00 00 CE 0E 00 00 CE 0E 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 80 00 00 80 00 00 00 80 80 00 80 00 00 00 80 00 80 00 80 80 00 00 C0 C0 C0 00 80 80 80 00 00 00 FF 00 00 FF 00 00 00 FF FF 00 FF 00 00 00 FF 00 FF 00 FF FF 00 00 FF FF FF 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |
BMv·······v···(· ·· ··· ········· ······•···•····· ············•··• ···••·•···•·•·•• ··•••·•••···•··• ···••·•···•·•·•• ··•••··········· ················ ········ww······ ··ww····ww······ ··ww···wwww····· ·wwww··wwww····· ·wwww··wwwww···· wwwww··wwwww···· wwwww···wwwww··w wwww····wwwww··w wwww·····wwwwwww www······wwwwwww www·······wwwwww ww········wwwwww ww·········wwwww w··········wwwww w··········wwwww w··········wwwww w·········wwwwww ww········wwwwww ww·······wwwwwww www······wwwwwww www·····wwwww··w wwww····wwwww··w wwww···wwwww···· wwwww··wwwww···· wwwww··wwww····· ·wwww··wwww····· ·wwww···ww······ ··ww····ww······ ··ww············ ················ ······ |
Komprimat (Bitmap)
| Zeile | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 | Text |
|
000 016 032 048 064 080 096 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400 416 432 448 464 480 496 512 528 544 560 576 |
00 00 7F FF 00 01 FF FF 00 02 FF FC 00 05 FF FE 00 03 FF F8 FF FD FF F9 00 04 00 0C 00 08 00 0D 00 0F 00 10 00 11 00 12 00 13 FF F4 00 0A 00 16 00 14 00 18 FF FA 00 19 00 1B 00 06 00 1C FF E4 00 1E 00 20 00 15 FF E7 00 21 00 24 FF DB FF DF FF F2 00 17 FF FB 00 0E FF E1 FF D6 FF F1 00 29 00 25 00 30 00 31 00 32 00 33 FF E2 FF CD 00 34 FF F0 FF EF 00 35 00 37 FF F3 00 3A FF E5 00 39 FF CE 00 2B 00 2A FF D2 00 1F 00 38 00 45 00 3B FF D3 FF F6 00 41 FF E8 FF B7 00 49 FF CA FF B4 FF B1 00 4D FF C8 00 50 FF B2 00 4F FF C7 00 53 FF AE FF B0 00 57 FF C2 FF A7 FF A4 00 55 00 47 00 5F 00 60 00 61 00 62 00 63 00 64 00 65 FF B9 FF EA FF 98 FF F7 00 4A 00 66 00 54 FF B3 FF 97 FF 9C 00 6F FF 92 00 6B 00 6C FF CF FF 8F 00 71 FF 93 FF 8A FF 96 FF F5 00 7B 00 51 00 74 FF EE FF 87 FF 84 00 80 00 7D FF A5 FF 7F 00 7A FF 8E FF 7B 00 7E FF EC FF 7E FF 75 00 86 FF CB FF 7A FF 74 00 88 00 87 FF 9D 00 90 FF 6E 00 94 FF 72 FF 6F FF 6C 00 82 FF 9E FF 67 FF 71 FF 63 00 7C FF 88 00 9E FF 6B FF 5F 00 2F FF DD FF 5D FF 5A FF 68 00 73 FF C9 FF 64 FF 58 00 91 00 97 FF 5E 00 AC 00 AF 00 89 FF 4F 00 AB FF 4D 00 A7 FF 4B 00 9F 00 B2 FF BD FF 50 FF 4C FF 44 FF 4A 00 77 00 B9 FF 5B FF 45 FF 42 FF 3D 00 B0 00 C0 FF D0 FF 43 FF 3E 00 C9 00 92 00 C6 FF 99 00 C4 00 B7 00 B1 00 CC FF 9B 00 C8 FF 31 00 BF 00 D1 FF 65 FF 32 FF 2D 00 A4 00 D6 FF A1 FF 27 FF 28 00 A9 00 DB FF E0 FF 23 FF 36 00 B4 00 E0 FF D4 FF 1D FF 22 FF 19 00 E5 FF AA 00 E9 FF 2C 00 E8 00 CF FF 25 00 E2 FF 13 FF 14 00 9A FF 82 FF 0F 00 F4 00 84 00 F2 00 EF FF 9F FF 0A 00 A1 FF 52 FF 04 00 B8 FF 8B FF 12 00 96 FF 05 FE FE 00 B6 FF 02 FE FB 00 AD FE FC FF 0D 01 06 00 E6 FF 07 00 D5 FF 34 00 FF FF 1F 01 08 00 83 FE F0 FE ED 00 DA FF DC 01 03 00 EA FF 76 01 0C FF A0 01 19 01 1A FF 81 01 1C 01 1F 01 22 01 23 01 24 FF 1B 00 00 |
··••··••··••··•• ··••••••········ ··········••···· ····••········•• ··· ··••·!·$•••• ••··••··••••••·) ·%·0·1·2·3••••·4 ••••·5·7••·:••·9 ••·+·*••···8·E·; ••••·A••••·I•••• ••·M••·P••·O••·S ••••·W••••••·U·G ·_·`·a·b·c·d·e•• ••••••·J·f·T•••• ••·o••·k·l••••·q ••••••••·{·Q·t•• ••••·•·}••••·z•• •{·~•••~•u·••••z •t·•·•••·••n·••r •o•l·••••g•q•c·| ••·••k•_·/•••]•Z •h·s•••d•X·•·••^ ·•·•·••O·••M·••K ·•·••••P•L•D•J·w ·••[•E•B•=·•·••• •C•>·•·•·•••·•·• ·•·•••·••1·•·••e •2•-·•·••••'•(·• ·••••#•6·•·••••· •"•··•••·••,·•·• •%·••·•··••••··• ·•·•·••••··••R•· ·••••··••·••·••· ••·••••····••··• •4·••····•••••·• ••···••v··••···· ••·····"·#·$•··· |
