āĻĒā§āĻ°āĻŦā§āĻļ
āĻāĻ āĻ¨āĻŋāĻŦāĻ¨ā§āĻ§ā§, āĻāĻŽāĻŋ āĻ¸ā§āĻĒāĻ°āĻŋāĻāĻŋāĻ¤ āĻšāĻžāĻĢāĻŽā§āĻ¯āĻžāĻ¨ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ, āĻ¸ā§āĻāĻ¸āĻžāĻĨā§ āĻĄā§āĻāĻž āĻ¸āĻāĻā§āĻāĻ¨ā§ āĻāĻ° āĻĒā§āĻ°āĻ¯āĻŧā§āĻ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻĨāĻž āĻŦāĻ˛āĻŦāĨ¤
āĻĢāĻ˛āĻ¸ā§āĻŦāĻ°ā§āĻĒ, āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ¸āĻžāĻ§āĻžāĻ°āĻŖ āĻāĻ°ā§āĻāĻžāĻāĻāĻžāĻ° āĻ˛āĻŋāĻāĻŦāĨ¤ āĻāĻ āĻāĻ¤āĻŋāĻŽāĻ§ā§āĻ¯ā§ āĻšāĻ¯āĻŧā§āĻā§
āĻāĻāĻā§ āĻĒā§āĻ°āĻ¤āĻŋāĻĢāĻ˛āĻ¨
āĻāĻāĻāĻŋ āĻ¸āĻžāĻ§āĻžāĻ°āĻŖ āĻĒāĻžāĻ ā§āĻ¯ āĻĢāĻžāĻāĻ˛ā§, āĻāĻāĻāĻŋ āĻ āĻā§āĻˇāĻ° 8 āĻŦāĻŋāĻ (ASCII āĻāĻ¨āĻā§āĻĄāĻŋāĻ) āĻŦāĻž 16 (āĻāĻāĻ¨āĻŋāĻā§āĻĄ āĻāĻ¨āĻā§āĻĄāĻŋāĻ) āĻĻāĻŋāĻ¯āĻŧā§ āĻāĻ¨āĻā§āĻĄ āĻāĻ°āĻž āĻšāĻ¯āĻŧāĨ¤ āĻĒāĻ°āĻŦāĻ°ā§āĻ¤ā§, āĻāĻŽāĻ°āĻž ASCII āĻāĻ¨āĻā§āĻĄāĻŋāĻ āĻŦāĻŋāĻŦā§āĻāĻ¨āĻž āĻāĻ°āĻŦāĨ¤ āĻāĻĻāĻžāĻšāĻ°āĻŖ āĻ¸ā§āĻŦāĻ°ā§āĻĒ, āĻ¸ā§āĻā§āĻ°āĻŋāĻ s1 = "SUSIE āĻŦāĻ˛ā§ 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;
}
...
}
āĻāĻāĻŋ āĻ¸āĻŽā§āĻĒā§āĻ°ā§āĻŖ āĻā§āĻĄ āĻ¨āĻ¯āĻŧ, āĻ¸āĻŽā§āĻĒā§āĻ°ā§āĻŖ āĻā§āĻĄāĻāĻŋ āĻ¨ā§āĻā§ āĻĨāĻžāĻāĻŦā§āĨ¤
āĻāĻāĻžāĻ¨ā§ āĻāĻāĻāĻŋ āĻāĻžāĻ āĻ¨āĻŋāĻ°ā§āĻŽāĻžāĻŖā§āĻ° āĻāĻ¨ā§āĻ¯ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ:
- āĻŦāĻžāĻ°ā§āĻ¤āĻž āĻĨā§āĻā§ āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻ āĻā§āĻˇāĻ°ā§āĻ° āĻāĻ¨ā§āĻ¯ āĻāĻāĻāĻŋ āĻ¨ā§āĻĄ āĻ āĻŦāĻā§āĻā§āĻ āĻ¤ā§āĻ°āĻŋ āĻāĻ°ā§āĻ¨ (āĻ˛āĻžāĻāĻ¨ s1)āĨ¤ āĻāĻŽāĻžāĻĻā§āĻ° āĻā§āĻˇā§āĻ¤ā§āĻ°ā§, 9āĻāĻŋ āĻ¨ā§āĻĄ (āĻ¨ā§āĻĄ āĻ āĻŦāĻā§āĻā§āĻ) āĻĨāĻžāĻāĻŦā§āĨ¤ āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻ¨ā§āĻĄ āĻĻā§āĻāĻŋ āĻĄā§āĻāĻž āĻā§āĻˇā§āĻ¤ā§āĻ° āĻ¨āĻŋāĻ¯āĻŧā§ āĻāĻ āĻŋāĻ¤: āĻĒā§āĻ°āĻ¤ā§āĻ āĻāĻŦāĻ āĻĢā§āĻ°āĻŋāĻā§āĻ¯āĻŧā§āĻ¨ā§āĻ¸āĻŋ
- āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻ¨ā§āĻĄ āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻ¯ āĻāĻāĻāĻŋ āĻā§āĻ°āĻŋ āĻ āĻŦāĻā§āĻā§āĻ (āĻŦāĻžāĻāĻ¨āĻžāĻ°ā§ āĻā§āĻ°āĻŋ) āĻ¤ā§āĻ°āĻŋ āĻāĻ°ā§āĻ¨āĨ¤ āĻ¨ā§āĻĄāĻāĻŋ āĻāĻžāĻā§āĻ° āĻŽā§āĻ˛ā§ āĻĒāĻ°āĻŋāĻŖāĻ¤ āĻšāĻ¯āĻŧāĨ¤
- āĻāĻ āĻāĻžāĻāĻā§āĻ˛āĻŋāĻā§ āĻ āĻā§āĻ°āĻžāĻ§āĻŋāĻāĻžāĻ° āĻ¸āĻžāĻ°āĻŋāĻ¤ā§ āĻĸā§āĻāĻžāĻ¨āĨ¤ āĻĢā§āĻ°āĻŋāĻā§āĻ¯āĻŧā§āĻ¨ā§āĻ¸āĻŋ āĻ¯āĻ¤ āĻāĻŽ, āĻ āĻā§āĻ°āĻžāĻ§āĻŋāĻāĻžāĻ° āĻ¤āĻ¤ āĻŦā§āĻļāĻŋāĨ¤ āĻ¸ā§āĻ¤āĻ°āĻžāĻ, āĻ¨āĻŋāĻˇā§āĻāĻžāĻļāĻ¨ āĻāĻ°āĻžāĻ° āĻ¸āĻŽāĻ¯āĻŧ, āĻ¸āĻ°ā§āĻŦāĻ¨āĻŋāĻŽā§āĻ¨ āĻĢā§āĻ°āĻŋāĻā§āĻ¯āĻŧā§āĻ¨ā§āĻ¸āĻŋ āĻ¸āĻš āĻāĻžāĻāĻāĻŋ āĻ¸āĻ°ā§āĻŦāĻĻāĻž āĻ¨āĻŋāĻ°ā§āĻŦāĻžāĻāĻ¨ āĻāĻ°āĻž āĻšāĻ¯āĻŧāĨ¤
āĻāĻ° āĻĒāĻ°ā§, āĻāĻĒāĻ¨āĻžāĻā§ āĻāĻā§āĻ°āĻžāĻāĻžāĻ°ā§ āĻ¨āĻŋāĻŽā§āĻ¨āĻ˛āĻŋāĻāĻŋāĻ¤āĻā§āĻ˛āĻŋ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§:
- āĻ āĻā§āĻ°āĻžāĻ§āĻŋāĻāĻžāĻ° āĻ¸āĻžāĻ°āĻŋ āĻĨā§āĻā§ āĻĻā§āĻāĻŋ āĻāĻžāĻ āĻĒā§āĻ¨āĻ°ā§āĻĻā§āĻ§āĻžāĻ° āĻāĻ°ā§āĻ¨ āĻāĻŦāĻ āĻ¤āĻžāĻĻā§āĻ° āĻāĻāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻ¨ā§āĻĄā§āĻ° āĻ¸āĻ¨ā§āĻ¤āĻžāĻ¨ āĻāĻ°ā§āĻ¨ (āĻāĻāĻāĻŋ āĻ āĻā§āĻˇāĻ° āĻāĻžāĻĄāĻŧāĻžāĻ āĻāĻāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻ¤ā§āĻ°āĻŋ āĻ¨ā§āĻĄ)āĨ¤ āĻ¨āĻ¤ā§āĻ¨ āĻ¨ā§āĻĄā§āĻ° āĻĢā§āĻ°āĻŋāĻā§āĻ¯āĻŧā§āĻ¨ā§āĻ¸āĻŋ āĻĻā§āĻāĻŋ āĻŦāĻāĻļāĻ§āĻ° āĻāĻžāĻā§āĻ° āĻĢā§āĻ°āĻŋāĻā§āĻ¯āĻŧā§āĻ¨ā§āĻ¸āĻŋāĻ° āĻ¯ā§āĻāĻĢāĻ˛ā§āĻ° āĻ¸āĻŽāĻžāĻ¨āĨ¤
- āĻāĻ āĻ¨ā§āĻĄā§āĻ° āĻāĻ¨ā§āĻ¯, āĻāĻ āĻ¨ā§āĻĄā§ āĻŽā§āĻ˛āĻ¯ā§āĻā§āĻ¤ āĻāĻāĻāĻŋ āĻāĻžāĻ āĻ¤ā§āĻ°āĻŋ āĻāĻ°ā§āĻ¨āĨ¤ āĻāĻ āĻāĻžāĻāĻāĻŋāĻā§ āĻāĻŦāĻžāĻ° āĻ āĻā§āĻ°āĻžāĻ§āĻŋāĻāĻžāĻ° āĻ¸āĻžāĻ°āĻŋāĻ¤ā§ āĻĸā§āĻāĻžāĻ¨āĨ¤ (āĻ¯ā§āĻšā§āĻ¤ā§ āĻāĻžāĻāĻāĻŋāĻ° āĻāĻāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻĢā§āĻ°āĻŋāĻā§āĻ¯āĻŧā§āĻ¨ā§āĻ¸āĻŋ āĻ°āĻ¯āĻŧā§āĻā§, āĻāĻāĻŋ āĻ¸āĻŽā§āĻāĻŦāĻ¤ āĻ¸āĻžāĻ°āĻŋāĻ¤ā§ āĻāĻāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻāĻžāĻ¯āĻŧāĻāĻžāĻ¯āĻŧ āĻĒā§āĻ°āĻŦā§āĻļ āĻāĻ°āĻŦā§)
- āĻ§āĻžāĻĒ 1 āĻāĻŦāĻ 2 āĻāĻžāĻ˛āĻŋāĻ¯āĻŧā§ āĻ¯āĻžāĻ¨ āĻ¯āĻ¤āĻā§āĻˇāĻŖ āĻ¨āĻž āĻāĻāĻāĻŋ āĻāĻžāĻ āĻ¸āĻžāĻ°āĻŋāĻ¤ā§ āĻŦāĻžāĻāĻŋ āĻĨāĻžāĻā§ - āĻšāĻžāĻĢāĻŽā§āĻ¯āĻžāĻ¨ āĻāĻžāĻ
āĻ˛āĻžāĻāĻ¨ s1-āĻ āĻāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻāĻŋ āĻŦāĻŋāĻŦā§āĻāĻ¨āĻž āĻāĻ°ā§āĻ¨:
āĻāĻāĻžāĻ¨ā§ "lf" (āĻ˛āĻžāĻāĻ¨āĻĢāĻŋāĻĄ) āĻāĻŋāĻšā§āĻ¨āĻāĻŋ āĻāĻāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻ˛āĻžāĻāĻ¨āĻā§ āĻŦā§āĻāĻžāĻ¯āĻŧ, "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 āĻāĻŋāĻšā§āĻ¨ āĻāĻžāĻĄāĻŧāĻž āĻā§āĻ¨? āĻĒā§āĻ°āĻā§āĻ¤āĻĒāĻā§āĻˇā§, āĻāĻāĻŋ āĻāĻāĻāĻŋ āĻĒā§āĻ°āĻ¤ā§āĻā§āĻ° āĻ¸āĻžāĻĨā§, āĻļā§āĻ§ā§āĻŽāĻžāĻ¤ā§āĻ° āĻāĻžāĻāĻž āĻ¸āĻ°āĻā§āĻāĻžāĻŽāĻā§āĻ˛āĻŋ āĻ¯āĻž āĻāĻŽāĻŋ āĻāĻāĻāĻŋ āĻĢāĻžāĻāĻ˛ā§ āĻāĻāĻāĻĒā§āĻ āĻāĻ°āĻžāĻ° āĻ¸āĻŽāĻ¯āĻŧ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°āĻŋ, āĻ¨āĻŋāĻāĻ˛āĻžāĻāĻ¨ āĻ āĻā§āĻˇāĻ° - 'n' - āĻāĻāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻ˛āĻžāĻāĻ¨ā§ āĻ°ā§āĻĒāĻžāĻ¨ā§āĻ¤āĻ°āĻŋāĻ¤ āĻšāĻ¯āĻŧ (āĻāĻāĻŋ āĻ¯āĻ¤āĻ āĻŦā§āĻāĻž āĻ˛āĻžāĻā§āĻ āĻ¨āĻž āĻā§āĻ¨)āĨ¤ āĻ āĻ¤āĻāĻŦ, āĻāĻĒāĻ°ā§āĻ° āĻāĻžāĻ˛āĻŋ āĻ˛āĻžāĻāĻ¨āĻāĻŋ āĻā§āĻĄ 01110-āĻāĻ° āĻāĻ¨ā§āĻ¯ āĻ āĻā§āĻˇāĻ°āĨ¤ āĻā§āĻĄ 00-āĻāĻ° āĻāĻ¨ā§āĻ¯, āĻ āĻā§āĻˇāĻ°āĻāĻŋ āĻ˛āĻžāĻāĻ¨ā§āĻ° āĻļā§āĻ°ā§āĻ¤ā§ āĻāĻāĻāĻŋ āĻ¸ā§āĻĒā§āĻ¸āĨ¤ āĻāĻŽāĻžāĻā§ āĻāĻāĻ¨āĻ āĻŦāĻ˛āĻ¤ā§ āĻšāĻŦā§ āĻ¯ā§ āĻā§āĻŦāĻŋāĻ˛ āĻ¸āĻāĻ°āĻā§āĻˇāĻŖā§āĻ° āĻāĻ āĻĒāĻĻā§āĻ§āĻ¤āĻŋāĻāĻŋ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻžāĻ¨ āĻ¸āĻšāĻā§āĻ° āĻāĻ¨ā§āĻ¯ āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻ āĻ¯ā§āĻā§āĻ¤āĻŋāĻ āĻŦāĻ˛ā§ āĻĻāĻžāĻŦāĻŋ āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°ā§āĨ¤ āĻ¤āĻŦā§ āĻāĻāĻŋ āĻŦā§āĻāĻž āĻāĻŦāĻ āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨ āĻāĻ°āĻž āĻ¸āĻšāĻāĨ¤ āĻāĻŽāĻŋ āĻ āĻĒā§āĻāĻŋāĻŽāĻžāĻāĻā§āĻļāĻžāĻ¨ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻŽāĻ¨ā§āĻ¤āĻŦā§āĻ¯ āĻāĻĒāĻ¨āĻžāĻ° āĻ¸ā§āĻĒāĻžāĻ°āĻŋāĻļ āĻļā§āĻ¨āĻ¤ā§ āĻā§āĻļāĻŋ āĻšāĻŦā§.
āĻāĻ āĻā§āĻŦāĻŋāĻ˛ā§āĻ° āĻ¸āĻžāĻšāĻžāĻ¯ā§āĻ¯ā§, āĻāĻāĻŋ āĻĄāĻŋāĻā§āĻĄ āĻāĻ°āĻž āĻā§āĻŦ āĻ¸āĻšāĻāĨ¤ āĻāĻ¸ā§āĻ¨ āĻŽāĻ¨ā§ āĻ°āĻžāĻāĻŦā§āĻ¨ āĻāĻ¨āĻā§āĻĄāĻŋāĻ āĻ¤ā§āĻ°āĻŋ āĻāĻ°āĻžāĻ° āĻ¸āĻŽāĻ¯āĻŧ āĻāĻŽāĻ°āĻž āĻā§āĻ¨ āĻ¨āĻŋāĻ¯āĻŧāĻŽ āĻĻā§āĻŦāĻžāĻ°āĻž āĻĒāĻ°āĻŋāĻāĻžāĻ˛āĻŋāĻ¤ āĻšāĻ¯āĻŧā§āĻāĻŋāĻ˛āĻžāĻŽ:
āĻā§āĻ¨ā§ āĻā§āĻĄ āĻ āĻ¨ā§āĻ¯ā§āĻ° āĻāĻĒāĻ¸āĻ°ā§āĻ āĻšāĻ¤ā§ āĻšāĻŦā§ āĻ¨āĻž
āĻāĻāĻžāĻ¨ā§ āĻāĻāĻŋ āĻāĻāĻāĻŋ āĻ¸ā§āĻŦāĻŋāĻ§āĻžāĻāĻ¨āĻ āĻā§āĻŽāĻŋāĻāĻž āĻĒāĻžāĻ˛āĻ¨ āĻāĻ°ā§āĨ¤ āĻāĻŽāĻ°āĻž āĻĒāĻ°ā§āĻ¯āĻžāĻ¯āĻŧāĻā§āĻ°āĻŽā§ āĻŦāĻŋāĻ āĻŦāĻŋāĻ āĻĒāĻĄāĻŧāĻŋ, āĻāĻŦāĻ āĻ¯āĻ¤ āĻ¤āĻžāĻĄāĻŧāĻžāĻ¤āĻžāĻĄāĻŧāĻŋ āĻĢāĻ˛āĻžāĻĢāĻ˛ āĻ¸ā§āĻā§āĻ°āĻŋāĻ d, āĻ°āĻŋāĻĄ āĻŦāĻŋāĻ āĻ¸āĻŽāĻ¨ā§āĻŦāĻŋāĻ¤, āĻ āĻā§āĻˇāĻ° āĻ āĻā§āĻˇāĻ°ā§āĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻāĻŋāĻ¤ āĻāĻ¨āĻā§āĻĄāĻŋāĻāĻ¯āĻŧā§āĻ° āĻ¸āĻžāĻĨā§ āĻŽā§āĻ˛ā§, āĻāĻŽāĻ°āĻž āĻ āĻŦāĻŋāĻ˛āĻŽā§āĻŦā§ āĻāĻžāĻ¨āĻŋ āĻ¯ā§ āĻ āĻā§āĻˇāĻ° āĻ āĻā§āĻˇāĻ°āĻāĻŋ (āĻāĻŦāĻ āĻļā§āĻ§ā§āĻŽāĻžāĻ¤ā§āĻ° āĻāĻāĻŋ!) āĻāĻ¨āĻā§āĻĄ āĻāĻ°āĻž āĻšāĻ¯āĻŧā§āĻāĻŋāĻ˛āĨ¤ āĻāĻ° āĻĒāĻ°ā§, āĻāĻŽāĻ°āĻž āĻĄāĻŋāĻā§āĻĄ āĻ¸ā§āĻā§āĻ°āĻŋāĻ (āĻĄāĻŋāĻā§āĻĄ āĻāĻ°āĻž āĻŦāĻžāĻ°ā§āĻ¤āĻž āĻ§āĻžāĻ°āĻŖāĻāĻžāĻ°ā§ āĻ¸ā§āĻā§āĻ°āĻŋāĻ) āĻ āĻ āĻā§āĻˇāĻ° āĻ˛āĻŋāĻāĻŋ, d āĻ¸ā§āĻā§āĻ°āĻŋāĻ āĻĒā§āĻ¨āĻ°āĻžāĻ¯āĻŧ āĻ¸ā§āĻ āĻāĻ°āĻŋ āĻāĻŦāĻ āĻāĻ¨āĻā§āĻĄ āĻāĻ°āĻž āĻĢāĻžāĻāĻ˛āĻāĻŋ āĻāĻ°āĻ āĻĒāĻĄāĻŧāĻŋāĨ¤
āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨
āĻāĻāĻŋ āĻāĻāĻāĻŋ āĻāĻ°ā§āĻāĻžāĻāĻāĻžāĻ° āĻ˛āĻŋāĻā§ āĻāĻŽāĻžāĻ° āĻā§āĻĄ āĻ āĻĒāĻŽāĻžāĻ¨ āĻāĻ°āĻžāĻ° āĻ¸āĻŽāĻ¯āĻŧ. āĻāĻ¸ā§āĻ¨ āĻāĻā§ āĻāĻŽā§āĻĒā§āĻ°ā§āĻ¸āĻžāĻ° āĻŦāĻ˛āĻŋāĨ¤
āĻ¨āĻ¤ā§āĻ¨ āĻāĻ°ā§ āĻļā§āĻ°ā§ āĻāĻ°. āĻĒā§āĻ°āĻĨāĻŽāĻ¤, āĻāĻŽāĻ°āĻž āĻ¨ā§āĻĄ āĻā§āĻ˛āĻžāĻ¸ āĻ˛āĻŋāĻāĻŋ:
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 āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļāĻžāĻŦāĻ˛ā§ āĻĻāĻŋāĻ¯āĻŧā§ āĻĢāĻžāĻāĻ˛āĻāĻŋ āĻ˛āĻŋāĻāĻ¤ā§ āĻšāĻŦā§ đ
āĻāĻĒāĻ¸āĻāĻšāĻžāĻ°
āĻāĻŽāĻŋ āĻ āĻ¨ā§āĻŽāĻžāĻ¨ āĻ¯ā§ āĻāĻŽāĻŋ āĻ¸āĻŦ āĻŦāĻ˛āĻ¤ā§ āĻā§āĻ¯āĻŧā§āĻāĻŋāĻ˛ā§āĻ¨. āĻā§āĻĄ, āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ, āĻ¸āĻžāĻ§āĻžāĻ°āĻŖāĻāĻžāĻŦā§, āĻ¯ā§ āĻā§āĻ¨āĻ āĻ āĻĒā§āĻāĻŋāĻŽāĻžāĻāĻā§āĻļāĻžāĻ¨ā§āĻ° āĻāĻ¨ā§āĻ¨āĻ¤āĻŋāĻ¤ā§ āĻāĻŽāĻžāĻ° āĻ āĻ¯ā§āĻā§āĻ¯āĻ¤āĻž āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻĒāĻ¨āĻžāĻ° āĻ¯āĻĻāĻŋ āĻāĻŋāĻā§ āĻŦāĻ˛āĻžāĻ° āĻĨāĻžāĻā§ āĻ¤āĻŦā§ āĻ¨āĻŋāĻ°ā§āĻĻā§āĻŦāĻŋāĻ§āĻžāĻ¯āĻŧ āĻ˛āĻŋāĻā§āĻ¨āĨ¤ āĻ¯āĻĻāĻŋ āĻāĻŽāĻŋ āĻāĻŋāĻā§ āĻŦā§āĻ¯āĻžāĻā§āĻ¯āĻž āĻ¨āĻž āĻāĻ°ā§ āĻĨāĻžāĻāĻŋ āĻ¤āĻŦā§ āĻĻāĻ¯āĻŧāĻž āĻāĻ°ā§ āĻ˛āĻŋāĻā§āĻ¨āĨ¤ āĻāĻŽāĻŋ āĻŽāĻ¨ā§āĻ¤āĻŦā§āĻ¯ā§ āĻāĻĒāĻ¨āĻžāĻ° āĻāĻžāĻ āĻĨā§āĻā§ āĻļā§āĻ¨āĻ¤ā§ āĻāĻžāĻ!
āĻĻā§āĻ°āĻˇā§āĻāĻŦā§āĻ¯
āĻšā§āĻ¯āĻžāĻ, āĻšā§āĻ¯āĻžāĻ, āĻāĻŽāĻŋ āĻāĻāĻ¨āĻ āĻāĻāĻžāĻ¨ā§ āĻāĻāĻŋ, āĻāĻžāĻ°āĻŖ āĻāĻŽāĻŋ āĻ¸āĻšāĻ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻā§āĻ˛ā§ āĻ¯āĻžāĻāĻ¨āĻŋāĨ¤ āĻ¸ā§āĻā§āĻ°āĻŋāĻ s1-āĻāĻ° āĻāĻ¨ā§āĻ¯, āĻāĻ¨āĻā§āĻĄāĻŋāĻ āĻā§āĻŦāĻŋāĻ˛ā§āĻ° āĻāĻāĻ¨ 48 āĻŦāĻžāĻāĻ - āĻŽā§āĻ˛ āĻĢāĻžāĻāĻ˛ā§āĻ° āĻā§āĻ¯āĻŧā§ āĻ
āĻ¨ā§āĻ āĻŦā§āĻļāĻŋ, āĻāĻŦāĻ āĻ¤āĻžāĻ°āĻž āĻ
āĻ¤āĻŋāĻ°āĻŋāĻā§āĻ¤ āĻļā§āĻ¨ā§āĻ¯ā§āĻ° āĻāĻĨāĻž āĻā§āĻ˛ā§ āĻ¯āĻžāĻ¯āĻŧāĻ¨āĻŋ (āĻ¯ā§āĻ āĻāĻ°āĻž āĻļā§āĻ¨ā§āĻ¯ā§āĻ° āĻ¸āĻāĻā§āĻ¯āĻž 7) => āĻāĻŽā§āĻĒā§āĻ°ā§āĻļāĻ¨ āĻ
āĻ¨ā§āĻĒāĻžāĻ¤ āĻāĻā§āĻ° āĻāĻŽ āĻšāĻŦā§: 176 /(65 + 48*8 + 7) = 0.38āĨ¤ āĻāĻĒāĻ¨āĻŋ āĻ¯āĻĻāĻŋ āĻāĻāĻŋāĻ āĻ˛āĻā§āĻˇā§āĻ¯ āĻāĻ°ā§āĻ¨, āĻ¤āĻŦā§ āĻāĻĒāĻ¨āĻžāĻ° āĻŽā§āĻā§āĻ° āĻŽāĻ§ā§āĻ¯ā§ āĻ¨āĻ¯āĻŧāĨ¤ āĻšā§āĻ¯āĻžāĻ, āĻāĻ āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨ āĻā§āĻ āĻĢāĻžāĻāĻ˛ā§āĻ° āĻāĻ¨ā§āĻ¯ āĻ
āĻ¤ā§āĻ¯āĻ¨ā§āĻ¤ āĻ
āĻĻāĻā§āĻˇ āĻšāĻŦā§āĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻŦāĻĄāĻŧ āĻĢāĻžāĻāĻ˛ā§āĻ° āĻāĻŋ āĻšāĻŦā§? āĻĢāĻžāĻāĻ˛ā§āĻ° āĻāĻāĻžāĻ° āĻāĻ¨āĻā§āĻĄāĻŋāĻ āĻā§āĻŦāĻŋāĻ˛ā§āĻ° āĻāĻāĻžāĻ°ā§āĻ° āĻā§āĻ¯āĻŧā§ āĻ
āĻ¨ā§āĻ āĻŦāĻĄāĻŧāĨ¤ āĻāĻāĻžāĻ¨ā§āĻ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻ¯ā§āĻŽāĻ¨ āĻāĻžāĻ āĻāĻ°ā§! āĻāĻĻāĻžāĻšāĻ°āĻŖāĻ¸ā§āĻŦāĻ°ā§āĻĒ, āĻāĻ¨ā§āĻ¯
āĻāĻ¤ā§āĻ¸: www.habr.com