자바 하프 만 압축 실현 실례
통계 파일 에서 바이트 마다 나타 나 는 빈 도 를 통 해 8 비트 의 01 열 을 자릿수 가 짧 은 하프 만 인 코딩 으로 변환 합 니 다.
그 중에서 하 프 만 인 코딩 은 파일 에 있 는 바이트 가 나타 나 는 주파수 에 따라 구 축 된 것 으로 그 중에서 빈도 가 높 은 바이트 가 나타 날 수록 경로 의 길이 가 짧다.
주파수 가 낮은 바이트 가 나타 날 수록 경로 의 길이 가 길 어 지고 압축 의 목적 을 달성 합 니 다.
어떻게 하프 만 나 무 를 만 듭 니까?
하나 정의 바이트 클래스
제 바이트 클래스 가 속성 을 정 의 했 습 니 다.
public int data;//
public int weight;//
public int point;// 0- 1-
private NodeData parent;//
private NodeData left;//
private NodeData right;//
2.건 하프 만 나무1.바이트 정 보 를 저장 하 는 배열 을 정의 합 니 다:int arrayBytes[256];
그 중에서 배열 의 하 표[0,256)는 바이트 수치(한 바이트 8 비트,그 값 은[0,256)범위 내 에 있다)를 나타 낸다.배열 저장 바이트 가 나타 나 는 횟수.
2.압축 할 파일 을 옮 겨 다 니 며 바이트 가 나타 나 는 횟수 를 통계 합 니 다.
InputStream data = new FileInputStream(path);
/******** ********/
int number = data.available();
for (int i = 0; i < number; i++) {
int b = data.read();
array_Bytes[b] ++;
}
data.close();
3.바이트 클래스 대상 을 우선 대기 열 에 저장4.HashMap 구조 메타 활용
하프 만 압축 코드 는 다음 과 같다.
1.바이트 클래스
package compressFile;
/**
*
* : ,
* @author Andrew
*
*/
public class NodeData {
public NodeData(){
}
public int data;//
public int weight;//
public int point;// 0- 1-
private NodeData parent;
private NodeData left;
private NodeData right;
public int getData(){
return data;
}
public NodeData getParent() {
return parent;
}
public void setParent(NodeData parent) {
this.parent = parent;
}
public NodeData getLeft() {
return left;
}
public void setLeft(NodeData left) {
this.left = left;
}
public NodeData getRight() {
return right;
}
public void setRight(NodeData right) {
this.right = right;
}
}
2.바이트 의 종 류 를 통계 하고 메타 표를 생 성 한다.
package compressFile;
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
/**
* : ,
*
* @author Andrew
*
*/
public class StatisticBytes {
/**
* :
*
*
* @param path
*
* @return
*/
private int[] statistic(String path) {
/****** -- - ******/
int[] array_Bytes = new int[256];
try {
InputStream data = new FileInputStream(path);
BufferedInputStream buffered = new BufferedInputStream(data);
/******** ********/
int number = data.available();
System.out.println(" 》》》"+number);
for (int i = 0; i < number; i++) {
int b = data.read();
array_Bytes[b] ++;
}
data.close();
} catch (IOException e) {
e.printStackTrace();
}
return array_Bytes;
}
/**
* :
*
* @param array
* @return
*/
private PriorityQueue<NodeData> createQueue(int[] array){
// ,
PriorityQueue<NodeData> queue =
new PriorityQueue<NodeData>(array.length,new Comparator<NodeData>(){
public int compare(NodeData o1, NodeData o2) {
return o1.weight - o2.weight;
}
});
for(int i=0; i<array.length; i++){
if(0 != array[i]){
NodeData node = new NodeData();
node.data = i;//
node.weight = array[i];//
queue.add(node);
}
}
return queue;
}
/**
* :
*
* @param queue
* @return
*/
private NodeData createTree(PriorityQueue<NodeData> queue){
while(queue.size() > 1){
NodeData left = queue.poll();//
NodeData right = queue.poll();//
NodeData root = new NodeData();//
root.weight = left.weight + right.weight;
root.setLeft(left);
root.setRight(right);
left.setParent(root);
right.setParent(root);
left.point = 0;
right.point = 1;
queue.add(root);
}
NodeData firstNode = queue.poll();
return firstNode;
}
/**
* :
*
* @param root
*/
private void achievehfmCode(NodeData root){
if(null == root.getLeft() && null == root.getRight()){
array_Str[root.data] = this.achieveLeafCode(root);
/**
*
*
* = *
*/
WriteFile.size_File += (array_Str[root.data].length())*(root.weight);
}
if(null != root.getLeft()){
achievehfmCode(root.getLeft());
}
if(null != root.getRight()){
achievehfmCode(root.getRight());
}
}
/**
*
* @param leafNode
*/
private String achieveLeafCode(NodeData leafNode){
String str = "";
/***************** 01 ****************/
List<Integer> list_hfmCode = new ArrayList<Integer>();
list_hfmCode.add(leafNode.point);
NodeData parent = leafNode.getParent();
while(null != parent){
list_hfmCode.add(parent.point);
parent = parent.getParent();
}
int size = list_hfmCode.size();
for(int i=size-2; i>=0; i--){
str += list_hfmCode.get(i);
}
System.out.println(leafNode.weight+" >>>"+str);
return str;
}
/**
* :
*
* Integer byte [0~256)
* String
* @return
*/
public Map<Integer,String> createMap(){
int[] hfm_Codes = this.statistic("F:\\JAVA\\ .txt");//
PriorityQueue<NodeData> queue = this.createQueue(hfm_Codes);//
/*
* ,
* this.createTree(queue) ( poll()),queue.size()=0
*/
NodeData root = this.createTree(queue);
this.achievehfmCode(root);//
Map<Integer,String> map = new HashMap<Integer,String>();
for(int i=0; i<256; i++){
if(null != array_Str[i]){
map.put(i, array_Str[i]);
}
}
return map;
}
/**
*
* :
* :
*/
public String[] array_Str = new String[256];
}
3.압축 파일 에 메타 를 쓰 고 본문 을 압축 합 니 다.
package compressFile;
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/**
*
* @author Andrew
*
*/
public class WriteFile {
//
private StatisticBytes statistic = new StatisticBytes();
private Map<Integer, String> map = statistic.createMap();//
// , 8
private int exmpCode;
public static int size_File;
public static void main(String[] args) {
WriteFile writeFile = new WriteFile();
writeFile.init();
}
private void init() {
String filePath = "F:\\JAVA\\ .txt";
this.writeFile(filePath);
}
/**
* :
*
* @param dataOut
*
*/
private void writeCodeTable(DataOutputStream dataOut) {
Set<Integer> set = map.keySet();
Iterator<Integer> p = set.iterator();
try {
//
dataOut.writeInt(map.size());
while (p.hasNext()) {
Integer key = p.next();
String hfmCode = map.get(key);
dataOut.writeInt(key);//
//
dataOut.writeByte(hfmCode.length());
for(int i=0; i<hfmCode.length(); i++){
dataOut.writeChar(hfmCode.charAt(i));//
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* :
*
* @param path
*/
private void writeFile(String path) {
try {
//
FileInputStream in = new FileInputStream("F:\\JAVA\\ .txt");
BufferedInputStream bIn = new BufferedInputStream(in);
//
FileOutputStream out = new FileOutputStream(path);
DataOutputStream dataOut = new DataOutputStream(out);
BufferedOutputStream bOut = new BufferedOutputStream(out);
//
this.writeCodeTable(dataOut);
/******************** *********************/
if(0 != size_File % 8){
dataOut.writeByte(8 - (size_File % 8));
}
String transString = "";// , size 8
String waiteString = "";// ,
int size_File = in.available();
for(int i=0; i<size_File; i++){
int j = bIn.read();
System.out.println("]]]]]]]]]]]>>");
waiteString = this.changeStringToByte(transString + statistic.array_Str[j]);
if(waiteString != ""){
bOut.write(exmpCode);
transString = waiteString;
}else{
transString += statistic.array_Str[j];
}
}
if("" != transString){
int num = 8-transString.length()%8;
for(int i=0; i<num; i++){
transString += 0;
}
}
transString = this.changeStringToByte(transString);
bOut.write(exmpCode);
bIn.close();
bOut.flush();
bOut.close();
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* :
* byte
*
* @param str
*
* @return str 8 8 str
* ""
*/
private String changeStringToByte(String str) {
if (8 <= str.length()) {
exmpCode = ((str.charAt(0) - 48) * 128
+ (str.charAt(1) - 48) * 64 + (str.charAt(2) - 48) * 32
+ (str.charAt(3) - 48) * 16 + (str.charAt(4) - 48) * 8
+ (str.charAt(5) - 48) * 4 + (str.charAt(6) - 48) * 2
+ (str.charAt(7) - 48));
str = str.substring(8);
return str;
}
return "";
}
}
2.하프 만 스트레스 해소 원리:압축 의 역방향,즉 당신 이 압축 하 는 대로 압축 을 푼다.자신 이 정의 한 프로 토 콜 에 따라 파일 을 압축 하고 압축 을 푸 는 것 과 같다.
코드 는 다음 과 같 습 니 다:
package decompressionFile;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
*
*
* @author Andrew
*
*/
public class ReadFile {
/**
* Integter: [0,255) String:
*/
private Map<Integer, String> code_Map = new HashMap<Integer, String>();
public static void main(String[] args) {
ReadFile readFile = new ReadFile();
readFile.readFile();
}
/**
* :
*
* @param dataInput
*
*
*/
private void readMap(DataInputStream dataInput) {
try {
//
int size_Map = dataInput.readInt();
/**************** ************************************/
for (int i = 0; i < size_Map; i++) {
int data = dataInput.readInt();//
String str = "";//
// ,
byte codeSize = dataInput.readByte();
for (byte j = 0; j < codeSize; j++) {
str += dataInput.readChar();
}
System.out.println("&&&&&&&&&&>>>>"+data+"!!!!!!!>>"+str);
code_Map.put(data, str);
}
/***************************************************************/
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* :
*/
private void readFile() {
try {
//
InputStream input = new FileInputStream("F:\\JAVA\\ .txt");
// BufferedInputStream bIn = new BufferedInputStream(input);
DataInputStream dInput = new DataInputStream(input);
//
this.readMap(dInput);
byte zerofill = dInput.readByte();//
System.out.println(" 》》》>>>>"+zerofill);
//
OutputStream out = new FileOutputStream("F:\\JAVA\\ .txt");
String transString = "";//
String waiteString = "";//
/*********************************** *****************************************/
int readCode = input.read();//
int size = input.available();
for(int j=0; j<=size; j++){
System.out.println("readCodereadCodereadCode》》>>>>"+readCode);
waiteString += this.changeIntToBinaryString(readCode);// 01
for(int i=0; i<waiteString.length(); i++){
// 01
transString += waiteString.charAt(i);
if(this.searchHC(transString, out)){
// waiteString = waiteString.substring( i+1 );
transString = "";
}
}
waiteString = "";
readCode = input.read();
if(j == size-1){
break;
}
}
/************************************ ***************************************/
// int lastByte = input.read();
String lastWord = this.changeIntToBinaryString(readCode);
waiteString = transString + lastWord.substring(0, 8-zerofill);
transString = "";
for(int i=0; i<waiteString.length(); i++){
// 01
transString += waiteString.charAt(i);
if(this.searchHC(transString, out)){
// waiteString = waiteString.substring( i+1 );
transString = "";
}
}
// this.searchHC(transString, out);
/*********************************** , ****************************************/
// int readCode = input.read();//
// List<Character> list = new ArrayList<Character>();
// while(-1 != readCode){
// String str = this.changeIntToBinaryString(readCode);
// for(int i=0; i<str.length(); i++){
// list.add(str.charAt(i));
// }
// readCode = input.read();
// }
// for(int j=0; j<list.size()-zerofill; j++){
// transString += list.get(j);
// if(this.searchHC(transString, out)){
// transString = "";
// }
// }
/*****************************************************************************************/
input.close();
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* 01
*
* ,
* @param str 01
* @param out
* @return true, false
* @throws IOException
*/
private boolean searchHC(String str, OutputStream out) throws IOException{
Set<Integer> set = code_Map.keySet();
Iterator<Integer> p = set.iterator();
while (p.hasNext()) {
Integer key = p.next();//
String hfmCode = code_Map.get(key);//
if(hfmCode.equals(str)){
out.write(key);
return true;
}
}
return false;
}
/**
* " 2 , "
*
* @param a
* @return 01
*/
private String changeIntToBinaryString(int a) {
int b = a;
int count = 0; // a 01 , 8
String str = "";//
String exmpStr = "";//
while (a != 0) {
b = a/2;
if (a % 2 != 0) {
str += 1;
} else {
str += 0;
}
a = b;
count++;
}
// 8
for (int i = 0; i < 8 - count; i++) {
str += 0;
}
//
for (int j = 7; j >= 0; j--) {
System.out.print(str.charAt(j));
exmpStr += str.charAt(j);
}
System.out.println(" >>>>>>>>>"+exmpStr);
return exmpStr;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.