ヘフマン符号化によるファイルの圧縮と解凍(Java実装)
ヘフマン符号化についてはあまり紹介しませんが、圧縮と解凍の方法を直接説明しましょう.
この方法はほとんどのファイルに適用され,無損圧縮である.
1.圧縮ファイル
私が書いた圧縮ファイルは主にいくつかのステップに分けられます.ファイルをバイト配列に変換する、ノードに変換してListに格納する.ヘフマンツリーを作成します.ヘフマン符号化4を生成する.生成したヘフマン符号化に基づいて圧縮して圧縮されたヘフマン符号化バイト配列を得る
2.ファイルを解凍する
1.圧縮バイト符号化をバイナリ文字列2に変換する.ヘフマン符号化により元のバイト配列が得られる
3.ファイル処理
圧縮と解凍は上記の方法を直接呼び出せばいいです.
4.主な方法
5.表示の便宜上、すべてのコードを差し上げます
この方法はほとんどのファイルに適用され,無損圧縮である.
1.圧縮ファイル
私が書いた圧縮ファイルは主にいくつかのステップに分けられます.ファイルをバイト配列に変換する、ノードに変換してListに格納する.ヘフマンツリーを作成します.ヘフマン符号化4を生成する.生成したヘフマン符号化に基づいて圧縮して圧縮されたヘフマン符号化バイト配列を得る
/**
*
* @param bytes
* @return ，
*/
private static byte[] huffmanZip(byte[] bytes){
List<Node> nodes=getNodes(bytes);
//
Node huffmanTreeRoot=createHuffmanTree(nodes);
//
Map<Byte,String> huffmanCodes=getCodes(huffmanTreeRoot);
// ，
byte[] huffmanCodeBytes=zip(bytes,huffmanCodes);
return huffmanCodeBytes;
}
/**
*
* @param bytes
* @param huffmanCodes map
* @return byte[]
* ： 01 ，8 byte ， huffmanCodeBytes
* ：huffmanCodeBytes[0]=10101000( )， 1 11011000=-88
*
*/
private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
StringBuilder stringBuilder=new StringBuilder();
// bytes ,
for(byte b : bytes){
stringBuilder.append(huffmanCodes.get(b));
}
// huffmanCodeBytes ，8
int len=(stringBuilder.length()+7)/8;
byte[] huffmanCodeBytes=new byte[len];
int index=0;
for(int i=0;i<stringBuilder.length();i=i+8){
String strByte;
if(i+8>stringBuilder.length()){
strByte=stringBuilder.substring(i);
}else{
strByte=stringBuilder.substring(i,i+8);
}
// strByte byte huffmanCodeBytes
huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
/**
* ： node ， huffmancodes
* @param node
* @param code ： 0， 1
* @param stringbuilder
*/
private static void getCodes(Node node,String code,StringBuilder stringbuilder){
StringBuilder stringbuilder2=new StringBuilder(stringbuilder);
// code stringbuilder2
stringbuilder2.append(code);
if(node!=null){
if(node.data==null){
//
getCodes(node.left,"0",stringbuilder2);
//
getCodes(node.right,"1",stringbuilder2);
}else{
//
huffmanCodes.put(node.data, stringbuilder2.toString());
}
}
}
// ， getCodes
private static Map<Byte,String> getCodes(Node root){
if(root==null){
return null;
}
//
getCodes(root.left,"0",stringbuilder);
//
getCodes(root.right,"1",stringbuilder);
return huffmanCodes;
}
/**
*
* @param bytes
* @return List [Node[data=97,value=5]]
*/
private static List<Node> getNodes(byte[] bytes){
ArrayList<Node> nodes = new ArrayList<Node>();
// bytes，
Map<Byte,Integer> counts=new HashMap<>();
for(Byte b:bytes){
Integer count=counts.get(b);
if(count==null){
counts.put(b, 1);
}else{
counts.put(b, count+1);
}
}
// Map， Node ， List
for(Map.Entry<Byte, Integer> entry:counts.entrySet()){
nodes.add(new Node(entry.getKey(),entry.getValue()));
}
return nodes;
}
2.ファイルを解凍する
1.圧縮バイト符号化をバイナリ文字列2に変換する.ヘフマン符号化により元のバイト配列が得られる
/**
*
* @param huffmanCodes
* @param huffmanBytes
* @return
*/
private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
StringBuilder strBuilder=new StringBuilder();
// byte
for(int i=0;i<huffmanBytes.length;i++){
byte b=huffmanBytes[i];
boolean flag=(i==huffmanBytes.length-1);
stringbuilder.append(byteToBitString(!flag,b));
}
//
//
Map<String,Byte> map=new HashMap<String,Byte>();
for(Map.Entry<Byte, String> entry : huffmanCodes.entrySet()){
map.put(entry.getValue(), entry.getKey());
}
// byte
List<Byte> list = new ArrayList<>();
for(int i=0;i<stringbuilder.length();){
int count=1;
boolean flag=true;
Byte b=null;
while(flag){
String key=stringbuilder.substring(i,i+count);
b=map.get(key);
if(b==null){
count++;
}else{
flag=false;
}
}
list.add(b);
i+=count;
}
// list byte[]
byte[] b=new byte[list.size()];
for(int i=0;i<b.length;i++){
b[i]=list.get(i);
}
return b;
}
/**
* byte
* @param flag true，flase
* @param b byte
* @return
*/
private static String byteToBitString(boolean flag,byte b){
int temp=b;
//
if(flag){
temp|=256;
}
String str=Integer.toBinaryString(temp);
if(flag){
return str.substring(str.length()-8);
}else{
return str;
}
}
3.ファイル処理
圧縮と解凍は上記の方法を直接呼び出せばいいです.
//
public static void unZipFile(String zipFile,String dstFile){
//
InputStream is=null;
//
ObjectInputStream ois=null;
//
OutputStream os=null;
try {
is=new FileInputStream(zipFile);
ois=new ObjectInputStream(is);
//
byte[] huffmanBytes=(byte[])ois.readObject();
//
Map<Byte,String> buffmanCodes=(Map<Byte,String>)ois.readObject();
//
byte[] bytes=decode(buffmanCodes,huffmanBytes);
os=new FileOutputStream(dstFile);
os.write(bytes);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
} finally{
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
//
/**
*
* @param srcFile
* @param dstFile
*/
public static void zipFile(String srcFile,String dstFile){
OutputStream os=null;
ObjectOutputStream oos=null;
FileInputStream is=null;
try {
is=new FileInputStream(srcFile);
// byte[]
byte[] b=new byte[is.available()];
//
is.read(b);
//
byte[] huffmanBytes=huffmanZip(b);
// ，
os=new FileOutputStream(dstFile);
// ObjectOutputStream
oos=new ObjectOutputStream(os);
//
oos.writeObject(huffmanBytes);
//
oos.writeObject(huffmanCodes);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}finally{
try {
is.close();
oos.close();
os.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
4.主な方法
// {32=01，97=100.....} huffmanCodes
static Map<Byte,String> huffmanCodes=new HashMap<Byte,String>();
//
static StringBuilder stringbuilder=new StringBuilder();
public static void main(String[] args) {
// String content="i like like like java do you like a java";
// byte[] contentBytes=content.getBytes();
// byte[] b=decode(huffmanCodes,huffmanZip(contentBytes));
// System.out.println(new String(b));
String srcFile="D://11111.jpeg";
String dstFile="D://Uninstall2.zip";
String jieFile="D://Uninstall3.jpeg";
zipFile(srcFile,dstFile);
System.out.println(" ");
unZipFile(dstFile,jieFile);
System.out.println(" ");
}
5.表示の便宜上、すべてのコードを差し上げます
package huffmantree;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class HuffmanTree {
// {32=01，97=100.....} huffmanCodes
static Map<Byte,String> huffmanCodes=new HashMap<Byte,String>();
//
static StringBuilder stringbuilder=new StringBuilder();
public static void main(String[] args) {
// String content="i like like like java do you like a java";
// byte[] contentBytes=content.getBytes();
// byte[] b=decode(huffmanCodes,huffmanZip(contentBytes));
// System.out.println(new String(b));
String srcFile="D://11111.jpeg";
String dstFile="D://Uninstall2.zip";
String jieFile="D://Uninstall3.jpeg";
zipFile(srcFile,dstFile);
System.out.println(" ");
unZipFile(dstFile,jieFile);
System.out.println(" ");
}
//
public static void unZipFile(String zipFile,String dstFile){
//
InputStream is=null;
//
ObjectInputStream ois=null;
//
OutputStream os=null;
try {
is=new FileInputStream(zipFile);
ois=new ObjectInputStream(is);
//
byte[] huffmanBytes=(byte[])ois.readObject();
//
Map<Byte,String> buffmanCodes=(Map<Byte,String>)ois.readObject();
//
byte[] bytes=decode(buffmanCodes,huffmanBytes);
os=new FileOutputStream(dstFile);
os.write(bytes);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
} finally{
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
//
/**
*
* @param srcFile
* @param dstFile
*/
public static void zipFile(String srcFile,String dstFile){
OutputStream os=null;
ObjectOutputStream oos=null;
FileInputStream is=null;
try {
is=new FileInputStream(srcFile);
// byte[]
byte[] b=new byte[is.available()];
//
is.read(b);
//
byte[] huffmanBytes=huffmanZip(b);
// ，
os=new FileOutputStream(dstFile);
// ObjectOutputStream
oos=new ObjectOutputStream(os);
//
oos.writeObject(huffmanBytes);
//
oos.writeObject(huffmanCodes);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}finally{
try {
is.close();
oos.close();
os.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
/**
*
* @param huffmanCodes
* @param huffmanBytes
* @return
*/
private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
StringBuilder strBuilder=new StringBuilder();
// byte
for(int i=0;i<huffmanBytes.length;i++){
byte b=huffmanBytes[i];
boolean flag=(i==huffmanBytes.length-1);
stringbuilder.append(byteToBitString(!flag,b));
}
//
//
Map<String,Byte> map=new HashMap<String,Byte>();
for(Map.Entry<Byte, String> entry : huffmanCodes.entrySet()){
map.put(entry.getValue(), entry.getKey());
}
// byte
List<Byte> list = new ArrayList<>();
for(int i=0;i<stringbuilder.length();){
int count=1;
boolean flag=true;
Byte b=null;
while(flag){
String key=stringbuilder.substring(i,i+count);
b=map.get(key);
if(b==null){
count++;
}else{
flag=false;
}
}
list.add(b);
i+=count;
}
// list byte[]
byte[] b=new byte[list.size()];
for(int i=0;i<b.length;i++){
b[i]=list.get(i);
}
return b;
}
/**
* byte
* @param flag true，flase
* @param b byte
* @return
*/
private static String byteToBitString(boolean flag,byte b){
int temp=b;
//
if(flag){
temp|=256;
}
String str=Integer.toBinaryString(temp);
if(flag){
return str.substring(str.length()-8);
}else{
return str;
}
}
/**
*
* @param bytes
* @return ，
*/
private static byte[] huffmanZip(byte[] bytes){
List<Node> nodes=getNodes(bytes);
//
Node huffmanTreeRoot=createHuffmanTree(nodes);
//
Map<Byte,String> huffmanCodes=getCodes(huffmanTreeRoot);
// ，
byte[] huffmanCodeBytes=zip(bytes,huffmanCodes);
return huffmanCodeBytes;
}
/**
*
* @param bytes
* @param huffmanCodes map
* @return byte[]
* ： 01 ，8 byte ， huffmanCodeBytes
* ：huffmanCodeBytes[0]=10101000( )， 1 11011000=-88
*
*/
private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
StringBuilder stringBuilder=new StringBuilder();
// bytes ,
for(byte b : bytes){
stringBuilder.append(huffmanCodes.get(b));
}
// huffmanCodeBytes ，8
int len=(stringBuilder.length()+7)/8;
byte[] huffmanCodeBytes=new byte[len];
int index=0;
for(int i=0;i<stringBuilder.length();i=i+8){
String strByte;
if(i+8>stringBuilder.length()){
strByte=stringBuilder.substring(i);
}else{
strByte=stringBuilder.substring(i,i+8);
}
// strByte byte huffmanCodeBytes
huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
/**
* ： node ， huffmancodes
* @param node
* @param code ： 0， 1
* @param stringbuilder
*/
private static void getCodes(Node node,String code,StringBuilder stringbuilder){
StringBuilder stringbuilder2=new StringBuilder(stringbuilder);
// code stringbuilder2
stringbuilder2.append(code);
if(node!=null){
if(node.data==null){
//
getCodes(node.left,"0",stringbuilder2);
//
getCodes(node.right,"1",stringbuilder2);
}else{
//
huffmanCodes.put(node.data, stringbuilder2.toString());
}
}
}
// ， getCodes
private static Map<Byte,String> getCodes(Node root){
if(root==null){
return null;
}
//
getCodes(root.left,"0",stringbuilder);
//
getCodes(root.right,"1",stringbuilder);
return huffmanCodes;
}
/**
*
* @param bytes
* @return List [Node[data=97,value=5]]
*/
private static List<Node> getNodes(byte[] bytes){
ArrayList<Node> nodes = new ArrayList<Node>();
// bytes，
Map<Byte,Integer> counts=new HashMap<>();
for(Byte b:bytes){
Integer count=counts.get(b);
if(count==null){
counts.put(b, 1);
}else{
counts.put(b, count+1);
}
}
// Map， Node ， List
for(Map.Entry<Byte, Integer> entry:counts.entrySet()){
nodes.add(new Node(entry.getKey(),entry.getValue()));
}
return nodes;
}
//
// public static void preOrder(Node root){
// if(root!=null){
// System.out.println(root);
// if(root.left!=null){
// preOrder(root.left);
// }
// if(root.right!=null){
// preOrder(root.right);
// }
// }else{
// System.out.println(" ");
// }
// }
//
public static Node createHuffmanTree(List<Node> nodes){
while(nodes.size()>1){
//
Collections.sort(nodes);
Node left=nodes.get(0);
Node right=nodes.get(1);
Node parent=new Node(null,left.value+right.value);
parent.left=left;
parent.right=right;
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return nodes.get(0);
}
}
//
class Node implements Comparable<Node>{
Byte data;
int value;
Node left;
Node right;
public Node(Byte data,int value){
this.value=value;
this.data=data;
}
@Override
public String toString() {
return "Node [data="+data+" value=" + value + "]";
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
//
return this.value-o.value;
}
}