ハフマン符号化による書き込みデータ圧縮解凍ソフトウェア(java実装)
20602 ワード
何人かの他のクラスの学生がjavaの課程の設計を書いているのを見て、書いたのはすべて各種の小さいゲームで、私も書きたいと思っていますが、私は小さいゲームを書きたくなくて、長い間考えてやっとこのデータの圧縮を書くことを考えました.それから資料を調べて書いたが、私のクラスにはカリキュラム設計がないことに気づいたので、インタフェースを追加しなかった.書き終わった後も収穫があり、データ圧縮方法に対する印象を完全に更新しました.以前はデータ圧縮が0000000111100111で6041031と表現されていると思っていたが、メモリに格納されているのは符号化であることが分かった.私が書くときに使うのは、圧縮できるファイルの体積を制限する整数表現のファイル長です.BigIntegerに置き換えると、より大きなファイルを圧縮できます.参考資料:http://www.cnblogs.com/keke2014/p/3857335.html
ソースのダウンロード:http://download.csdn.net/detail/gyhguoge01234/9696065
HuffmanCompress.java:
HufTree.java:
Compare.java:
テスト:
ソースのダウンロード:http://download.csdn.net/detail/gyhguoge01234/9696065
HuffmanCompress.java:
import java.util.*;
import java.io.*;
public class HuffmanCompress {
private PriorityQueue queue = null;
//
public void compress(File inputFile, File outputFile){
Compare cmp = new Compare();
queue = new PriorityQueue(12,cmp);
//
HashMap map = new HashMap();
//
int i,char_kinds = 0;
int char_temp,file_len = 0;
FileInputStream fis = null;
FileOutputStream fos = null;
ObjectOutputStream oos = null;
//
int node_num;
HufTree[] huf_tree = null;
String code_buf = null;
//
TmpNode[] tmp_nodes = new TmpNode[256];
for(i = 0; i < 256; ++i){
tmp_nodes[i] = new TmpNode();
tmp_nodes[i].weight = 0;
tmp_nodes[i].uch = (byte)i;
}
try {
fis = new FileInputStream(inputFile);
fos = new FileOutputStream(outputFile);
oos = new ObjectOutputStream(fos);
// ,
while((char_temp = fis.read()) != -1){
++tmp_nodes[char_temp].weight;
++file_len;
}
fis.close();
Arrays.sort(tmp_nodes);
// 0 , 0
//
for(i = 0; i < 256; ++i){
if(tmp_nodes[i].weight == 0)
break;
}
char_kinds = i;
//
if(char_kinds == 1){
oos.writeInt(char_kinds);
oos.writeByte(tmp_nodes[0].uch);
oos.writeInt(tmp_nodes[0].weight);
//
}else{
node_num = 2*char_kinds-1;//
huf_tree = new HufTree[node_num];
for(i = 0; i < char_kinds; ++i){
huf_tree[i] = new HufTree();
huf_tree[i].uch = tmp_nodes[i].uch;
huf_tree[i].weight = tmp_nodes[i].weight;
huf_tree[i].parent = 0;
huf_tree[i].index = i;
queue.add(huf_tree[i]);
}
tmp_nodes = null;
for(; i < node_num; ++i){
huf_tree[i] = new HufTree();
huf_tree[i].parent = 0;
}
//
createTree(huf_tree, char_kinds, node_num,queue);
//
hufCode(huf_tree, char_kinds);
//
oos.writeInt(char_kinds);
for(i = 0; i < char_kinds; ++i){
oos.writeByte(huf_tree[i].uch);
oos.writeInt(huf_tree[i].weight);
map.put(huf_tree[i].uch, huf_tree[i].code);
}
oos.writeInt(file_len);
fis = new FileInputStream(inputFile);
code_buf = "";
//
while((char_temp = fis.read()) != -1){
code_buf += map.get((byte)char_temp);
while(code_buf.length() >= 8){
char_temp = 0;
for(i = 0; i < 8; ++i){
char_temp <<= 1;
if(code_buf.charAt(i) == '1')
char_temp |= 1;
}
oos.writeByte((byte)char_temp);
code_buf = code_buf.substring(8);
}
}
// 8 , 0
if(code_buf.length() > 0){
char_temp = 0;
for(i = 0; i < code_buf.length(); ++i){
char_temp <<= 1;
if(code_buf.charAt(i) == '1')
char_temp |= 1;
}
char_temp <<= (8-code_buf.length());
oos.writeByte((byte)char_temp);
}
}
oos.close();
fis.close();
} catch (Exception e) {
e.printStackTrace();
}
}
//
public void extract(File inputFile, File outputFile){
Compare cmp = new Compare();
queue = new PriorityQueue(12,cmp);
int i;
int file_len = 0;
int writen_len = 0;
FileInputStream fis = null;
FileOutputStream fos = null;
ObjectInputStream ois = null;
int char_kinds = 0;
int node_num;
HufTree[] huf_tree = null;
byte code_temp;
int root;
try{
fis = new FileInputStream(inputFile);
ois = new ObjectInputStream(fis);
fos = new FileOutputStream(outputFile);
char_kinds = ois.readInt();
//
if(char_kinds == 1){
code_temp = ois.readByte();
file_len = ois.readInt();
while((file_len--) != 0){
fos.write(code_temp);
}
//
}else{
node_num = 2 * char_kinds - 1; //
huf_tree = new HufTree[node_num];
for(i = 0; i < char_kinds; ++i){
huf_tree[i] = new HufTree();
huf_tree[i].uch = ois.readByte();
huf_tree[i].weight = ois.readInt();
huf_tree[i].parent = 0;
huf_tree[i].index = i;
queue.add(huf_tree[i]);
}
for(;i < node_num; ++i){
huf_tree[i] = new HufTree();
huf_tree[i].parent = 0;
}
createTree(huf_tree, char_kinds, node_num,queue);
file_len = ois.readInt();
root = node_num-1;
while(true){
code_temp = ois.readByte();
for(i = 0; i < 8; ++i){
if((code_temp & 128) == 128){
root = huf_tree[root].rchild;
}else{
root = huf_tree[root].lchild;
}
if(root < char_kinds){
fos.write(huf_tree[root].uch);
++writen_len;
if(writen_len == file_len) break;
root = node_num - 1; // ,
}
code_temp <<= 1;
}
// 0
// , 0
// 0 ,
// 0
if(writen_len == file_len) break;
}
}
fis.close();
fos.close();
}catch(Exception e){
e.printStackTrace();
}
}
//
public void createTree(HufTree[] huf_tree, int char_kinds, int node_num,PriorityQueue queue){
int i;
int[] arr = new int[2];
for(i = char_kinds; i < node_num; ++i){
arr[0] = queue.poll().index;
arr[1] = queue.poll().index;
huf_tree[arr[0]].parent = huf_tree[arr[1]].parent = i;
huf_tree[i].lchild = arr[0];
huf_tree[i].rchild = arr[1];
huf_tree[i].weight = huf_tree[arr[0]].weight + huf_tree[arr[1]].weight;
huf_tree[i].index = i;
queue.add(huf_tree[i]);
}
}
//
public void hufCode(HufTree[] huf_tree, int char_kinds){
int i;
int cur,next;
for(i = 0; i < char_kinds; ++i){
String code_tmp = "";
for(cur = i,next = huf_tree[i].parent; next != 0; cur = next,next = huf_tree[next].parent){
if(huf_tree[next].lchild == cur)
code_tmp += "0";
else
code_tmp += "1";
}
huf_tree[i].code = (new StringBuilder(code_tmp)).reverse().toString();
}
}
}
HufTree.java:
//
public class HufTree{
public byte uch; // 8
public int weight;//
public String code; //
//
// index
//
public int index;
public int parent,lchild,rchild;
/** **/
public String toString(){
return "uch:" + uch + ",weight:" + weight + ",code:" + code + ",parent:" + parent + ",lchild:" + lchild + ",rchild:" + rchild;
}
}
//
class TmpNode implements Comparable{
public byte uch;
public int weight;
@Override
public int compareTo(TmpNode arg0) {
if(this.weight < arg0.weight)
return 1;
else if(this.weight > arg0.weight)
return -1;
return 0;
}
}
Compare.java:
import java.util.*;
//
public class Compare implements Comparator<HufTree>{
@Override
public int compare(HufTree o1, HufTree o2) {
if(o1.weight < o2.weight)
return -1;
else if(o1.weight > o2.weight)
return 1;
return 0;
}
}
テスト:
import java.io.*;
//
public class Test {
public static void main(String[] args){
HuffmanCompress sample = new HuffmanCompress();
File inputFile = new File("gyh.txt");
File outputFile = new File("gyh.rar");
sample.compress(inputFile, outputFile);
// File inputFile = new File("gyh.rar");
// File outputFile = new File("hyq.txt");
// sample.extract(inputFile, outputFile);
}
}