Entry
แแ แกแขแแขแแแจแ แแแกแแฃแแ แแ แฐแแคแแแแแก แชแแแแแ แแแแแ แแแแแ, แแกแแแ แแแก แแแแแงแแแแแแแ แแแแแชแแแแ แจแแแฃแแจแแแกแแก.
แจแแแแแแ, แฉแแแ แแแแฌแแ แ แแแ แขแแ แแ แฅแแแก. แแก แฃแแแ แแงแ
แแแขแแ แ แแแแ แแแแ
แฉแแแฃแแแแ แแ แขแแฅแกแขแฃแ แคแแแแจแ แแ แแ แกแแแแแแ แแแจแแคแ แฃแแแ 8 แแแขแแ (ASCII แแแแแ แแแ) แแ 16 (Unicode แแแแแ แแแ). แจแแแแแแ, แแแแแแฎแแแแแ ASCII แแแแแ แแแแก. แแแแแแแแแ, แแแฆแแ แกแขแ แแฅแแแ s1 = "SUSIE SAYS IT IS EASYn". แกแแแ แแ แฏแแแจแ, แกแขแ แแฅแแแจแ 22 แกแแแแแแแ, แ แ แแฅแแ แฃแแแ, แแแขแแ แแแแแก แแ แแฎแแแ แฎแแแแก แกแแแแแแแก แฉแแแแแแ - 'n'. แแ แฎแแแแก แจแแแชแแแแ แคแแแแ แแฌแแแแก 22*8 = 176 แแแขแก. แแแจแแแแ แฉแแแแแ แแแแฎแแ: แแ แแก แแฃ แแ แ แ แแชแแแแแแฃแ แ 8 แแแขแแก แแแแแงแแแแแ 1 แกแแแแแแแก แแแจแแคแแ แแกแแแแก? แฉแแแ แแ แแแงแแแแแ แงแแแแ ASCII แกแแแแแแแก. แแแจแแแแช แแ, แแฃ แแกแแแ แงแแคแแแแงแแแแ, แฃแคแ แ แ แแชแแแแแแฃแ แ แแฅแแแแแแ, แแแแชแแ แงแแแแแแ แฎแจแแ แ แแกแ - S - แงแแแแแแ แแแแแ แแแแ, แฎแแแ แฃแแจแแแแแแกแ แแกแแกแแแแก - T (แแ U, แแ 'n') - แฃแคแ แ แแแแแแขแฃแ แ แแแแ. แแก แแ แแก แฐแแคแแแแแก แแแแแ แแแแ: แแฅแแแ แฃแแแ แแแแแแ แกแแฃแแแแแกแ แแแแแ แแแแก แแแ แแแแขแ, แ แแแแแจแแช แคแแแแ แแฅแแแแ แแแแแแแแฃแ แ แฌแแแแก. แกแแแกแแแแ แแแ แแแแฃแ แแ, แ แแ แกแฎแแแแแกแฎแแ แกแแแแแแแก แแฅแแแแ แกแฎแแแแแกแฎแแ แแแแแก แกแแแ แซแ - แแก แแ แแก แแแแแ แแแแแก แกแแคแฃแซแแแแ.
แแแแแ แแแ
แ แแขแแ แแ แแแแชแแ แกแแแแแแแก 'S' แแแแ, แแแแแแแแแ, 1 แแแขแแแแ: 0 แแ 1. แแแแแ แแงแแก 1. แจแแแแแ แแแแ แ แงแแแแแแ แแแแ แชแแแแแฃแแ แกแแแแแแ - ' ' (แกแแแ แชแ) - แแแแชแแแ 0-แก. แฌแแ แแแแแแแแแ, แแฅแแแ แแแแฌแงแแ แแแจแแคแ แแ แแฅแแแแ แจแแขแงแแแแแแแ - แแแจแแคแ แฃแแ แกแขแ แแฅแแแ s1 - แแ แฎแแแแแ, แ แแ แแแแ แแฌแงแแแ 1-แแ. แแแจ, แ แ แฃแแแ แแแแแแแแ: แแ แแก แกแแแแแแ S, แแฃ แกแฎแแ แกแแแแแแ, แแแแแแแแแ A? แแฅแแแแ แแแแแแแแแแ แ, แฉแแแแแ แแแแจแแแแแแแแแ แฌแแกแ:
แแ แชแแ แแ แแแแ แแ แฃแแแ แแงแแก แกแฎแแ แแ แแคแแฅแกแ
แแก แฌแแกแ แแ แแก แแแแแ แแแแแก แแแกแแฆแแแ. แแแ แแแแ, แแแแแก แจแแฅแแแ แแฌแงแแแ แกแแฎแจแแ แแก แชแฎแ แแแแ, แ แแแแแแช แแแฃแแแแแแก แแแแแแฃแแ แกแแแแแแแก แกแแฎแจแแ แแแ (แจแแแแฎแแแแแแแก แ แแแแแแแแแแ):
แงแแแแแแ แแแขแ แแแแแแแแก แแฅแแแ แกแแแแแแแแแ แฃแแแ แแงแแก แแแแแ แแแฃแแ แงแแแแแแ แแแแแแแแ แจแแกแแซแแแแแแแ แแแขแแแแก แ แแแแแแแแ. แแ แแแแชแแ แแ แ-แแ แแ แจแแกแแซแแ แแแแแก แชแฎแ แแแแก แแแแแแแแก:
แแกแ แ แแ, แแแแแ แแแฃแแ แจแแขแงแแแแแแแ แแกแ แแแแแแงแฃแ แแแ:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
แแแแแแฃแแ แกแแแแแแแก แแแแ แแแแแแงแแแ แแแขแแ แแแแแ. แแก แแแแแแแแแ แแ แแแฎแแแแ แจแแแฃแแจแฃแ แคแแแแจแ!
แฉแแแแแ แแแแฎแแ: แ แแแแ แแแแคแแฅแ แ แแ แแฎแแแแแแ แแแแแ แ แแแแ แจแแฅแแแแก แแแแแก แชแฎแ แแแ? แแก แฅแแแแแ แแฅแแแแ แแแแฎแแแฃแแ.
แฐแแคแแแแแก แฎแแก แแจแแแแแ
แแก แแ แแก แกแแแแช แแแแแ แฃแแ แกแแซแแแแ แฎแแแแ แแแแแแ แกแแแแจแแแแแจแ. แแ แแแแ แแแฃแแแ, แแฅ แแ แแแแญแแ แแแแแ แซแแแแแก, แฉแแกแแแก แแ แฌแแจแแแก แแแแแแแแ. แแฅ แแ แแก แฎแแก แกแขแ แฃแฅแขแฃแ แ แฏแแแแจแ:
public class Node {
private int frequence;
private char letter;
private Node leftChild;
private Node rightChild;
...
}
class BinaryTree {
private Node root;
public BinaryTree() {
root = new Node();
}
public BinaryTree(Node root) {
this.root = root;
}
...
}
แแก แแ แแ แแก แกแ แฃแแ แแแแ, แกแ แฃแแ แแแแ แแฅแแแแ แฅแแแแแ.
แแฅ แแ แแก แแแแแ แแแแ แฎแแก แแกแแจแแแแแแแ:
- แจแแฅแแแแแ Node แแแแแฅแขแ แจแแขแงแแแแแแแแแแแแ แแแแแแฃแแ แกแแแแแแแกแแแแก (แกแขแ แแฅแแแ s1). แฉแแแแก แจแแแแฎแแแแแจแ, แแฅแแแแ 9 แแแแแซแ (Node แแแแแฅแขแแแ). แแแแแแฃแแ แแแแแซแ แจแแแแแแ แแ แ แแแแแชแแแแ แแแแแกแแแแ: แกแแแแแแ แแ แกแแฎแจแแ แ
- แจแแฅแแแแแ แฎแแก แแแแแฅแขแ (BinaryTree) แแแแแแฃแแ แแแแแซแแก แแแแแซแแกแแแแก. แแแแแซแ แฎแแแแ แฎแแก แคแแกแแ.
- แฉแแแแ แแก แฎแแแแ แแ แแแ แแขแแขแฃแ แ แแแจแ. แ แแช แฃแคแ แ แแแแแแแ แกแแฎแจแแ แ, แแแ แฃแคแ แ แแแฆแแแแ แแ แแแ แแขแแขแ. แแแ แแแแ, แแแแแแแแแกแแก แงแแแแแแแแก แจแแแ แฉแแแ แงแแแแแแ แแแแแแ แกแแฎแจแแ แแก แฎแ.
แจแแแแแแ, แแฅแแแ แฃแแแ แแแแแแแแ แชแแแแฃแ แแ แจแแแแแแ:
- แแแแแฆแแ แแ แ แฎแ แแ แแแ แแขแแขแฃแแ แ แแแแแแ แแ แแแฎแแแแ แแกแแแ แแฎแแแ แแแแแซแแก แจแแแแแแแ (แแฎแแแ แจแแฅแแแแแ แแแแแซแ แแกแแก แแแ แแจแ). แแฎแแแ แแแแแซแแก แกแแฎแจแแ แ แฃแแ แแก แแ แ แจแแแแแแแแแแ แฎแแก แกแแฎแจแแ แแแแแก แฏแแแก.
- แแ แแแแแซแแกแแแแก แจแแฅแแแแแ แแ แแแแแซแแ แแแคแฃแซแแแแฃแแ แฎแ. แฉแแแแ แแก แฎแ แแกแแ แแ แแแ แแขแแขแฃแ แ แแแจแ. (แ แแแแแ แฎแแก แแฎแแแ แกแแฎแจแแ แ แแฅแแก, แแก แกแแแแ แแฃแแแ แแฎแแ แแแแแแแ แแแฎแแแแแ แ แแแจแ)
- แแแแแ แซแแแแ 1 แแ 2 แแแแแฏแแแ, แกแแแแ แ แแแจแ แแ แแแ แฉแแแ แแ แแ แฎแ - แฐแแคแแแแแก แฎแ
แแแแแแฎแแแแ แแก แแแแแ แแแแ แกแขแ แแฅแแแแ s1:
แแฅ แกแแแแแแ "lf" (linefeed) แแฆแแแจแแแแก แแฎแแ แฎแแแก, "sp" (แกแแแ แชแ) แแ แแก แกแแแ แชแ.
แ แ แแ แแก แจแแแแแแ?
แฉแแแ แแแแแฆแแ แฐแแคแแแแแก แฎแ. แฒแฒแฒ แฒแฒ. แแ แ แ แแฃแงแแ แแแก? แแกแแแ แแแแก แฃแคแแกแแ แแ แแแแฆแแแแ แแ แจแแแแแ, แแฅแแแ แฃแแแ แแแแแ แแ แงแแแแ แจแแกแแซแแ แแแแแแ แคแแกแแแแแ แฎแแก แคแแแแแแแแแ. แฉแแแ แแแแแแฎแแแแแ, แ แแ แแแแแฌแแ แแ 0-แแก แแแแแก, แแฃ แแก แแแแงแแแแ แ แแแ แชแฎแแแ แจแแแแแแ แแ 1, แแฃ แแก แแแแงแแแแ แ แแแ แฏแแแแ. แแแแชแ แแ แ แแ แแแฅแแแ, แแ แแฆแแแจแแแแแจแ, แกแแแแแแแก แแแแ แแ แแก แแแ แฎแแก แคแแกแแแแแ แคแแแแแแแ, แ แแแแแแช แจแแแชแแแก แแแแแ แกแแแแแแแก.
แแแ แแแแ, แแแแแแแก แชแฎแ แแแ แแฆแแแฉแแแ. แแแแแแแแแกแฌแแแแ, แ แแ แแฃ แแแแแแแแแแกแฌแแแแแ แแ แชแฎแ แแแก, แจแแแแแซแแแ แแแแแกแแแแแ แแแแแแฃแแ แกแแแแแแแก "แฌแแแแแ" - แแก แแ แแก แแแกแ แแแแแก แกแแแ แซแ. แจแแแแแ, แจแแแฃแแจแฃแแ แคแแ แแแ, แฌแงแแ แแก แคแแแแ แแฌแแแแก: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 แแแขแ . แแแแแแแ แแฌแแแแแ 176 แแแขแก. แแแแขแแ, แฉแแแ แจแแแแแชแแ แแ แแก 176/65 = 2.7-แฏแแ ! แแแแ แแ แแก แฃแขแแแแแ. แแกแแแ แแแแแคแแ แแแแ แแแแแแแแ แกแแแแ แแฃแแแ. แ แแขแแ? แแแแแ แชแแขแ แแแแแแแแแแแ แแฅแแแแ แแแแฎแแแฃแแ.
แแแแแแแ แแแ
แแกแ, แแแแแ แงแแแแแแ แแแ แขแแแ แ แแ แแ แแก แแแจแแคแแ แ. แแคแแฅแ แแ, แแแแ แแ แแฅแแแแแแแแ แแแแแแชแแแแ, แ แแ แจแแแฃแแจแฃแแ แคแแแแแก แจแแฅแแแ แจแแฃแซแแแแแแแ, แงแแแแแแแแ แ แแแแแจแแแแแแแก แแแ แแจแ, แแฃ แ แแแแ แแงแ แแแแแ แแแฃแแ - แฉแแแ แแแ แจแแแซแแแแ แแแก แแแจแแคแแ แแก! แแแแฎ, แแแแฎ, แแแแแญแแ แแ แแแแก แแแชแแแแแแ แแแ, แแแแ แแ แแ แฃแแแ แจแแแฅแแแ แขแแฅแกแขแฃแ แ แคแแแแแก table.txt แจแแแฃแแจแแแก แชแฎแ แแแแ:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
แชแฎแ แแแแก แฉแแแแฌแแ แ แกแแฎแแ โแกแแแแแแโ โแกแแแแแแ แแแแโ. แ แแขแแ แแ แแก 01110 แกแแแแแแแก แแแ แแจแ? แกแแแแแแแแแแจแ, แแก แแ แแก แกแแแแแแแแ, แแฎแแแแ java แแแกแขแ แฃแแแแขแแแแ, แ แแแแแแกแแช แแแงแแแแ แคแแแแจแ แแแแแขแแแแกแแก, แแฎแแแ แฎแแแแก แกแแแแแแ - 'n' - แแแ แแแแฅแแแแแ แแฎแแ แฎแแแแ (แ แแช แแ แฃแแแ แกแฃแแแแฃแ แแ แแฆแแ แแแก). แแฅแแแแ แแแแแแแแแแ แ, แชแแ แแแแ แฎแแแ แแแแแ แแ แแก แกแแแแแแ 01110 แแแแแกแแแแก. 00 แแแแแกแแแแก แกแแแแแแ แแ แแก แกแแแ แชแ แกแขแ แแฅแแแแก แแแกแแฌแงแแกแจแ. แแแฃแงแแแแแแแแ แฃแแแ แแแฅแแ, แ แแ แชแฎแ แแแแก แจแแแแฎแแแก แแก แแแแแแ แจแแแซแแแแ แแงแแก แงแแแแแแ แแ แแชแแแแแแฃแ แ แฉแแแแ แฎแแแแก แแแแคแแชแแแแขแแกแแแแก. แแแแ แแ แแแแแแ แแแกแแแแแ แแ แแแแฎแแ แชแแแแแแแ. แแแฎแแ แฃแแ แแแฅแแแแ แแแแแกแแแแ แแฅแแแแ แ แแแแแแแแแชแแแแ แแแแแแขแแ แแแจแ แแแขแแแแแแชแแแก แจแแกแแฎแแ.
แแ แชแฎแ แแแแ แแแกแ แแแจแแคแแ แ แซแแแแแ แแแแแแแ. แแแแแฎแกแแแแ แ แ แฌแแกแแ แแแฎแแแแซแฆแแแแแแแ แแแแแ แแแแก แจแแฅแแแแกแแก:
แแ แชแแ แแ แแแแ แแ แฃแแแ แแงแแก แกแฎแแ แแ แแคแแฅแกแ
แแฅ แแก แแแแแจแแแก แฎแแแจแแแฌแงแแ แ แแแก. แฉแแแ แแแแแฎแฃแแแแ แแแข-แแแขแ แแแแแแแแแแ แแแแ แแ แ แแแแ แช แแ แแแฆแแแฃแแ แกแขแ แแฅแแแ, แ แแแแแแช แจแแแแแแ แฌแแแแแฎแฃแแ แแแขแแแแกแแแแ, แแแแฎแแแแ แกแแแแแแแก แกแแแแแแแก แจแแกแแแแแแก แแแจแแคแแ แแก, แแแจแแแแ แแแชแแ, แ แแ แกแแแแแแแก แกแแแแแแ (แแ แแฎแแแแ แแก!) แแงแ แแแแแ แแแฃแแ. แจแแแแแแ, แฉแแแ แแฌแแ แ แกแแแแแแแก แแแแแแแ แแแแก แกแขแ แแฅแแแแ (แกแขแ แแฅแแแ, แ แแแแแแช แจแแแชแแแก แแแแแแแ แแแฃแ แจแแขแงแแแแแแแแก), แแแแแแแงแแแแแ d แกแขแ แแฅแแแก แแ แแแแแฎแฃแแแแ แแแจแแคแ แฃแ แคแแแแก แจแแแแแแแจแ.
ะ ะตะฐะปะธะทะฐัะธั
แแ แแ แแแแแแชแแ แ แฉแแแ แแแแ แแ แฅแแแแก แแแฌแแ แแ. แแแแแ แฅแแแ แแแแแ แแกแแ แ.
แฒแแแแแแ แแแฌแงแแแ. แฃแแแ แแแแแก แงแแแแแกแ, แฉแแแ แแฌแแ แ Node แแแแกแก:
public class Node {
private int frequence;//ัะฐััะพัะฐ
private char letter;//ะฑัะบะฒะฐ
private Node leftChild;//ะปะตะฒัะน ะฟะพัะพะผะพะบ
private Node rightChild;//ะฟัะฐะฒัะน ะฟะพัะพะผะพะบ
public Node(char letter, int frequence) { //ัะพะฑััะฒะตะฝะฝะพ, ะบะพะฝััััะบัะพั
this.letter = letter;
this.frequence = frequence;
}
public Node() {}//ะฟะตัะตะณััะทะบะฐ ะบะพะฝัััััะพัะฐ ะดะปั ะฑะตะทัะผัะฝะฝัั
ัะทะปะพะฒ(ัะผ. ะฒััะต ะฒ ัะฐะทะดะตะปะต ะพ ะฟะพัััะพะตะฝะธะธ ะดะตัะตะฒะฐ ะฅะฐััะผะฐะฝะฐ)
public void addChild(Node newNode) {//ะดะพะฑะฐะฒะธัั ะฟะพัะพะผะบะฐ
if (leftChild == null)//ะตัะปะธ ะปะตะฒัะน ะฟัััะพะน=> ะฟัะฐะฒัะน ัะพะถะต=> ะดะพะฑะฐะฒะปัะตะผ ะฒ ะปะตะฒัะน
leftChild = newNode;
else {
if (leftChild.getFrequence() <= newNode.getFrequence()) //ะฒ ะพะฑัะตะผ, ะปะตะฒัะผ ะฟะพัะพะผะบะพะผ
rightChild = newNode;//ััะฐะฝะตั ัะพั, ั ะบะพะณะพ ะผะตะฝััะต ัะฐััะพัะฐ
else {
rightChild = leftChild;
leftChild = newNode;
}
}
frequence += newNode.getFrequence();//ะธัะพะณะพะฒะฐั ัะฐััะพัะฐ
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public int getFrequence() {
return frequence;
}
public char getLetter() {
return letter;
}
public boolean isLeaf() {//ะฟัะพะฒะตัะบะฐ ะฝะฐ ะปะธัั
return leftChild == null && rightChild == null;
}
}
แแฎแแ แฎแ:
class BinaryTree {
private Node root;
public BinaryTree() {
root = new Node();
}
public BinaryTree(Node root) {
this.root = root;
}
public int getFrequence() {
return root.getFrequence();
}
public Node getRoot() {
return root;
}
}
แแ แแแ แแขแแขแฃแแ แ แแแ:
import java.util.ArrayList;//ะดะฐ-ะดะฐ, ะพัะตัะตะดั ะฑัะดะตั ะฝะฐ ะฑะฐะทะต ัะฟะธัะบะฐ
class PriorityQueue {
private ArrayList<BinaryTree> data;//ัะฟะธัะพะบ ะพัะตัะตะดะธ
private int nElems;//ะบะพะป-ะฒะพ ัะปะตะผะตะฝัะพะฒ ะฒ ะพัะตัะตะดะธ
public PriorityQueue() {
data = new ArrayList<BinaryTree>();
nElems = 0;
}
public void insert(BinaryTree newTree) {//ะฒััะฐะฒะบะฐ
if (nElems == 0)
data.add(newTree);
else {
for (int i = 0; i < nElems; i++) {
if (data.get(i).getFrequence() > newTree.getFrequence()) {//ะตัะปะธ ัะฐััะพัะฐ ะฒััะฐะฒะปัะตะผะพะณะพ ะดะตัะตะฒะฐ ะผะตะฝััะต
data.add(i, newTree);//ัะตะผ ัะฐัั. ัะตะบััะตะณะพ, ัะพ cะดะฒะธะณะฐะตะผ ะฒัะต ะดะตัะตะฒัั ะฝะฐ ะฟะพะทะธัะธัั
ัะฟัะฐะฒะฐ ะฝะฐ 1 ััะตะนะบั
break;//ะทะฐัะตะผ ััะฐะฒะธะผ ะฝะพะฒะพะต ะดะตัะตะฒะพ ะฝะฐ ะฟะพะทะธัะธั ัะตะบััะตะณะพ
}
if (i == nElems - 1)
data.add(newTree);
}
}
nElems++;//ัะฒะตะปะธัะธะฒะฐะตะผ ะบะพะป-ะฒะพ ัะปะตะผะตะฝัะพะฒ ะฝะฐ 1
}
public BinaryTree remove() {//ัะดะฐะปะตะฝะธะต ะธะท ะพัะตัะตะดะธ
BinaryTree tmp = data.get(0);//ะบะพะฟะธััะตะผ ัะดะฐะปัะตะผัะน ัะปะตะผะตะฝั
data.remove(0);//ัะพะฑััะฒะตะฝะฝะพ, ัะดะฐะปัะตะผ
nElems--;//ัะผะตะฝััะฐะตะผ ะบะพะป-ะฒะพ ัะปะตะผะตะฝัะพะฒ ะฝะฐ 1
return tmp;//ะฒะพะทะฒัะฐัะฐะตะผ ัะดะฐะปะตะฝะฝัะน ัะปะตะผะตะฝั(ัะปะตะผะตะฝั ั ะฝะฐะธะผะตะฝััะตะน ัะฐััะพัะพะน)
}
}
แแแแกแ, แ แแแแแแช แฅแแแแก แฐแแคแแแแแก แฎแแก:
public class HuffmanTree {
private final byte ENCODING_TABLE_SIZE = 127;//ะดะปะธะฝะฐ ะบะพะดะธัะพะฒะพัะฝะพะน ัะฐะฑะปะธัั
private String myString;//ัะพะพะฑัะตะฝะธะต
private BinaryTree huffmanTree;//ะดะตัะตะฒะพ ะฅะฐััะผะฐะฝะฐ
private int[] freqArray;//ัะฐััะพัะฝะฐั ัะฐะฑะปะธัะฐ
private String[] encodingArray;//ะบะพะดะธัะพะฒะพัะฝะฐั ัะฐะฑะปะธัะฐ
//----------------constructor----------------------
public HuffmanTree(String newString) {
myString = newString;
freqArray = new int[ENCODING_TABLE_SIZE];
fillFrequenceArray();
huffmanTree = getHuffmanTree();
encodingArray = new String[ENCODING_TABLE_SIZE];
fillEncodingArray(huffmanTree.getRoot(), "", "");
}
//--------------------frequence array------------------------
private void fillFrequenceArray() {
for (int i = 0; i < myString.length(); i++) {
freqArray[(int)myString.charAt(i)]++;
}
}
public int[] getFrequenceArray() {
return freqArray;
}
//------------------------huffman tree creation------------------
private BinaryTree getHuffmanTree() {
PriorityQueue pq = new PriorityQueue();
//ะฐะปะณะพัะธัะผ ะพะฟะธัะฐะฝ ะฒััะต
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {//ะตัะปะธ ัะธะผะฒะพะป ัััะตััะฒัะตั ะฒ ัััะพะบะต
Node newNode = new Node((char) i, freqArray[i]);//ัะพ ัะพะทะดะฐัั ะดะปั ะฝะตะณะพ Node
BinaryTree newTree = new BinaryTree(newNode);//ะฐ ะดะปั Node ัะพะทะดะฐัั BinaryTree
pq.insert(newTree);//ะฒััะฐะฒะธัั ะฒ ะพัะตัะตะดั
}
}
while (true) {
BinaryTree tree1 = pq.remove();//ะธะทะฒะปะตัั ะธะท ะพัะตัะตะดะธ ะฟะตัะฒะพะต ะดะตัะตะฒะพ.
try {
BinaryTree tree2 = pq.remove();//ะธะทะฒะปะตัั ะธะท ะพัะตัะตะดะธ ะฒัะพัะพะต ะดะตัะตะฒะพ
Node newNode = new Node();//ัะพะทะดะฐัั ะฝะพะฒัะน Node
newNode.addChild(tree1.getRoot());//ัะดะตะปะฐัั ะตะณะพ ะฟะพัะพะผะบะฐะผะธ ะดะฒะฐ ะธะทะฒะปะตัะตะฝะฝัั
ะดะตัะตะฒะฐ
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode);
} catch (IndexOutOfBoundsException e) {//ะพััะฐะปะพัั ะพะดะฝะพ ะดะตัะตะฒะพ ะฒ ะพัะตัะตะดะธ
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
//-------------------encoding array------------------
void fillEncodingArray(Node node, String codeBefore, String direction) {//ะทะฐะฟะพะปะฝะธัั ะบะพะดะธัะพะฒะพัะฝัั ัะฐะฑะปะธัั
if (node.isLeaf()) {
encodingArray[(int)node.getLetter()] = codeBefore + direction;
} else {
fillEncodingArray(node.getLeftChild(), codeBefore + direction, "0");
fillEncodingArray(node.getRightChild(), codeBefore + direction, "1");
}
}
String[] getEncodingArray() {
return encodingArray;
}
public void displayEncodingArray() {//ะดะปั ะพัะปะฐะดะบะธ
fillEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Encoding table====================");
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {
System.out.print((char)i + " ");
System.out.println(encodingArray[i]);
}
}
System.out.println("========================================================");
}
//-----------------------------------------------------
String getOriginalString() {
return myString;
}
}
แแแแกแ, แ แแแแแแช แจแแแชแแแก แแแจแแคแแ แแก/แแแจแแคแ แแแก:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127;//ะดะปะธะฝะฐ ัะฐะฑะปะธัั
private HuffmanTree mainHuffmanTree;//ะดะตัะตะฒะพ ะฅะฐััะผะฐะฝะฐ (ะธัะฟะพะปัะทัะตััั ัะพะปัะบะพ ะดะปั ัะถะฐัะธั)
private String myString;//ะธัั
ะพะดะฝะพะต ัะพะพะฑัะตะฝะธะต
private int[] freqArray;//ัะฐััะพัะฐะฝะฐั ัะฐะฑะปะธัะฐ
private String[] encodingArray;//ะบะพะดะธัะพะฒะพัะฝะฐั ัะฐะฑะปะธัะฐ
private double ratio;//ะบะพัััะธัะธะตะฝั ัะถะฐัะธั
public HuffmanOperator(HuffmanTree MainHuffmanTree) {//for compress
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {}//for extract;
//---------------------------------------compression-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = "";//ะฟัะพะผะตะถััะพัะฝะฐั ัััะพะบะฐ(ะฑะตะท ะดะพะฑะฐะฒะพัะฝัั
ะฝัะปะตะน)
//System.out.println("=============================Compression=======================");
//displayEncodingArray();
for (int i = 0; i < myString.length(); i++) {
intermidiate += encodingArray[myString.charAt(i)];
}
//ะั ะฝะต ะผะพะถะตะผ ะฟะธัะฐัั ะฑะธั ะฒ ัะฐะนะป. ะะพััะพะผั ะฝัะถะฝะพ ัะดะตะปะฐัั ะดะปะธะฝั ัะพะพะฑัะตะฝะธั ะบัะฐัะฝะพะน 8=>
//ะฝัะถะฝะพ ะดะพะฑะฐะฒะธัั ะฝัะปะธ ะฒ ะบะพะฝะตั(ะผะพะถะฝะพ 1, ะฝะตั ัะฐะทะฝะธัั)
byte counter = 0;//ะบะพะปะธัะตััะฒะพ ะดะพะฑะฐะฒะปะตะฝะฝัั
ะฒ ะบะพะฝะตั ะฝัะปะตะน (ะฑะฐะนัะฐ ะฒ ะฟะพะปะฝะต ั
ะฒะฐัะธั: 0<=counter<8<127)
for (int length = intermidiate.length(), delta = 8 - length % 8;
counter < delta ; counter++) {//delta - ะบะพะปะธัะตััะฒะพ ะดะพะฑะฐะฒะปะตะฝะฝัั
ะฝัะปะตะน
intermidiate += "0";
}
//ัะบะปะตะธัั ะบะพะป-ะฒะพ ะดะพะฑะฐะฒะพัะฝัั
ะฝัะปะตะน ะฒ ะฑะธะฝะฐัะฝะพะผ ะฟัะตะดะฐััะฒะปะตะฝะธะธ ะธ ะฟัะพะผะตะถััะพัะฝัั ัััะพะบั
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate;
//ะธะดะตะฐะปะธะทะธัะพะฒะฐะฝะฝัะน ะบะพัััะธัะธะตะฝั
setCompressionRatio();
//System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() {//ะฟะพััะธัะฐัั ะธะดะตะฐะปะธะทะธัะพะฒะฐะฝะฝัะน ะบะพัััะธัะธะตะฝั
double sumA = 0, sumB = 0;//A-the original sum
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {
sumA += 8 * freqArray[i];
sumB += encodingArray[i].length() * freqArray[i];
}
}
ratio = sumA / sumB;
}
public byte[] getBytedMsg() {//final compression
StringBuilder compressedString = new StringBuilder(getCompressedString());
byte[] compressedBytes = new byte[compressedString.length() / 8];
for (int i = 0; i < compressedBytes.length; i++) {
compressedBytes[i] = (byte) Integer.parseInt(compressedString.substring(i * 8, (i + 1) * 8), 2);
}
return compressedBytes;
}
//---------------------------------------end of compression----------------------------------------------------------------
//------------------------------------------------------------extract-----------------------------------------------------
public String extract(String compressed, String[] newEncodingArray) {
String decompressed = "";
String current = "";
String delta = "";
encodingArray = newEncodingArray;
//displayEncodingArray();
//ะฟะพะปััะธัั ะบะพะป-ะฒะพ ะฒััะฐะฒะปะตะฝะฝัั
ะฝัะปะตะน
for (int i = 0; i < 8; i++)
delta += compressed.charAt(i);
int ADDED_ZEROES = Integer.parseInt(delta, 2);
for (int i = 8, l = compressed.length() - ADDED_ZEROES; i < l; i++) {
//i = 8, ั.ะบ. ะฟะตัะฒัะผ ะฑะฐะนัะพะผ ั ะฝะฐั ะธะดะตั ะบะพะป-ะฒะพ ะฒััะฐะฒะปะตะฝะฝัั
ะฝัะปะตะน
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) {//ะตัะปะธ ัะพะฒะฟะฐะปะพ
decompressed += (char)j;//ัะพ ะดะพะฑะฐะฒะปัะตะผ ัะปะตะผะตะฝั
current = "";//ะธ ะพะฑะฝัะปัะตะผ ัะตะบัััั ัััะพะบั
}
}
}
return decompressed;
}
public String getEncodingTable() {
String enc = "";
for (int i = 0; i < encodingArray.length; i++) {
if (freqArray[i] != 0)
enc += (char)i + encodingArray[i] + 'n';
}
return enc;
}
public double getCompressionRatio() {
return ratio;
}
public void displayEncodingArray() {//ะดะปั ะพัะปะฐะดะบะธ
System.out.println("======================Encoding table====================");
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
//if (freqArray[i] != 0) {
System.out.print((char)i + " ");
System.out.println(encodingArray[i]);
//}
}
System.out.println("========================================================");
}
}
แแแแกแ, แ แแแแแแช แฎแแแก แฃแฌแงแแแก แคแแแแจแ แฉแแฌแแ แแก:
import java.io.File;
import java.io.PrintWriter;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.Closeable;
public class FileOutputHelper implements Closeable {
private File outputFile;
private FileOutputStream fileOutputStream;
public FileOutputHelper(File file) throws FileNotFoundException {
outputFile = file;
fileOutputStream = new FileOutputStream(outputFile);
}
public void writeByte(byte msg) throws IOException {
fileOutputStream.write(msg);
}
public void writeBytes(byte[] msg) throws IOException {
fileOutputStream.write(msg);
}
public void writeString(String msg) {
try (PrintWriter pw = new PrintWriter(outputFile)) {
pw.write(msg);
} catch (FileNotFoundException e) {
System.out.println("ะะตะฒะตัะฝัะน ะฟััั, ะธะปะธ ัะฐะบะพะณะพ ัะฐะนะปะฐ ะฝะต ัััะตััะฒัะตั!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
แแแแกแ, แ แแแแแแช แแแแแแแแแก แคแแแแแแแ แแแแฎแแแก:
import java.io.FileInputStream;
import java.io.EOFException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Closeable;
import java.io.File;
import java.io.IOException;
public class FileInputHelper implements Closeable {
private FileInputStream fileInputStream;
private BufferedReader fileBufferedReader;
public FileInputHelper(File file) throws IOException {
fileInputStream = new FileInputStream(file);
fileBufferedReader = new BufferedReader(new InputStreamReader(fileInputStream));
}
public byte readByte() throws IOException {
int cur = fileInputStream.read();
if (cur == -1)//ะตัะปะธ ะทะฐะบะพะฝัะธะปัั ัะฐะนะป
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
แแกแ, แแ แแแแแแ แ แแแแกแ:
import java.io.File;
import java.nio.charset.MalformedInputException;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.NoSuchFileException;
import java.nio.file.Paths;
import java.util.List;
import java.io.EOFException;
public class Main {
private static final byte ENCODING_TABLE_SIZE = 127;
public static void main(String[] args) throws IOException {
try {//ัะบะฐะทัะฒะฐะตะผ ะธะฝััััะบัะธั ั ะฟะพะผะพััั ะฐัะณัะผะตะฝัะพะฒ ะบะพะผะฐะฝะดะฝะพะน ัััะพะบะธ
if (args[0].equals("--compress") || args[0].equals("-c"))
compress(args[1]);
else if ((args[0].equals("--extract") || args[0].equals("-x"))
&& (args[2].equals("--table") || args[2].equals("-t"))) {
extract(args[1], args[3]);
}
else
throw new IllegalArgumentException();
} catch (ArrayIndexOutOfBoundsException | IllegalArgumentException e) {
System.out.println("ะะตะฒะตัะฝัะน ัะพัะผะฐั ะฒะฒะพะดะฐ ะฐัะณัะผะตะฝัะพะฒ ");
System.out.println("ะงะธัะฐะนัะต Readme.txt");
e.printStackTrace();
}
}
public static void compress(String stringPath) throws IOException {
List<String> stringList;
File inputFile = new File(stringPath);
String s = "";
File compressedFile, table;
try {
stringList = Files.readAllLines(Paths.get(inputFile.getAbsolutePath()));
} catch (NoSuchFileException e) {
System.out.println("ะะตะฒะตัะฝัะน ะฟััั, ะธะปะธ ัะฐะบะพะณะพ ัะฐะนะปะฐ ะฝะต ัััะตััะฒัะตั!");
return;
} catch (MalformedInputException e) {
System.out.println("ะขะตะบััะฐั ะบะพะดะธัะพะฒะบะฐ ัะฐะนะปะฐ ะฝะต ะฟะพะดะดะตัะถะธะฒะฐะตััั");
return;
}
for (String item : stringList) {
s += item;
s += 'n';
}
HuffmanOperator operator = new HuffmanOperator(new HuffmanTree(s));
compressedFile = new File(inputFile.getAbsolutePath() + ".cpr");
compressedFile.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(compressedFile)) {
fo.writeBytes(operator.getBytedMsg());
}
//create file with encoding table:
table = new File(inputFile.getAbsolutePath() + ".table.txt");
table.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(table)) {
fo.writeString(operator.getEncodingTable());
}
System.out.println("ะััั ะบ ัะถะฐัะพะผั ัะฐะนะปั: " + compressedFile.getAbsolutePath());
System.out.println("ะััั ะบ ะบะพะดะธัะพะฒะพัะฝะพะน ัะฐะฑะปะธัะต " + table.getAbsolutePath());
System.out.println("ะะตะท ัะฐะฑะปะธัั ัะฐะนะป ะฑัะดะตั ะฝะตะฒะพะทะผะพะถะฝะพ ะธะทะฒะปะตัั!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100;//ะธะดะตะฐะปะธะทะธัะพะฒะฐะฝะฝัะน ะบะพัััะธัะธะตะฝั
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100;//ะฝะฐััะพััะธะน ะบะพัััะธัะธะตะฝั
System.out.println("ะะดะตะฐะปะธะทะธัะพะฒะฐะฝะฝัะน ะบะพัััะธัะธะตะฝั ัะถะฐัะธั ัะฐะฒะตะฝ " + idealRatio);
System.out.println("ะะพัััะธัะธะตะฝั ัะถะฐัะธั ั ััะตัะพะผ ะบะพะดะธัะพะฒะพัะฝะพะน ัะฐะฑะปะธัั " + realRatio);
}
public static void extract(String filePath, String tablePath) throws FileNotFoundException, IOException {
HuffmanOperator operator = new HuffmanOperator();
File compressedFile = new File(filePath),
tableFile = new File(tablePath),
extractedFile = new File(filePath + ".xtr");
String compressed = "";
String[] encodingArray = new String[ENCODING_TABLE_SIZE];
//read compressed file
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!check here:
try (FileInputHelper fi = new FileInputHelper(compressedFile)) {
byte b;
while (true) {
b = fi.readByte();//method returns EOFException
compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0");
}
} catch (EOFException e) {
}
//--------------------
//read encoding table:
try (FileInputHelper fi = new FileInputHelper(tableFile)) {
fi.readLine();//skip first empty string
encodingArray[(byte)'n'] = fi.readLine();//read code for 'n'
while (true) {
String s = fi.readLine();
if (s == null)
throw new EOFException();
encodingArray[(byte)s.charAt(0)] = s.substring(1, s.length());
}
} catch (EOFException ignore) {}
extractedFile.createNewFile();
//extract:
try (FileOutputHelper fo = new FileOutputHelper(extractedFile)) {
fo.writeString(operator.extract(compressed, encodingArray));
}
System.out.println("ะััั ะบ ัะฐัะฟะฐะบะพะฒะฐะฝะฝะพะผั ัะฐะนะปั " + extractedFile.getAbsolutePath());
}
}
แแฅแแแ แแแแแ แแแแแฌแแแ แคแแแแแก แแแฌแแ แ readme.txt แแแกแขแ แฃแฅแชแแแแแ ๐
แแแกแแแแ
แแแแแ แกแฃแ แแก แแงแ แ แแกแ แแฅแแแช แแแแแแแ. แแฃ แ แแแแ แแแฅแแ แกแแแฅแแแแ แแแแแก, แแแแแ แแแแแก, แแแแแแแ, แ แแแแ แแแขแแแแแแชแแแก แแแฃแแฏแแแแกแแแแก แฉแแแก แแ แแแแแแแขแแแขแฃแ แแแแแ, แแแจแแ แแแแแกแฃแคแแแ แแแฌแแ แแ. แแฃ แ แแแ แแ แแแฎแกแแแ แแแฌแแ แ. แกแแแแแแแแแแ แแแแแกแแแแแ แแฅแแแแแแ แแแแแแขแแ แแแจแ!
PS
แแแแฎ, แแแแฎ, แแ แแกแแ แแฅ แแแ , แ แแแแแ แแแแคแแชแแแแขแ แแ แแแแแแแฌแงแแ. แกแขแ แแฅแแแแกแแแแก s1, แแแแแ แแแแก แชแฎแ แแแ แแฌแแแแก 48 แแแแขแก - แแแแ แแ แแฆแแแแขแแแ แแแแแแแแ แแแ แคแแแแก แแ แแ แแแแแแฌแงแแก แแแแแขแแแแแ แแฃแแแแ (แแแแแขแแแฃแแ แแฃแแแแแก แ แแแแแแแแ แแ แแก 7) => แจแแแฃแแจแแแก แแแแคแแชแแแแขแ แแฅแแแแ แแ แแแ แแแแแแแ: 176 /(65 + 48*8 + 7) = 0.38. แแฃ แแฅแแแแช แจแแแแฉแแแแ แแก, แแแจแแ แฃแแ แแแแ แกแแฎแแแ แแ แฎแแ แ แแแกแ แฃแแแแฃแแ. แแแแฎ, แแก แแแแฎแแ แชแแแแแแ แฃแแแแฃแ แแกแแ แแ แแแคแแฅแขแฃแ แ แแฅแแแแ แแชแแ แ แแแแแก แคแแแแแแแกแแแแก. แแแแ แแ แ แ แฎแแแแ แแแ แคแแแแแแแแ? แคแแแแแก แแแแ แแแแ แแ แแฆแแแแขแแแ แแแแแ แแแแก แชแฎแ แแแแก แแแแแก. แแก แแ แแก แกแแแแช แแแแแ แแแแ แแฃแจแแแแก แแกแ, แ แแแแ แช แฃแแแ! แแแแแแแแแ, แแแแกแแแแก
แฌแงแแ แ: www.habr.com