Я получаю некоторую логическую ошибку в кодировке Хаффмана java - PullRequest
Новая
       16

Я получаю некоторую логическую ошибку в кодировке Хаффмана java

1 голос
/ 14 января 2020

Вот код ... 

public class Huffman_Coding {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a string to compress: ");
        String str = sc.nextLine();
        sc.close();
        HashString hs = new HashString();

        HashMap<Character, Integer> hm = hs.getStringHash(str);

        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        for (char ch : hm.keySet()) {
            pq.add(new Node(null, null, hm.get(ch), ch));
        }
        System.out.println(pq);
        while (pq.size() != 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node(left, right, left.freq + right.freq, '\0');
            pq.add(parent);
            System.out.println(pq);
        }
        Huffman_Tree ht = new Huffman_Tree();
        String ans = "";
        ht.inOrder(pq.poll(), ans);
    }
}

class Node implements Comparable<Node> {

    @Override
    public String toString() {
        return "Node [freq=" + freq + ", ch=" + ch + "]";
    }

    Node lptr;
    Node rptr;
    int freq;
    char ch;

    Node(Node lptr, Node rptr, int freq, char ch) {
        this.freq = freq;
        this.lptr = lptr;
        this.rptr = rptr;
        this.ch = ch;
    }

    public int compareTo(Node o) {

        int comparedvalue = Integer.compare(this.freq, o.freq);
        if (comparedvalue != 0)
            return comparedvalue;
        else
            return Integer.compare(this.ch, o.ch);
        }
    }

    boolean isLeaf() {
        return this.lptr == null && this.rptr == null;
    }
}

class Huffman_Tree {
    void inOrder(Node root, String code) {
        if (!root.isLeaf()) {
            inOrder(root.lptr, code + '0');
            inOrder(root.rptr, code + '1');

        } else
            System.out.println(root.ch + " : " + code);

    }
}

Здесь для входной строки abccddeeee я получаю что-то вроде: 

[Node [freq=1, ch=a], Node [freq=1, ch=b], Node [freq=2, ch=c], Node [freq=2, ch=d], Node [freq=4, ch=e]]
[Node [freq=2, ch= ]]

Я запутался, почему в Второй шаг Узел, имеющий «d», идет впереди «e». Это дает мне ошибки в окончательном кодировании. Почему метод CompareTo не работает, я не могу понять.

getHashString возвращает Ха sh, в котором есть символы в ключе и их частота в значении.

1 Ответ

1 голос
/ 14 января 2020

Я не могу понять, почему порядок элементов в PriorityQueue не является ожидаемым после опроса элементов муравья добавления новых элементов "syntheti c", но я думаю, что вы можете решить проблему, переключившись на TreeSet, как я успешно справился с 

TreeSet<Node> pq = new TreeSet<Node>((n1, n2) -> n1.compareTo(n2)); // explicit but unnecessary comparator

и изменив каждый pq.poll() вызов на pq.pollFirst() ...

Я надеюсь, что этот обходной путь может помочь вам!

РЕДАКТИРОВАТЬ

Как вы можете прочитать в официальной PriorityQueue документации , * Итератор, предоставленный в методе iterator (), не является гарантированно пройти элементы очереди приоритета в любом конкретном порядке. Если вам нужен упорядоченный обход, рассмотрите возможность использования Arrays.sort (pq.toArray ()). *

Это должно объяснить, почему при вызове метода toString() элементы очереди отображаются в порядке, отличном от ожидаемого приоритета. порядок ...

...