Skip to content

Instantly share code, notes, and snippets.

@mvoitko
Created February 4, 2020 16:00
Show Gist options
  • Save mvoitko/01bcc2a80db92f39d7d47d8dfaacea51 to your computer and use it in GitHub Desktop.
Save mvoitko/01bcc2a80db92f39d7d47d8dfaacea51 to your computer and use it in GitHub Desktop.
Huffman coding algorithm
// При кодировании информации каждый символ заменяется на свой код.
// Декодирование для префиксных кодов однозначно и выполняется слева направо.
// Чтобы эффективно реализовать процесс декодирования, необходимо хранить информацию о коде в удобной форме.
// Например, можно представить код в виде двоичного дерева, листья которого соответствуют кодируемым символам.
// А путь от вершины дерева до кодируемого символа определяет кодирующую последовательность битов: поворот налево дает 0, направо — 1.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Huffman {
public class Node implements Comparable<Node> {
final int sum;
String code;
public Node(int sum) {
this.sum = sum;
}
public void buildCode(String code) {
this.code = code;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.sum, o.sum);
}
}
public class InnerNode extends Node{
Node left;
Node right;
public InnerNode(Node left, Node right) {
super(left.sum + right.sum);
this.left = left;
this.right = right;
}
@Override
public void buildCode(String code) {
super.buildCode(code);
this.left.buildCode(code + "1");
this.right.buildCode(code + "0");
}
}
public class LeafNode extends Node{
char symbol;
public LeafNode(char symbol, int frequency) {
super(frequency);
this.symbol = symbol;
}
@Override
public void buildCode(String code) {
super.buildCode(code);
System.out.println(symbol + ": " + code);
}
}
public static void main(String[] args) throws FileNotFoundException {
new Huffman().run();
}
private void run() throws FileNotFoundException {
Scanner in = new Scanner(new File("input.txt"));
String text = in.nextLine();
Map<Character, Integer> map = new HashMap();
for(int i = 0; i < text.length(); ++i) {
char ch = text.charAt(i);
if (map.containsKey(ch)) {
int value = map.get(ch);
map.put(ch, value+1);
}
else {
map.put(ch, 1);
}
}
PriorityQueue<Node> pq = new PriorityQueue<Node>();
for(Entry<Character, Integer> entry: map.entrySet()) {
LeafNode leaf = new LeafNode(entry.getKey(), entry.getValue());
pq.add(leaf);
}
while(pq.size() > 1) {
Node first = pq.poll();
Node second = pq.poll();
InnerNode inode = new InnerNode(first, second);
pq.add(inode);
}
Node root = pq.poll();
root.buildCode("");
in.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment