Stepik - 4.2. Коды Хаффмана
Описание задачи
По данной непустой строке ss длины не более 10^4, состоящей из строчных букв латинского алфавита, постройте оптимальный беспрефиксный код. В первой строке выведите количество различных букв k, встречающихся в строке, и размер получившейся закодированной строки. В следующих k строках запишите коды букв в формате “letter: code”. В последней строке выведите закодированную строку.
Надежный шаг
Чтобы решить данную задачу нужно посчитать частоту вхождения каждого символа в строку а после построить дерево где листья - символы имеющие свой вес (частота вхождения) а узлы - сумма всех нижестоящих узлов/листьев.
Это позволит потом вычислить оптимальные коды, так как при правильном построении данного бинарного дерева наиболее часто встречающиеся символы будут расположены ближе к корню а значит займут меньшее место в итоговом коде.
Надежным шагом в данной задаче является выбор двух узлов (в начале там только символы) с наименьшими вхождениями и помещением их в один узел (так, чтобы они стали братьями).
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.stream.Collectors;
/**
* Main
*
* @author Vladislav Sidlyarevich <vlsidlyarevich@gmail.com>
* Created on 4/28/21.
*/
public class Main {
public static void main(String[] args) {
Main main = new Main();
main.run();
}
public void run() {
Scanner scanner = new Scanner(System.in).useDelimiter("\n");
String input = scanner.nextLine();
//Calculate frequency of chars in string
Map<Character, Integer> frequency = calculateFrequency(input);
PriorityQueue<Node> nodes = new PriorityQueue<>();
//Add initial nodes
for (Map.Entry<Character, Integer> entry : frequency.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
//Build binary tree
while (nodes.size() != 1) {
Node firstNode = nodes.poll();
Node secondNode = nodes.poll();
Node newNode = new Node(firstNode, secondNode, firstNode.weight + secondNode.weight);
nodes.remove(firstNode);
nodes.remove(secondNode);
nodes.add(newNode);
}
Map<Character, String> codes = frequency.keySet().stream()
.collect(Collectors.toMap(v -> v, v -> ""));
//Traverse the tree and fulfill codes map
fillCodes(nodes.peek(), codes, "");
//Encode the input
String encodedInput = encode(codes, input);
printResults(codes, encodedInput);
}
private void printResults(final Map<Character, String> codes, final String encodedInput) {
System.out.println(codes.keySet().size() + " " + encodedInput.length());
codes.forEach((ch, code) -> System.out.println(ch + ": " + code));
System.out.println(encodedInput);
}
private String encode(final Map<Character, String> codes, final String input) {
StringBuilder result = new StringBuilder();
for (char ch : input.toCharArray()) {
result.append(codes.get(ch));
}
return result.toString();
}
private Map<Character, Integer> calculateFrequency(final String input) {
Map<Character, Integer> result = new HashMap<>();
for (char c : input.toCharArray()) {
result.merge(c, 1, Integer::sum);
}
return result;
}
private void fillCodes(Node root, Map<Character, String> codes, String code) {
if (root.isLeaf()) {
//Put code into codes dictionary and handle case when single node
codes.put(root.character, code.isEmpty() ? "0" : code);
return;
}
fillCodes(root.leftNode, codes, code + "0");
fillCodes(root.rightNode, codes, code + "1");
}
static class Node implements Comparable<Node> {
private Node leftNode;
private Node rightNode;
private Character character;
private Integer weight;
public Node(final Character character, final Integer weight) {
this.character = character;
this.weight = weight;
}
public Node(final Node leftNode, final Node rightNode, final Integer weight) {
this.leftNode = leftNode;
this.rightNode = rightNode;
this.weight = weight;
}
boolean isLeaf() {
return this.leftNode == null && this.rightNode == null && this.character != null;
}
@Override
public int compareTo(final Node o) {
if (o.weight.equals(weight)) return 0;
return o.weight > weight ? -1 : 1;
}
}
}