다음과 같이 코드 코드를 복사합니다.
//허프만 코딩의 구현 클래스
공개 클래스 HffmanCoding {
private int charsAndWeight[][];// [][0]은 문자이고, [][1]은 문자의 가중치(횟수)를 저장합니다.
private int hfmcoding[][];//스토리지 허프만 트리
private int i = 0; // 루프 변수
개인 문자열 hcs[];
공개 HffmanCoding(int[][] 문자) {
// TODO 생성자
charsAndWeight = new int[chars.length][2];
charsAndWeight = 문자;
hfmcoding = new int[2 * chars.length - 1][4];//허프만 트리를 위한 공간 할당
}
//허프만 트리 구현
공개 무효 코딩() {
int n = charsAndWeight.length;
만약(n==0)
반품;
int m = 2 * n - 1;
//허프만 트리 초기화
for (i = 0; i < n; i++) {
hfmcoding[i][0] = charsAndWeight[i][1];//허프만 트리의 가중치 초기화
hfmcoding[i][1] = 0;//허프만 트리의 루트 노드 초기화
hfmcoding[i][2] = 0;//허프만 트리의 왼쪽 자식 초기화
hfmcoding[i][3] = 0;//허프만 트리의 오른쪽 자식을 초기화합니다.
}
for (i = n; i < m; i++) {
hfmcoding[i][0] = 0;//허프만 트리의 가중치 초기화
hfmcoding[i][1] = 0;//허프만 트리의 루트 노드 초기화
hfmcoding[i][2] = 0;//허프만 트리의 왼쪽 자식 초기화
hfmcoding[i][3] = 0;//허프만 트리의 오른쪽 자식을 초기화합니다.
}
//허프만 트리 구축
for (i = n; i < m; i++) {
int s1[] = select(i); // 허프만 트리에서 부모가 0인 가장 작은 가중치를 갖는 노드를 찾습니다.
hfmcoding[s1[0]][1] = i;// 허프만 트리의 최소값에 대해 부모에게 지불
hfmcoding[s1[1]][1] = i;
hfmcoding[i][2] = s1[0];//새 노드의 왼쪽 자식
hfmcoding[i][3] = s1[1];//새 노드의 오른쪽 자식
hfmcoding[i][0] = hfmcoding[s1[0]][0] + hfmcoding[s1[1]][0];//새 노드의 가중치는 왼쪽 및 오른쪽 자식 노드의 가중치의 합입니다.
}
}
//부모가 0이고 가중치가 가장 작은 노드를 찾습니다.
개인 int[] select(int w) {
// TODO 자동 생성된 메서드 스텁
int s[] = { -1, -1 }, j = 0; // s1은 가중치가 가장 작고 부모가 0인 노드의 시퀀스 번호이고, i는 루프 변수입니다.
int min1 = 32767, min2 = 32767;
for (j = 0; j < w; j++) {
if (hfmcoding[j][1] == 0) {// 아직 이진 트리를 구성하지 않은 노드(부모가 없는 노드)에서만 검색합니다.
if (hfmcoding[j][0] < min1) {
최소2 = 최소1;
s[1] = s[0];
min1 = hfmcoding[j][0];
s[0] = j;
} else if (hfmcoding[j][0] < min2) {
min2 = hfmcoding[j][0];
s[1] = j;
}
}
}
반환 s;
}
public String[] CreateHCode() {// 허프만 트리를 기반으로 허프만 코드 찾기
int n = charsAndWeight.length;
int i, f, c;
문자열 hcodeString = "";
hcs = 새로운 문자열[n];
for (i = 0; i < n; i++) {// 허프만 트리를 기반으로 허프만 코드 찾기
c = 나;
hcodeString = "";
f = hfmcoding[i][1]; // f는 허프만 트리의 루트 노드입니다.
while (f != 0) {//트리의 루트 노드까지 순차적으로
if (hfmcoding[f][2] == c) {// 왼쪽 하위 노드를 처리합니다.
hcodeString += "0";
} 또 다른 {
hcodeString += "1";
}
c = f;
f = hfmcoding[f][1];
}
hcs[i] = new String(new StringBuffer(hcodeString).reverse());
}
hcs를 반환합니다.
}
public String show(String s) {// 문자열 인코딩 표시
문자열 textString = "";
문자 c[];
정수 k = -1;
c = 새로운 문자[s.length()];
c = s.toCharArray(); // 문자열을 문자 배열로 변환
for (int i = 0; i < c.length; i++) {
k = c[i];
for(int j = 0; j < charsAndWeight.length; j++)
if (k == charsAndWeight[j][0])
textString += hcs[j];
}
텍스트 문자열을 반환합니다.
}
// 허프만 코딩 디컴파일
공개 문자열 reCoding(문자열 s) {
String text = "";//저장소 디컴파일된 문자
int k = 0, m = hfmcoding.length - 1;//루트 노드에서 쿼리 시작
문자 c[];
c = 새로운 문자[s.length()];
c = s.toCharArray();
k = m;
for (int i = 0; i < c.length; i++) {
if (c[i] == '0') {
k = hfmcoding[k][2];//k 값은 루트 노드의 왼쪽 자식 시퀀스 번호입니다.
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 리프 노드인지 확인, 조건(왼쪽 및 오른쪽 자식 모두 0)
{
텍스트 += (문자) charsAndWeight[k][0];
k = m;
}
}
if (c[i] == '1') {
k = hfmcoding[k][3];//k 값은 루트 노드 오른쪽 자식의 시퀀스 번호입니다.
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 리프 노드인지 확인, 조건(왼쪽 및 오른쪽 자식 모두 0)
{
텍스트 += (문자) charsAndWeight[k][0];
k = m;
}
}
}
텍스트 반환;
}
}