Блог

Я нахожусь в процессе кодирования кода Хаффмана, где я импортирую файл, генерирую код Хаффмана для каждого символа, затем вывожу двоичный файл в файл. Для импорта символов я использую сканер, который считывает каждый символ, помещает его в узел, который имеет значения считанного символа и частоту 1. Затем узел добавляется в PriorityQueue. Поскольку класс Node имеет метод compareTo, который сравнивает только частоту, как я могу реализовать компаратор для этого конкретного PriorityQueue, который сравнивает символы при сортировке в очереди?

Буквальный пример: Очередь символов должна быть отсортирована следующим образом:

 [A:1][A:1][A:1][B:1][C:1]
Next step:
[A:1][A:2][B:1][C:1]
Final:
[A:3][B:1][C:1]
  

Вот несколько фрагментов:

 protected class Node implements Comparable<Node>{
    Character symbol;
    int frequency;
    
    Node left = null;
    Node right = null;
    @Override
    public int compareTo(Node n) {
        return n.frequency < this.frequency ? 1 : (n.frequency == this.frequency ? 0 : -1);
    }
    
    public Node(Character c, int f){
        this.symbol = c;
        this.frequency = f;
    }
    public String toString(){
        return "[" this.symbol  "," this.frequency "]";
    }
  

Это PriorityQueue, для которого требуется пользовательский компаратор:

 public static PriorityQueue<Node> gatherFrequency(String file) throws Exception{
    File f = new File(file);
    Scanner reader = new Scanner(f);
    PriorityQueue<Node> PQ = new PriorityQueue<Node>();
    while(reader.hasNext()){
        for(int i = 0; i < reader.next().length();i  ){
            PQ.add(new Node(reader.next().charAt(0),1));
        }
    }
    if(PQ.size()>1){ //during this loop the nodes should be compared by character value
        while(PQ.size() > 1){
            Node a = PQ.remove();
            Node b = PQ.remove();
            if(a.symbol.compareTo(b.symbol)==0){
                Node c = new Node(a.symbol, a.frequency   b.frequency);
                PQ.add(c);
            }
            else break;
        }
        return PQ;
    }
    return PQ;
    
}
  

Это новый метод, который я создал, используя HashMap:

 public static Collection<Entry<Character,Integer>> gatherFrequency(String file) throws Exception{
        File f = new File(file);
        Scanner reader = new Scanner(f);
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        while(reader.hasNext()){
            for(int i = 0; i < reader.next().length();i  ){
                Character key = reader.next().charAt(i);
                if(map.containsKey(reader.next().charAt(i))){
                    int freq = map.get(key);
                    map.put(key, freq 1);
                }
                else{
                    map.put(key, 1);
                }
            }
        }
        return map.entrySet();
    }

    
  

Стандартный подход к реализации деревьев Хаффмана заключается в использовании хэш-карты (в Java вы, вероятно, использовали бы HashMap<Character, Integer> ) для подсчета частоты для каждой буквы и вставки в очередь приоритетов одного узла для каждой буквы. Итак, при построении самого дерева Хаффмана вы начинаете с приоритетной очереди, которая уже находится в «конечном» состоянии, которое вы показали. Затем алгоритм Хаффмана повторно извлекает два узла из очереди приоритетов, создает новый родительский узел для этих двух узлов и вставляет новый узел в очередь приоритетов.