Etant plongé dans le codage de l'algorithme de Huffman, je cherche à présent à lire et écrire dans des chaînes de caractères bit après bit. Je pensais avoir trouvé une solution, mais, pour une raison demeurant pour moi inexpliquée, cela marche une fois sur deux. Exemple :
- "a" ; "az" ; "aze" ; "azer" ; "azert" marchent
- "azerty" ne fonctionne pas : En faisant compression puis décompression, j'obtiens "trryet" ... ?
- "azertyu" ; "azertyui" ; "azertyuio" ; "azertyuiop" marchent
Tout est codé en anglais, étant donné que le compresseur sera open source.
À propos de la source, la voici :
MainClass.java
import java.util.Scanner;
import com.compressor.Compressor;
import com.compressor.HuffmanCompressor;
public class MainClass {
/**
* @param args
*/
public static void main(String[] args) {
HuffmanCompressor hc = new HuffmanCompressor();
Compressor c = new Compressor(hc);
Scanner sc = new Scanner(System.in);
String str = "a";
boolean stop = false;
while(!stop) {
stop = true;
System.out.print("Please enter the string that will be compressed : ");
str = sc.nextLine();
System.out.println("Compressed string :\n" + c.compress(str));
if(!str.isEmpty()) {
stop = false;
}
System.out.print("Please enter the string that will be uncompressed : ");
str = sc.nextLine();
System.out.println("Uncompressed string :\n" + c.unCompress(str));
if(!str.isEmpty()) {
stop = false;
}
}
}
}
com.compressor.Compressor.java
package com.compressor;
public class Compressor {
private CompressorInterface i;
public Compressor(CompressorInterface i) {
this.i = i;
}
public void setCompressor(CompressorInterface i) {
this.i = i;
}
public CompressorInterface getCompressor() {
return this.i;
}
public String compress(String str) {
return this.i.getCompressedValue(str);
}
public String unCompress(String str) {
return this.i.getNonCompressedValue(str);
}
}
com.compressor.CompressorInterface.java
package com.compressor;
public interface CompressorInterface {
public String getCompressedValue(String nonCompressedValue);
public String getNonCompressedValue(String compressedValue);
}
com.compressor.HuffmanCompressor.java
package com.compressor;
import java.util.ArrayList;
import com.util.leows.BinaryTree;
import com.util.leows.ExceptionBinaryTreeUnparsableStringNotOnlyZerosAndOnes;
import com.util.leows.ExceptionBinaryTreeUnparsableTreeItNotExists;
public class HuffmanCompressor implements CompressorInterface {
@Override
public String getCompressedValue(String nonCompressedValue) {
String str = nonCompressedValue;
BinaryTree tree = new BinaryTree();
ArrayList<Character> ac = new ArrayList<Character>();
ArrayList<Integer> ai = new ArrayList<Integer>();
ArrayList<BinaryTree> at = new ArrayList<BinaryTree>();
char c;
// We push all str in ai and ac ...
for(int i = 0 ; i < str.length() ; ++i) {
c = str.charAt(i);
if(ac.contains(c)) {
ai.set(ac.indexOf(c), ai.get(ac.indexOf(c)) + 1);
} else {
ac.add(c);
ai.add(1);
}
}
// We push all "ai" and "ac" in tree following the rules of :
// - We take the two smallest integer values of "ai" and "at"
// - We push it into a tree with its characters
// - We push the tree into "at"
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE,
ind1 = -1, ind2 = -1;
boolean is1int = true, is2int = true;
BinaryTree tmp = new BinaryTree();
while(!ai.isEmpty() || at.size() != 1) {
// Getting "min1" and "min2"
ind1 = -1;
ind2 = -1;
min1 = Integer.MAX_VALUE;
min2 = Integer.MAX_VALUE;
for(int i = 0 ; i < ai.size(); ++i) {
if(min1 >= min2 && ai.get(i) < min1) {
min1 = ai.get(i);
ind1 = i;
is1int = true;
} else if(min2 > min1 && ai.get(i) < min2) {
min2 = ai.get(i);
ind2 = i;
is2int = true;
}
}
for(int i = 0 ; i < at.size() ; ++i) {
if(min1 >= min2
&& at.get(i).getElement() != null
&& (Integer) at.get(i).getElement() < min1) {
min1 = (Integer) at.get(i).getElement();
ind1 = i;
is1int = false;
} else if(min1 < min2
&& at.get(i).getElement() != null
&& (Integer) at.get(i).getElement() < min2) {
min2 = (Integer) at.get(i).getElement();
ind2 = i;
is2int = false;
}
}
// Pushing "min1" and "min2" into "tmp"
tmp = new BinaryTree();
if(ind1 == -1 && ind2 != -1) {
if(is2int) {
tmp.setRightTree(new HuffmanTreeElement(ac.get(ind2), min2));
} else {
tmp.setRightTree(at.get(ind2));
}
tmp.setElement(min2);
} else if(ind2 == -1 && ind1 != -1) {
if(is1int) {
tmp.setLeftTree(new HuffmanTreeElement(ac.get(ind1), min1));
} else {
tmp.setLeftTree(at.get(ind1));
}
tmp.setElement(min1);
} else if(ind1 == -1 && ind2 == -1) {
tmp.setElement(0);
}
else {
if(is1int) {
tmp.setLeftTree(new HuffmanTreeElement(ac.get(ind1), min1));
} else {
tmp.setLeftTree(at.get(ind1));
}
if(is2int) {
tmp.setRightTree(new HuffmanTreeElement(ac.get(ind2), min2));
} else {
tmp.setRightTree(at.get(ind2));
}
tmp.setElement(min1 + min2);
}
// Pushing "tmp" into "at"
at.add(tmp.clone());
// Cleaning "at"
if(is1int && !is2int) {
if(ind1 != -1) {
ai.remove(ind1);
ac.remove(ind1);
}
if(ind2 != -1) {
at.remove(ind2);
}
} else if(!is1int && is2int) {
if(ind1 != -1) {
at.remove(ind1);
ai.remove(ind1);
}
if(ind2 != -1) {
ac.remove(ind2);
}
} else if(is1int && is2int) {
if(ind1 < ind2){
if(ind2 != -1) {
ai.remove(ind2);
ac.remove(ind2);
}
if(ind1 != -1) {
ai.remove(ind1);
ac.remove(ind1);
}
} else if(ind1 > ind2) {
if(ind1 != -1) {
ai.remove(ind1);
ac.remove(ind1);
}
if(ind2 != -1) {
ai.remove(ind2);
ac.remove(ind2);
}
}
} else if(!is1int && !is2int) {
if(ind1 < ind2) {
if(ind2 != -1) {
at.remove(ind2);
}
if(ind1 != -1) {
at.remove(ind1);
}
} else if(ind1 > ind2) {
if(ind1 != -1) {
at.remove(ind1);
}
if(ind2 != -1) {
at.remove(ind2);
}
}
}
}
// Getting the resulting string
tree = this.simplifyTree(at.get(0));
String res = this.simplify(at.get(0));
char b = 0;
int bit = 0;
String s;
char ch;
for(int i = 0 ; i < str.length() ; ++i) {
s = tree.find(str.charAt(i));
//*
for(int j = 0 ; j < s.length() ; ++j) {
bit++;
ch = s.charAt(j);
if(ch == '1') {
b |= 1 << (8-bit);
}
if(bit == 8) {
bit = 0;
res += b;
b = 0;
}
}
/**/System.out.print(" " + s);
//*/res += " " + s;
}
int nb = (8 - bit) % 8;
if(nb != 0) {
res += b;
}
return String.valueOf(nb) + res;
}
private String simplify(BinaryTree t) {
return this.stringify(this.simplifyTree(t));
}
private BinaryTree simplifyTree(BinaryTree t) {
if(t instanceof HuffmanTreeElement) {
t = new HuffmanCharacter(((HuffmanTreeElement)t).getC());
} else {
t.setElement(null);
if(t.getLeftTree() != null) {
t.setLeftTree(this.simplifyTree(t.getLeftTree()));
}
if(t.getRightTree() != null) {
t.setRightTree(this.simplifyTree(t.getRightTree()));
}
}
return t;
}
private String stringify(BinaryTree t) {
String res = "";
if(!(t instanceof HuffmanCharacter)) {
res += "(";
res += t.getLeftTree() != null ? this.stringify(t.getLeftTree()) : "";
res += t.getRightTree() != null ? this.stringify(t.getRightTree()) : "";
res += ")";
} else {
res += t.toString();
}
return res;
}
public String getNonCompressedValue(String compressedValue) {
String str = compressedValue;
int lastIndexTree = -1;
for(int i = 1, tmp = 0 ; i < str.length() ; ++i) {
if(str.charAt(i) == '(' && str.charAt(i-1) != '\\') {
++tmp;
} else if(str.charAt(i) == ')' && str.charAt(i-1) != '\\') {
--tmp;
}
if(tmp == 0) {
lastIndexTree = i;
break;
}
}
BinaryTree tree = this.realitify(str.substring(1, lastIndexTree+1));
boolean b;
String res = "";
String tmp = "";
for(int i = lastIndexTree+1 ; i < str.length() ; ++i) {
for(int j = 7 ; j >= 0 ; --j) {
if((i == (str.length()-1)) && ((j+1) == Integer.valueOf(String.valueOf(str.charAt(0))))) {
break;
}
b = ((str.charAt(i) & (1<<j)) != 0);
if(b) {
tmp += '1';
} else {
tmp += '0';
}
try {
if(tree.get(tmp) instanceof HuffmanCharacter) {
res += tree.get(tmp).toString();
System.out.print(" " + tmp);
tmp = "";
}
} catch (Exception e) { e.printStackTrace(); }
}
}
return res;
}
private BinaryTree realitify(String str) {
BinaryTree res = new BinaryTree();
int nbSubTrees = 0;
String tmp = "";
boolean inSubTree = false,
leftDone = false;
for(int i = 1 ; i < str.length()-1 ; ++i) {
if(str.charAt(i) == '(' && !inSubTree && nbSubTrees == 0) {
tmp = "(";
inSubTree = true;
} else if(str.charAt(i) == ')' && nbSubTrees == 0) {
tmp += ")";
inSubTree = false;
if(!leftDone) {
res.setLeftTree(this.realitify(tmp));
leftDone = true;
} else {
res.setRightTree(this.realitify(tmp));
}
} else if(str.charAt(i) == '(' && str.charAt(i-1) != '\\') {
++nbSubTrees;
tmp += '(';
} else if(str.charAt(i) == ')' && str.charAt(i-1) != '\\') {
--nbSubTrees;
tmp += ')';
} else if(str.charAt(i) == '\\' && !inSubTree) {
if(!leftDone) {
res.setLeftTree(new HuffmanCharacter(str.charAt(i+1)));
leftDone = true;
} else {
res.setRightTree(new HuffmanCharacter(str.charAt(i+1)));
}
} else if(!inSubTree) {
if(!leftDone) {
res.setLeftTree(new HuffmanCharacter(str.charAt(i)));
leftDone = true;
} else {
res.setRightTree(new HuffmanCharacter(str.charAt(i)));
}
} else {
tmp += str.charAt(i);
}
}
return res;
}
private class HuffmanTreeElement extends BinaryTree {
private char c;
private int l;
public HuffmanTreeElement() {
}
public HuffmanTreeElement(HuffmanTreeElement e) {
this.c = e.c;
this.l = e.l;
}
public HuffmanTreeElement(char c) {
this.c = c;
this.l = 1;
}
public HuffmanTreeElement(char c, int l) {
this.c = c;
this.l = l;
}
public HuffmanTreeElement(int l, char c) {
this.c = c;
this.l = l;
}
public String toString() {
return this.c + ":" + this.l;
}
public String toString(String ind) {
return ind + this.toString();
}
public char getC() {
return c;
}
public void setC(char c) {
this.c = c;
}
public int getL() {
return l;
}
public void setL(int l) {
this.l = l;
}
}
private class HuffmanCharacter extends BinaryTree {
private char c;
public HuffmanCharacter() {
}
public HuffmanCharacter(char c) {
this.c = c;
}
public char getC() {
return this.c;
}
public void setC(char c) {
this.c = c;
}
public String toString() {
return String.valueOf(this.c);
}
public String toString(String ind) {
return ind + this.toString();
}
public String find(Object o, String prefix) {
if(this.c == (Character) o) {
return prefix;
} else {
return null;
}
}
public Object get(String place) throws ExceptionBinaryTreeUnparsableStringNotOnlyZerosAndOnes, ExceptionBinaryTreeUnparsableTreeItNotExists {
if(place.isEmpty()) {
return this;
} else {
throw new ExceptionBinaryTreeUnparsableTreeItNotExists();
}
}
}
}
com.util.leows.BinaryTree.java
package com.util.leows;
public class BinaryTree implements Cloneable {
private Object element;
private BinaryTree left,
right;
public BinaryTree() {
element = null;
left = null;
right = null;
}
public BinaryTree(Object value) {
element = value;
left = null;
right = null;
}
public BinaryTree(BinaryTree l, BinaryTree r) {
element = null;
left = l;
right = r;
}
public BinaryTree(BinaryTree l, BinaryTree r, Object value) {
element = value;
left = l;
right = r;
}
public BinaryTree(Object value, BinaryTree l, BinaryTree r) {
element = value;
left = l;
right = r;
}
public String find(Object o) {
return this.find(o, "");
}
public String find(Object o, String prefix) {
if(this.element == o) {
return prefix;
} else {
if(left != null && left.find(o, prefix + "0") != null) {
return left.find(o, prefix + "0");
}
if(right != null && right.find(o, prefix + "1") != null) {
return right.find(o, prefix + "1");
}
return null;
}
}
public Object get(String place) throws ExceptionBinaryTreeUnparsableStringNotOnlyZerosAndOnes, ExceptionBinaryTreeUnparsableTreeItNotExists {
if(place.isEmpty()) {
return this.element;
} else {
char c = place.charAt(0);
place = place.substring(1, place.length());
if(c == '0' && this.left != null) {
return this.left.get(place);
} else if(c == '1' && this.right != null) {
return this.right.get(place);
} else if(c != '0' && c != '1') {
throw new ExceptionBinaryTreeUnparsableStringNotOnlyZerosAndOnes();
} else {
throw new ExceptionBinaryTreeUnparsableTreeItNotExists();
}
}
}
public void set(String place, Object o) throws Exception {
if(place == "") {
this.element = o;
} else {
char c = place.charAt(place.length()-1);
place = place.substring(0, place.length()-2);
if(c == '0') {
this.getLeftTree().set(place, o);
} else if(c == '1') {
this.getRightTree().set(place, o);
} else {
throw new ExceptionBinaryTreeUnparsableStringNotOnlyZerosAndOnes();
}
}
}
public String toString() {
String res;
res = "(";
res += element != null ? element.toString() : "";
res += ",";
res += left != null ? left.toString() : "";
res += ",";
res += right != null ? right.toString() : "";
res += ")";
return res;
}
public String toString(String ind) {
String res = "";
res += element != null ? ind + element.toString() + "\n" : ind + "null\n";
res += ind + "{\n";
res += left != null ? left.toString(ind + "\t") + ",\n" : ind + "\tnull,\n";
res += right != null ? right.toString(ind + "\t") + "\n" : ind + "\tnull\n";
res += ind + "}";
return res;
}
public String toStringWithIndent() {
return this.toString("");
}
public String toStringWithIndents() {
return this.toString("");
}
public void fromString(String str) throws Exception {
if(str.charAt(0) != '(') {
throw new ExceptionBinaryTreeUnparsableString();
}
if(str.charAt(str.length()-1) != ')') {
throw new ExceptionBinaryTreeUnparsableString();
}
str = str.substring(1, str.length()-2);
String os,
lefts,
rights;
os = str.substring(0, str.indexOf(',')-1);
lefts = str.substring(str.indexOf(',')+1, str.lastIndexOf(',')-1);
rights = str.substring(str.lastIndexOf(',')+1);
this.element = os;
if(lefts != null && !lefts.isEmpty()) {
this.left = new BinaryTree();
this.left.fromString(lefts);
}
if(rights != null && !rights.isEmpty()) {
this.right = new BinaryTree();
this.right.fromString(rights);
}
}
public BinaryTree clone() {
return new BinaryTree(this.element, this.left, this.right);
}
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public BinaryTree getLeftTree() {
return left;
}
public void setLeftTree(BinaryTree left) {
this.left = left;
}
public BinaryTree getRightTree() {
return right;
}
public void setRightTree(BinaryTree right) {
this.right = right;
}
}
package com.util.leows;
@SuppressWarnings("serial")
public class ExceptionBinaryTreeUnparsableString extends Exception {
public ExceptionBinaryTreeUnparsableString() {
super("BinaryTree : Unable to parse string");
}
}
package com.util.leows;
@SuppressWarnings("serial")
public class ExceptionBinaryTreeUnparsableStringNotOnlyZerosAndOnes extends Exception {
public ExceptionBinaryTreeUnparsableStringNotOnlyZerosAndOnes() {
super("BinaryTree : Unable to parse string (It does not contains only 0 and 1)");
}
}
package com.util.leows;
@SuppressWarnings("serial")
public class ExceptionBinaryTreeUnparsableTreeItNotExists extends Exception {
public ExceptionBinaryTreeUnparsableTreeItNotExists() {
super("BinaryTree : Unable to parse string (It does not exists)");
}
}
com.util.leows.Queue.java
package com.util.leows;
public class Queue extends sun.misc.Queue {
}
com.util.leows.Stack.java
package com.util.leows;
@SuppressWarnings({ "unchecked", "serial" })
public class Stack extends java.util.Stack {
}
Pour l'instant, je n'utilise pas Queue(File,FIFO) ni Stack(Pile,LIFO), mais c'est prévu pour la suite ...
Je vous laisse donc partir à la recherche du bug.
Bonne chance et merci d'avance,
Leows
PS : Est-ce que quelqu'un sait pourquoi les codes sur le SdZ ont rétréci ?
EDIT : Arf ... Dire que j'ai cherché si longtemps pour çà ... En fait, c'était juste un problème de Windows, qui ne copiait/collait pas bien. Bref, çà marche
[String] [Bit à bit] Lecture d'un string bit après bit
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
