Huffman Tree với tần số cho nhầm lẫn như thế nào để bắt đầu? Java

Question

Tôi đang cố gắng hiểu những gì cần làm với bài tập về nhà của tôi. Tôi đang cố gắng tạo ra một cây Huffman sẽ mã hóa và giải mã các thông điệp trong Java. Tôi đã cho Strings và Frequency.

[a=10, b=15, c=12, e=3, nl=4, sp=13, t=1]. 

Tôi biết rằng với Huffman Tree, bạn có hai tần suất thấp nhất và đặt chúng thành một cây có tổng Tần suất làm cha mẹ. Tôi hiểu rằng việc sử dụng Hàng đợi ưu tiên tôi có thể chèn tất cả Tần suất vào nó và sử dụng phương pháp remove() để đưa ra 2 Tần suất thấp nhất. Sau đó thêm chúng lại với nhau để có được trọng lượng của cả hai, sau đó chèn trọng lượng đó trở lại vào hàng đợi và lặp lại.

The Tree thức nên giữ trọng lượng của

[58=root, root.left = 33, root.right = 25] 
[33.left = 18, 18.left = 8, 8.left = 4] 

Tôi không chắc chắn chính xác làm thế nào để thậm chí bắt đầu để thực hiện một mã Huffman Tree rằng sẽ có thể tạo ra các cây với tần số và hiển thị Tree. Tôi đã xem xét các mã khác và có vẻ như tất cả chúng đều đang tạo từ Mã đầu vào truyền trực tuyến.

Mọi trợ giúp sẽ rất tuyệt vời trong việc giúp tôi. Cảm ơn trước!

tôi là giả để in ra với một định dạng như: (pre-order traversal)

58 
- 33 
- - 18 
- - - 8 
- - - - 4 
- - - - - 1:t 
- - - - - 3:e 
- - - - 4:nl 
- - - 10:a 
- - 15:b 
- 25 
- - 12:c 
- - 13:sp 

Answer 1

import java.util.PriorityQueue; 

public class Node implements Comparable<Node> { 
    Node left; 
    Node right; 
    Node parent; 
    String text; 
    int frequency; 

    public Node(String textIn, int frequencyIn) { 
     text = textIn; 
     frequency = frequencyIn; 
    } 

    public Node(int frequencyIn) { 
     text = ""; 
     frequency = frequencyIn; 
    } 

    public int compareTo(Node n) { 
     if (frequency < n.frequency) { 
      return -1; 
     } 
     else if(frequency > n.frequency) { 
      return 1; 
     } 
     return 0; 
    } 

    public static void printFromPreOrder(Node n, String dashes) { 
     // print with colon if leaf node 
     if (n.text != "") { 
      System.out.println(dashes + n.frequency + ":" + n.text); 
     } 
     else { 
      System.out.println(dashes + n.frequency); 
     } 

     // Start recursive on left child then right 
     if (n.left != null) { 
      printFromPreOrder(n.left, dashes + "-"); 
     } 
     if (n.right != null) { 
      printFromPreOrder(n.right, dashes + "-"); 
     } 
    } 

    // Returns root node to pass to printFromPreOrder 
    public static Node makeHuffmanTree(int frequencies[], String text[]) { 
     PriorityQueue<Node> queue = new PriorityQueue<Node>(); 
     for (int i = 0; i < text.length; i++) { 
      Node n = new Node(text[i], frequencies[i]); 
      queue.add(n); 
     } 
     Node root = null; 
     while (queue.size() > 1) { 
      Node least1 = queue.poll(); 
      Node least2 = queue.poll(); 
      Node combined = new Node(least1.frequency + least2.frequency); 
      combined.right = least1; 
      combined.left = least2; 
      least1.parent = combined; 
      least2.parent = combined; 
      queue.add(combined); 
      // Keep track until we actually find the root 
      root = combined; 
     } 
     return root; 
    } 

    public static void main(String[] args) { 
     int frequencies[] = {10, 15, 12, 3, 4, 13, 1}; 
     String text[] = {"a", "b", "c", "e", "nl", "sp", "t"}; 
     Node root = Node.makeHuffmanTree(frequencies, text); 
     Node.printFromPreOrder(root, ""); 
    } 
} 

này sẽ làm việc cho bạn. Tôi đã bao gồm ví dụ của bạn, nhưng nó sẽ làm việc cho bất kỳ số lượng tần số và văn bản. Chỉ cần đảm bảo tần số và văn bản có cùng kích thước vì tôi không kiểm tra lỗi.