แแถแแป
แแ แแแแปแแขแแแแแแแแ แแแแปแแแนแแแทแแถแแขแแแธแแแแฝแแแแแแแแถแ Huffman แแแแแแธ แแแแผแ แแถแแแแแแทแแธแแแแแแถแแแแปแแแถแแแแแ แถแแแแทแแแแแแแ
แแถแแแแแแแแพแแแนแแแแแแแแแแแแแถแแแถแแแแแ แแแโแแถแโแแฝแ
โแแ
โแ แพแแ
แแถแแแแแปแแแแแ แถแแแแทแ แแฝแ
แแ แแแแปแแฏแแแถแแขแแแแแแแแแแแถ แแฝแขแแแแแแฝแแแแแผแแแถแแขแแทแแแผแแแแ 8 แแแธแ (แแถแแขแแทแแแผแ ASCII) แฌ 16 (แแถแแขแแทแแแผแแแผแแธแแผแ) แ แแแแแถแแ แแพแแแนแแแทแ แถแแแถแแถแแขแแทแแแผแ ASCII แ แงแแถแ แแแ แแ string s1 = "SUSIE SAYS IT IS EASYn" แ แแแปแแแ แแถแแแฝแขแแแแแ แแแฝแ 22 แแ แแแแปแแแแแแถแแ แแฝแแแถแแแแแแแแถ แแทแแแฝแขแแแแแแแแแถแแแแแแธ - 'n' แ แฏแแแถแแแแแแถแแแแแแถแแแแแแแนแแแถแแแแแแแ 22 * โโ8 = 176 แแแธแแ แแแแฝแแแพแแกแพแแแแแถแแแ แแพแแถแแแ แแแปแแแแแแแแปแแแถแแแแแพ 8 แแแธแ แแพแแแแธแขแแทแแแผแแแฝแขแแแแ 1? แแพแแแทแแแแแพแแฝแขแแแแ ASCII แแถแแแขแแแแแ แแแแแธแแถแแฝแแแแแถแแแแแแ แแถแแนแแแแ แแแปแแแแถแแแแแปแแแถแแแแแแแขแแแแแแนแแแถแแแแแแปแ - S - แแแแแผแแแแแธแแแแปแแแแแขแถแ แแแแพแแ แแถแ แ แพแแแแแแถแแแขแแแแแแแแแแแแแแปแ - T (แฌ U แฌ 'n') - แแแแแแฑแแแแแแแผแแแทแแแแแถแแแแถแแ แแแแแบแแถแแแแฝแแแแแแแแถแ Huffmanแ แขแแแแแแแผแแแแแแแแแแแแแพแแแถแแขแแทแแแผแแแแขแแแแปแ แแแแฏแแแถแแแนแแแถแแแแแแแแขแแแแแแแถแ แแถแแถแแฟแแแแแแแถแแแแแแแฝแขแแแแแแแแแแแแแถแแนแแแถแแแแแแแแแผแแแปแแแแแแถ - แแแแแบแแถแแผแแแแแถแแแแแแแฝแแแแแแแแถแแ
ะพะดะธัะพะฒะฐะฝะธะต
แ แแแปแขแแแธแแทแแแแแแแฑแแแแฝแขแแแแ '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
แแแแปแแแถแแแแแแแแผแแแแแฝแขแแแแแแธแแฝแแแแแแแแแแแถแ แแถแแนแแแทแแแพแแกแพแแแ
แแแแปแแฏแแแถแแแแแแถแแแแแ แถแแแแ!
แแแแฝแแแพแแกแพแแ แแพแขแแแแแแแธแแแแแแแแแแแแแพแแแผแแแแแแแแแแพแแแถแแถแแแผแแแแแแแแแแถ? แแแแแนแแแแแผแแแถแแแทแแถแแแแถแแผแ
แแถแแแแแแแ
แแถแแแถแแแแแแพแแแพ Huffman
แแแแแบแแถแแแแแแแแแแแพแแแพแแแแแแแแแแแแแแแแแแแแธแแแแแฝแแแแแแแแแแ แแปแแแถแแแแ แขแแแแแนแแแทแแแแแผแแแถแแแถแแแแแแแแ แแแแ แผแ แแทแแแปแแแทแแธแแถแแแแแแแ แแธแแแแแแ แแแแแบแแถแแ แแถแแแแแแแแแแพแแแพแแ แแแแปแ java:
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 nodes ( Node objects ) แ แแแแถแแแแธแแฝแแแแถแแแถแแแทแแแแแแแแธแแ แแทแแทแแแแแแแแถ แแทแแแแแแแแ
- แแแแแพแ Tree object (BinaryTree) แแแแแถแแ Node แแธแแฝแแแ แแแแถแแแแแแถแแแถแซแแแแแพแแแพแ
- แแแแ แผแแแพแแแพแแถแแแแแแแ แแแแปแแแฝแแขแถแแทแแถแแ แแแแแแแแแถแแแแแแถแ แขแถแแทแแถแแแถแแแแแแแแแแ แแผแ แแแแแแ แแแแแแแแแ แแ แแแแแถแแแแแแถแแแแแแแแแแถแแแแแปแแแแแแแแแแผแแแถแแแแแพแแแพแแ
แแแแแถแแโแแ แขแแแโแแแแผแโแแแแพโแแผแ โแแถแโแแแแแแ
- แแถแแแแแแแแถแแแธแแแธแแฝแแขแถแแทแแถแ แ แพแแแแแพแฑแแแแฝแแแถแแถแแผแแแแแถแแแแแแธ (แแแแถแแแแแแแถแแแแแแพแแแแแธแแแแแแแถแแขแแแแ)แ แแแแแแแแแแแแแถแแแแแแธแแบแแแแพแแนแแแแแผแแแแแแแแแแแแแแพแแแพแแแแแแผแแแถแแแแธแแ
- แแแแแถแแแแแแถแแแแแ แแแแแพแแแแแแถแแแแแแถแแซแแแแแแ แแแแถแแแแแแ แแแแ แผแแแแแแถแแแแแแแแกแแแแ แแฝแแขแถแแทแแถแแ (แ แถแแแแถแแแแธแแพแแแพแแถแแแแแแแแแแแแธ แแถแแแแแแถแแนแแ แผแแแ แแแแแแแแแแธแแ แแแแปแแแฝแ)
- แแแแแแแ แถแแแธ 1 แแทแแแธ 2 แแ แผแแแแแแพแแแพแแฝแแแ แแแแแแแปแแแฝแ - แแพแแแพ Huffman
แแทแ แถแแแถแแแแฝแแแแแแแแถแแแแแแ แแพแแแแแถแแ s1:
แแ
แแธแแแแแทแแทแแแแแแแแถ "lf" (linefeed) แแแแ แถแแแธแแแแแถแแแแแแธ "sp" (space) แแบแแถแแแ แ
แแถแโแขแแแธโแแแแแถแแ?
แแพแแแแฝแแแถแแแพแแแพ Huffman แ แแแแแแแแ แ แพแแขแแแธแแแแแแแผแแแแแพแแถแแฝแแแถ? แแฝแแแแแนแแแทแแแแแถแแแแฅแแแทแแแแแแแแ แ แพแแแแแแถแแแแ แขแแแแแแแผแแแถแแแถแแแแแผแแแแแขแถแ แแแแพแแถแแแถแแแขแแแแธแซแแแ แแแแนแแแแแแแพแแแพแ แแพแแแแแแแแแแถแแแแแแถแแแแ 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 แแ! แแแปแแแแแแแแแบแแถ utopia แ แแแถแแถแแแแแแแแแแแแแแแถแแทแแแแแผแแแถแแแแฝแแแแ แ แแแปแขแแแธ? แแแแแนแแแแแผแแแถแแแทแแถแแแแถแแแแแทแ
แแแแแแแแ
แแถแแแทแแผแ
แแถแแถแแแแแแพแแแถแแ, แแแแ แแแแถแขแแแธแแแแแถแแแแแแแแปแแแแแแ แแแแแบแแถแแแทแแผแแ แแแแปแโแแทแโแแถ แขแแแโแแถโแ แแแพแโแแถแโแแถแโแแถโแแถโแแทแโแขแถแ โแแ โแแฝแ โแแโแแแแปแโแแถแโแแแแแพแโแฏแแแถแโแแแแ แถแแโแแแโแแทแโแแถแโแแแแแปแโแแธโแแแแโแแแโแแถโแแแแผแโแแถแโแขแแทแแแผแโแแแโแแ แแพแโแแนแโแแทแโแขแถแ โแแทแแผแโแแถโแแถแโแแ! แแถแ แแถแ แแถแแทแแถแแแแแแถแแแแแแปแแแแแปแแแถแแแแแแนแแขแแแธแแฟแแแแ แแแปแแแแแแแแปแแแแแผแแแแแแแแพแแฏแแแถแแขแแแแแ table.txt แแถแแฝแแแนแแแถแแถแแแแแ แถแแแ
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
แแถแแปแแถแแถแแแแแปแแแแแแแ 'แแฝแขแแแแ' "แแผแแแฝแขแแแแ" แ แ แแแปแขแแแธแแถแแแถ 01110 แแแแถแแแทแแทแแแแแแแแถ? แแถแแแทแแแ แแถแแบแแถแแฝแแแนแแแทแแทแแแแแแแแถแแฝแ แแแแถแแแแแแถแงแแแแแ java แแแแแแแปแแแแแพแแ แแแแ แแแฏแแแถแแแฝแ แแฝแขแแแแแแแแแถแแแแแแธ - 'n' - แแแแผแแแถแแแแแแแแแแ แแถแแแแแถแแแแแแธ (แแทแแแถแแถแแแแถแแแแ แแแแแแแแถแแแถแแ)แ แแผแ แแแแ แแแแแถแแแแแแแถแแแพแแบแแถแแฝแขแแแแแแแแแถแแแแแแแผแ 01110แ แแแแแถแแแแแแแผแ 00 แแฝแขแแแแแแบแแถแ แแแแแแแ แแพแแแแแแถแแแ แแแแปแแแแแผแแแแแทแแถแแแแแถแแแแถ แแทแแธแแถแแแแแแแแแถแแแแแแถแแปแแแถแแถแแแแแขแถแ แขแแขแถแแแถแแทแแแแ แแแปแแแแแแปแแแแแแถแแแแแแปแแแถแแแแแแแแพแแ แแแปแแแแแแถแแถแแแแแฝแแแแ แแทแแขแแปแแแแแ แแแแปแแแนแแแธแแแถแแแแแปแแแถแแแแแถแแแแถแแแแแถแแแแแแขแแแแแ แแแแปแแแแทแแแแแแขแแแธแแถแแแแแแพแแแแแแทแแแแแถแแ
แแถแแฝแแแนแแแถแแถแแแแแแถแแถแแแแแฝแแแถแแแแแแปแแแถแแแทแแผแแ แ แผแแแพแแ แถแแแถแแพแ แแแถแแแแถแแแแแพแแแแแผแแแถแแแแแถแแแ แแแแแแแแพแแแถแแขแแทแแแผแแ
แแแแถแแแแแแผแแแแแผแแแแแถแแปแแแแแแแแแฝแแแแแแแแแ
แแแแแบแแถแแแแแแแแแแแถแแพแแแฝแแถแแธแแแแแแแแแแฝแแ แแพแแขแถแแแแแแทแ แแแแแแแถแแแแแถแแแแแแแ แ แพแแแแถแแแถแแแแแแแแแแแแ d แแแแแถแแแแธแแขแถแแแแแผแแแแแถแแนแแแถแแขแแทแแแผแแแแแแแแผแแแแแถแแนแแแฝแขแแแแแแฝแขแแแแ แแพแแแนแแแแแถแแแถแแฝแขแแแแแแฝแขแแแแ (แ แพแแแถแแแแแฝแขแแแแแแแปแแแแแ!) แแแแผแแแถแแขแแทแแแผแแ แแแแแถแแแแพแแแแแแแแฝแขแแแแแแ แแแแแขแแแแแแทแแผแ (แแแแแขแแแแแแแแแถแแแถแแแแแแถแแแทแแผแ) แแแแแแแแแแขแแแแ d แกแพแแแทแแ แพแแขแถแแฏแแแถแแแแแแถแแขแแทแแแผแแแแแแแแแแแ
ะ ะตะฐะปะธะทะฐัะธั
แแถแแแแแแแแแแแแแผแแแแแแถแแแแแแแแแแแแผแแแแแแแแแปแแแแแแถแแแแแแแแแแแแถแแ แแแแ แ แแถแแถ Compressorแ
แแถแโแกแพแแแทแแ แแแแผแแแพแแแแแแ Node classแ
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;//ะฒะพะทะฒัะฐัะฐะตะผ ัะดะฐะปะตะฝะฝัะน ัะปะตะผะตะฝั(ัะปะตะผะตะฝั ั ะฝะฐะธะผะตะฝััะตะน ัะฐััะพัะพะน)
}
}
แแแแถแแแแแแแแแแพแแแแแแถแ Huffmanแ
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