รหัส Huffman

นึกภาพก่อน

รหัสมอร์สใช้จุดเดียวแทน E ซึ่งพบบ่อยที่สุดในภาษาอังกฤษ แต่ใช้สี่สัญญาณแทน Q ที่นาน ๆ พบที ข้อความโดยรวมจึงสั้นกว่าการให้ทุกตัวอักษรยาวเท่ากัน

รหัส Huffman ใช้ความคิดเดียวกันกับบิต: ตัวอักษรที่พบบ่อยได้รหัสสั้น ตัวที่พบน้อยได้รหัสยาว และใช้ต้นไม้ทวิภาคเป็นเครื่องมือสร้างรหัส

รหัสความยาวคงที่ กับความยาวแปรได้

ข้อความหนึ่งมีตัวอักษร 6 ชนิด จำนวนครั้งที่พบดังนี้:

• ความยาวคงที่: 6 ชนิดต้องใช้ 3 บิตต่อตัว รวม 40×3 + 21×3 + 15×3 + 14×3 + 8×3 + 2×3 = 300 บิต
• ความยาวแปรได้: 40×1 + 21×3 + 15×3 + 14×3 + 8×4 + 2×4 = 230 บิต

ประหยัดได้เพราะ ช ซึ่งพบถึง 40 ครั้งใช้เพียงบิตเดียว

วิธีสร้างต้นไม้ Huffman

1. สร้างปมเก็บจำนวนของตัวอักษรแต่ละตัว
2. สร้างปมใหม่เก็บผลรวมของ สองปมที่มีค่าน้อยที่สุด โดยให้สองปมนั้นเป็นลูก
3. ทำซ้ำข้อ 2 ไปเรื่อย ๆ จนเหลือต้นเดียว
4. ใส่รหัส: เส้นด้านซ้าย = 0 เส้นด้านขวา = 1

รหัสของตัวอักษรคือบิตตามทางเดินจากรากลงไปถึงใบของตัวนั้น

ตัวอย่างไล่ทีละขั้น

ใช้ข้อมูลข้างบน (ช:40, ม:21, ย:15, ป:14, ส:8, า:2)

6 ตัวอักษรใช้ 5 รอบ (n − 1 รอบ) ต้นไม้ในสไลด์:

             100
           0/   \1
          ช      60
              0/    \1
             36      24
           0/ \1   0/  \1
           ม   ย   ป    10
                      0/  \1
                      ส    า

อ่านรหัส: ช = 0, ม = 100, ย = 101, ป = 110, ส = 1110, า = 1111

ช อยู่ติดราก ได้รหัส 1 บิต ส่วน ส และ า ถูกรวมตั้งแต่รอบแรกจึงอยู่ลึกสุด ได้รหัส 4 บิต

public static HuffmanTree coding(int[] freq) {
  BinaryMinHeap h = new BinaryMinHeap();
  for (int i = 0; i < freq.length; i++)
    h.enqueue(new HuffmanTree(freq[i], null, null));
  for (int i = 0; i < freq.length - 1; i++) {
    HuffmanTree t1 = (HuffmanTree) h.dequeue();
    HuffmanTree t2 = (HuffmanTree) h.dequeue();
    int f = t1.freq() + t2.freq();
    h.enqueue(new HuffmanTree(f, t1.root, t2.root));
  }
  return (HuffmanTree) h.dequeue();
}

ทำไมถอดรหัสได้ไม่กำกวม

ตัวอักษรอยู่ที่ ใบ เท่านั้น ทางเดินไปใบหนึ่งจึงไม่มีทางเป็นส่วนต้นของทางเดินไปอีกใบ ไม่มีรหัสของตัวใดเป็นส่วนขึ้นต้นของรหัสตัวอื่น เมื่ออ่านบิตจากรากลงมาจนถึงใบ ก็รู้ทันทีว่าจบตัวอักษรแล้ว แล้วกลับไปเริ่มที่รากใหม่

ถอดรหัส 0100110: 0 → ช, 100 → ม, 110 → ป

โปรแกรม

"เลือกสองตัวที่น้อยที่สุด" ซ้ำ ๆ คืองานของ priority queue แบบ min heap:

public static HuffmanTree coding(int[] freq) {
  BinaryMinHeap h = new BinaryMinHeap();
  for (int i = 0; i < freq.length; i++) {
    h.enqueue(new HuffmanTree(freq[i], null, null));
  }
  for (int i = 0; i < freq.length - 1; i++) {
    HuffmanTree t1 = (HuffmanTree) h.dequeue();
    HuffmanTree t2 = (HuffmanTree) h.dequeue();
    int f = t1.freq() + t2.freq();
    h.enqueue(new HuffmanTree(f, t1.root, t2.root));
  }
  return (HuffmanTree) h.dequeue();
}

• ลูปแรก: สร้างต้นไม้ปมเดียวของทุกตัวอักษรใส่ heap (ชั้นล่างสุดของต้นไม้ Huffman)
• ลูปที่สอง: วน n − 1 รอบ dequeue สองต้นที่น้อยสุด รวมเป็นต้นใหม่ แล้ว enqueue กลับ
• สุดท้าย dequeue ต้นเดียวที่เหลือ

public class HuffmanTree extends BinaryTree implements Comparable {
  public HuffmanTree(int freq, Node left, Node right) {
    root = new Node(new Integer(freq), left, right);
  }
  public int freq() {
    return ((Integer) root.element).intValue();
  }
  public int compareTo(Object obj) {
    return freq() - ((HuffmanTree) obj).freq();
  }
}

HuffmanTree ต้อง implements Comparable เพราะ heap เปรียบเทียบข้อมูลด้วย compareTo (เทียบจากความถี่ที่ราก)

พิมพ์รหัส

private void printCodes(Node r, int[] c, int k) {
  if (r.isLeaf()) {
    System.out.print(r.element + " \t: ");
    for (int i = 0; i < k; i++) System.out.print(c[i]);
    System.out.println();
  } else {
    c[k] = 0;
    printCodes(r.left, c, k + 1);
    c[k] = 1;
    printCodes(r.right, c, k + 1);
  }
}

เดินลงซ้ายจดบิต 0 เดินลงขวาจดบิต 1 เมื่อถึงใบก็พิมพ์บิตที่จดมาทั้งหมด (เป็นการแวะผ่านแบบเรียกซ้ำ)

ผลการรัน int[] f = { 5, 9, 12, 13, 16, 45 } ในสไลด์:

45  : 0
12  : 100
13  : 101
5   : 1100
9   : 1101
16  : 111

ความสัมพันธ์ของคลาส

เป็นตัวอย่างที่รวมเรื่อง inheritance, interface และ polymorphism จากส่วน OOP ไว้ครบ

จุดที่มักพลาด

1. รวมสองตัวที่มากที่สุด

ต้องรวมสองตัวที่ น้อย ที่สุด ตัวที่พบน้อยจึงลงไปอยู่ลึก

2. ลืมว่าปมรวมก็เข้าแข่งในรอบถัดไป

รอบที่ 2 เลือกระหว่าง 40, 21, 15, 14 และ 10 (ปมรวม) ไม่ใช่เฉพาะตัวอักษรที่เหลือ

3. คำนวณบิตรวมผิด

บิตรวม = ผลรวมของ (ความถี่ × ความยาวรหัส) ของทุกตัว ไม่ใช่ผลรวมความยาวรหัส

4. ใช้ max heap

ต้องเป็น min heap เพื่อ dequeue ตัวน้อยสุด

5. คิดว่าตัวอักษรอยู่ที่ปมภายในได้

ตัวอักษรอยู่ที่ใบเท่านั้น ปมภายในเก็บแต่ผลรวม

6. จำนวนรอบ

n ตัวอักษรรวม n − 1 รอบ และได้ปมภายใน n − 1 ปม

7. คิดว่าต้นไม้ Huffman มีแบบเดียว

ถ้าความถี่เท่ากันหรือสลับซ้ายขวา ได้ต้นไม้ต่างกันได้ แต่บิตรวมเท่ากัน

ที่มา: BinaryTREE_8.pdf หน้า 36–59