자바 하프 만 압축 및 압축 풀기 실현 방법
1.하프 만 나무:
N 개의 가중치 를 N 개의 잎 결점 으로 지정 하고 이 진 트 리 를 구성 합 니 다.이 나무의 권한 경로 길이 가 가장 작 으 면 이 진 트 리 를 가장 좋 은 이 진 트 리 라 고 부 르 고 하 프 만 트 리 라 고도 부 릅 니 다.하 프 만 나 무 는 권한 을 가 진 경로 의 길이 가 가장 짧 은 나무 로 권한 이 비교적 큰 결점 은 뿌리 와 가깝다
.다음 배열 의 경우 하프 만 트 리 를 구축 합 니 다.
int a[] = {0,1,2,3,4,5,6,7,8}
우 리 는 다음 과 같은 규칙 을 발견 할 수 있다.
1:9 개의 수로 구 성 된 하프 만 나 무 는 모두 17 개의 결점 이 있 는데,즉 n 개의 수가 2*n-1 개의 결점 을 생산 할 수 있다
2:숫자 가 클 수록 뿌리 노드 와 가 까 워 지고 작은 숫자 가 뿌리 노드 와 가 까 워 집 니 다.
2.haffman 인 코딩 을 이용 하여 파일 압축 을 실현 하 는 방법:
예 를 들 어 abc.txt 파일 에는 다음 과 같은 문자 가 있 습 니 다:aaaabbbccde,
1.문자 통계 진행
aaaabbbccde
a : 4
b : 3
c : 2
d : 1
e : 1 
3.하프 만 트 리 로 하프 만 인 코딩 생 성(뿌리 노드 부터 경로 왼쪽 은 0,오른쪽 은 1):
a ：1
b :01
c :000
d :0011
e :0010원본 파일 내용:aaaabbbccde
원본 파일 을 대응 하 는 하 프 만 인 코딩(haffman code)으로 교체 하면 11110101 01000000 00110010(총 3 바이트)이 있 습 니 다.
이 를 통 해 알 수 있 듯 이 원본 파일 은 모두 11 개의 문자 로 11 바이트 의 메모 리 를 차지 하지만 haffman code 로 교체 한 후에 3 개의 바이트 만 차지 하면 압축 의 목적 을 달성 할 수 있다.
두 번 째 주요 기술 점:
1.하프 만 트 리 알고리즘(하프 만 압축 의 기본 알고리즘)
2.해시 알고리즘(문자 통 계 를 할 때 사용 되 고 HashMap 으로 직접 통계 할 수 있 음)
3.비트 연산(지 정 된 비트 를 0 또는 1 로 설정 하 는 것 과 관련된다)
4.자바 파일 작업 및 버퍼 작업.
5.저장 모드(큰 엔 드 저장,작은 엔 드 저장,파일 16 진법 을 알 아 볼 수 있 음)
7.압축 암 호 를 설정 하고 압축 을 풀 고 암 호 를 입력 하여 압축 을 푼다.
3 실현 과정:
상기 aaaabbbccde 를 예 로 들 면
1.문자 통계:
public class FreqHuf {
public static int BUFFER_SIZE = 1 << 18;
int freq[] = new int[256];
File file;
int count;
List<HuffmanFreq> list;
FreqHuf(String pathname) throws Exception {
list = new ArrayList<>();
this.file = new File(pathname);
if(!file.exists()){
throw new Exception(" ");
}
System.out.println(" ");
CensusChar();
System.out.println(" ");
}
public void CensusChar() throws IOException{
int intchar;
FileInputStream fis = new FileInputStream(file);
System.out.println(" ");
// ， ， ， 。
// while((intchar = fis.read()) != -1){
// freq[intchar]++;
// }
// ， 1 << 18 ， 。
byte[] bytes = new byte[BUFFER_SIZE];
while((intchar = fis.read(bytes))!= -1){
for(int i = 0; i < intchar;i++){
int temp = bytes[i]& 0xff;
freq[temp]++;
}
}
fis.close();
for(int i = 0; i < 256; i++){
if(freq[i] != 0){
this.count++;
}
}
int index = 0;
for(int i = 0; i < 256; i++){
if(freq[i] != 0){
HuffmanFreq huffman = new HuffmanFreq();
huffman.character = (char)i;
huffman.freq = freq[i];
list.add(index, huffman);
}
}
}
}
//
public class HuffmanFreq {
char character;
int freq;
HuffmanFreq() {
}
HuffmanFreq(int character,int freq) {
this.character = (char)character;
this.freq = freq;
}
char getCharacter() {
return character;
}
void setCharacter(int character) {
this.character = (char)character;
}
int getFreq() {
return freq;
}
void setFreq(int freq) {
this.freq = freq;
}
byte[] infoToByte(){
byte[] bt = new byte[6];
byte[] b1 = ByteAnd8Types.charToByte(character);
for(int i= 0; i < b1.length;i++){
bt[i] = b1[i];
}
byte[] b2 = ByteAnd8Types.intToBytes2(freq);
int index = 2;
for(int i= 0; i < b2.length;i++){
bt[index++] = b2[i];
}
return bt;
}
@Override
public String toString() {
return "Huffman [character=" + character + ", freq=" + freq + "]";
}
}
//treeSize
private void creatTree(int treeSize){
int temp;
treeList = new ArrayList<HuffTreeNode>();
for(int i = 0; i < treeSize; i++){
HuffTreeNode node = new HuffTreeNode();
treeList.add(i, node);
}
for(int i = 0; i < charCount; i++){
HuffTreeNode node = treeList.get(i);
node.freq.freq = charList.get(i).getFreq();
node.freq.character = charList.get(i).getCharacter();
node.left = -1;
node.right = -1;
node.use = 0;
}
for(int i = charCount; i < treeSize; i++){
int index = i;
HuffTreeNode node = treeList.get(i);
node.use = 0;
node.freq.character = '#';
node.right = searchmin(index);
node.left = searchmin(index);
node.freq.freq = treeList.get(node.right).freq.freq + treeList.get(node.left).freq.freq;
temp = searchmin(++index);
if(temp == -1){
break;
}
treeList.get(temp).use = 0;
}
}
private int searchmin(int count){
int minindex = -1;
for(int i = 0; i < count; i++){
if(treeList.get(i).use == 0){
minindex = i;
break;
}
}
if(minindex == -1){
return -1;
}
for(int i = 0; i < count; i++){
if((treeList.get(i).freq.freq <= treeList.get(minindex).freq.freq) && treeList.get(i).use == 0){
minindex = i;
}
}
treeList.get(minindex).use = 1;
return minindex;
}
private void bulidhuftreecode(int root, String str){
if(treeList.get(root).getLeft() != -1 && treeList.get(root).getRight() != -1){
bulidhuftreecode(treeList.get(root).getLeft(), str+"0");
bulidhuftreecode(treeList.get(root).getRight(), str + "1");
}
else{
treeList.get(root).code = str;
}
}
4.하 브 만 인 코딩 은 문 자 를 대체 하여 압축 합 니 다.압축 하기 전에 먼저 파일 헤더(파일 표지,문자 수량,마지막 바이트 유효 위치,비밀번호)문자 와 그 주파수 의 표를 파일 에 기록 하여 압축 을 풀 수 있 도록 해 야 합 니 다.
public void creatCodeFile(String path) throws Exception{
byte value = 0;
int index = 0;
int arr[] = new int[256];
int intchar;
for(int i = 0; i < charCount; i++){
arr[treeList.get(i).freq.character] = i;
}
File file = new File(path);
if(!file.exists()){
if(!file.createNewFile()){
throw new Exception(" ");
}
}
int count = charList.size();
HuffmanHead head = new HuffmanHead(count, howlongchar(count), password);
//
this.write = new RandomAccessFile(file, "rw");
write.write(head.InfoToByte());
//
for(HuffmanFreq freq : charList){
byte[] bt = freq.infoToByte();
write.write(bt);
}
// ，
byte[] readBuffer = new byte[BUFFER_SIZE];
while((intchar = read.read(readBuffer))!= -1){
ProgressBar.SetCurrent(read.getFilePointer());
for(int i = 0; i < intchar;i++){
int temp = readBuffer[i]& 0xff;
String code = treeList.get(arr[temp]).code;
char[] chars = code.toCharArray();
for(int j = 0; j < chars.length; j++){
if(chars[j] == '0'){
value = CLR_BYTE(value, index);
}
if(chars[j] == '1'){
value = SET_BYTE(value, index);
}
if(++index >= 8){
index = 0;
writeInBuffer(value);
}
}
}
}
//
// while((intchar = is.read()) != -1){
// String code = treeList.get(arr[intchar]).code;
// char[] chars = code.toCharArray();
//
// for(int i = 0; i < chars.length; i++){
// if(chars[i] == '0'){
// value = CLR_BYTE(value, index);
// }
// if(chars[i] == '1'){
// value = SET_BYTE(value, index);
// }
// if(++index >= 8){
// index = 0;
// oos.write(value);
// }
// }
// }
if(index != 0){
writeInBuffer(value);
}
byte[] Data = Arrays.copyOfRange(writeBuffer, 0, writeBufferSize);
write.write(Data);
write.close();
read.close();
}
// ， 1
byte SET_BYTE(byte value, int index){
return (value) |= (1 << ((index) ^ 7));
}
// ， 0
byte CLR_BYTE(byte value, int index){
return (value) &= (~(1 << ((index) ^ 7)));
}
// 0,0 false,1 true
boolean GET_BYTE(byte value, int index){
return ((value) & (1 << ((index) ^ 7))) != 0;
}
private void writeInBuffer(byte value) throws Exception {
if(writeBufferSize < BUFFER_SIZE){
writeBuffer[writeBufferSize] = value;
if(++writeBufferSize >= BUFFER_SIZE){
write.write(writeBuffer);
writeBufferSize = 0;
}
} else{
throw new Exception(" ");
}
}1.파일 에 기 록 된 문자 통 계 를 표 에서 읽 어 list 에 넣 기
public void init() throws Exception{
char isHUf = read.readChar();
//
if(isHUf != ' '){
throw new Exception(" HUFFMAN ");
}
this.charCount = read.readChar();
this.treeSize = 2*charCount -1;
this.lastIndex = read.readChar();
int password = read.readInt();
if(password != this.password.hashCode()){
System.out.println(" ");
} else{
System.out.println(" ， ");
}
//
byte[] buffer = new byte[charCount * 6];
read.seek(10);
read.read(buffer, 0, charCount * 6);
ProgressBar.SetCurrent(read.getFilePointer());
for(int i = 0; i < buffer.length; i+=6){
byte[] buff = Arrays.copyOfRange(buffer, i, i+2);
ByteBuffer bb = ByteBuffer.allocate (buff.length);
bb.put (buff);
bb.flip ();
CharBuffer cb = cs.decode (bb);
byte[] buff1 = Arrays.copyOfRange(buffer, i+2, i+6);
int size = ByteAnd8Types.bytesToInt2(buff1, 0);
HuffmanFreq freq = new HuffmanFreq(cb.array()[0], size);
charList.add(freq);
}
}3.하프 만 트 리 로 하프 만 인 코딩 생 성(루트 노드 부터 경로 왼쪽 은 0,오른쪽 은 1)(상기 코드 와 동일)
4.파일 마다 바 이 트 를 옮 겨 다 니 며 하프 만 인 코딩 에 따라 해당 하 는 문 자 를 찾 아 새 파일 에 쓰기
public void creatsourcefile(String pathname) throws Exception{
int root = treeList.size() - 1;
int fininsh = 1;
long len;
File file = new File(pathname);
if(!file.exists()){
if(!file.createNewFile()){
throw new Exception(" ");
}
}
write = new RandomAccessFile(file, "rw");
int intchar;
byte[] bytes = new byte[1<<18];
int index = 0;
while((intchar = read.read(bytes))!= -1){
len = read.getFilePointer();
ProgressBar.SetCurrent(len);
for(int i = 0; i < intchar;i++){
for(;index < 8 && fininsh != 0;){
if(GET_BYTE(bytes[i], index)){
root = treeList.get(root).right;
} else{
root = treeList.get(root).left;
}
if(treeList.get(root).right== -1 && treeList.get(root).left == -1){
byte temp = (byte)treeList.get(root).freq.character;
writeInBuffer(temp);
root = treeList.size() - 1;
}
index++;
if(len == this.goalfilelenth && i == intchar-1){
if(index >= this.lastIndex){
fininsh = 0;
}
}
}
index = 0;
}
}
byte[] Data = Arrays.copyOfRange(writeBuffer, 0, writeBufferSize);
write.write(Data);
write.close();
write.close();
read.close();
}
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
