Created
August 19, 2017 09:16
-
-
Save nbyouri/5c0e3e25ca34eebd8e7f50c1114f8d8e to your computer and use it in GitHub Desktop.
huffman code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package Révision; | |
import java.util.Arrays; | |
import java.util.HashMap; | |
import java.util.Iterator; | |
import java.util.LinkedList; | |
import java.util.Map; | |
import java.util.PriorityQueue; | |
import java.util.Queue; | |
import java.util.Stack; | |
import java.util.TreeSet; | |
import java.util.Vector; | |
public class Huffman { | |
public static final int N = 256; // nb car | |
static class Node implements Comparable<Node> { | |
public char ch; | |
public int freq; | |
private final Node left, right; | |
public Node(char ch, int freq, Node left, Node right) { | |
this.ch = ch; | |
this.freq = freq; | |
this.left = left; | |
this.right = right; | |
} | |
public boolean isLeaf() { | |
return left == null && right == null; | |
} | |
public int compareTo(Node that) { | |
return this.freq - that.freq; | |
} | |
public String toString() { | |
return this.ch + " " + this.freq; | |
} | |
} | |
private static Node buildTrie(int[] freq) { | |
PriorityQueue<Node> pq = new PriorityQueue<Node>(); | |
for (char c = 0; c < N; c++) { | |
if (freq[c] > 0) { | |
pq.offer(new Node(c, freq[c], null, null)); | |
} | |
} | |
while (pq.size() > 1) { | |
Node x = pq.poll(); | |
Node y = pq.poll(); | |
System.out.println((x.ch == '\0' ? 'x' : x.ch) + " " + (y.ch == '\0' ? 'x' : y.ch) + " = " + (x.freq + y.freq)); | |
Node parent = new Node('\0', x.freq + y.freq, x, y); | |
pq.offer(parent); | |
} | |
return pq.poll(); | |
} | |
public static void buildCode(String[] st, Node x, String s) { | |
if (x.isLeaf()) { | |
st[x.ch] = s; | |
return; | |
} | |
buildCode(st, x.left, s + '0'); | |
buildCode(st, x.right, s + '1'); | |
} | |
public static void writeTrie(Node x) { | |
if (x.isLeaf()) { | |
BinaryStdOut.write(true); | |
BinaryStdOut.write(x.ch, 8); | |
return; | |
} | |
BinaryStdOut.write(false); | |
writeTrie(x.left); | |
writeTrie(x.right); | |
} | |
public static Node readTrie() { | |
if (BinaryStdIn.readBoolean()) | |
return new Node(BinaryStdIn.readChar(), 0, null, null); | |
return new Node('\0', 0, readTrie(), readTrie()); | |
} | |
public static void expand() { | |
Node root = readTrie(); | |
int N = BinaryStdIn.readInt(); | |
for (int i = 0; i < N; i++) { | |
Node x = root; | |
while (!x.isLeaf()) | |
if (BinaryStdIn.readBoolean()) | |
x = x.right; | |
else x = x.left; | |
BinaryStdOut.write(x.ch, 8); | |
} | |
} | |
public static void main(String[] args) { | |
char[] input = "abteehhwwwiiiissssss ".toCharArray(); | |
// étape 0 : remplir un tableau de fréquence des caractères | |
int[] charFreq = new int[N]; | |
for (char c : input) { | |
charFreq[c]++; | |
} | |
// étape 1 : construire l'arbre de trie | |
Node root = buildTrie(charFreq); | |
// étape 2 : construction des codes | |
String[] st = new String[N]; | |
buildCode(st, root, ""); | |
for (int i = 0; i < N; i++) { | |
if (charFreq[i] > 0) | |
System.out.println((char)i + " -> " + st[i]); | |
} | |
// étape 3 : encodage de l'input avec les codes | |
// écriture du trie | |
writeTrie(root); | |
BinaryStdOut.write(input.length); | |
// encodage du message | |
for (int i = 0; i < input.length; i++) { | |
String code = st[input[i]]; | |
for (int j = 0; j < code.length(); j++) | |
if (code.charAt(j) == '1') | |
BinaryStdOut.write(true); | |
else BinaryStdOut.write(false); | |
} | |
// Décodage de la chaine encodée | |
//expand(); | |
BinaryStdOut.close(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment