พัฒนายูทิลิตีบีบอัดข้อมูลด้วยโค้ด Huffman โดยใช้ Haskell

การสร้างโปรแกรมบีบอัดข้อมูลด้วยการเข้ารหัส Huffman

• โค้ด Huffman คืออะไร?
  • เป็นการบีบอัดข้อมูลโดยแมปอักขระแต่ละตัวเข้ากับลำดับบิตที่ไม่ซ้ำกัน
  • อักขระที่ปรากฏบ่อยมักถูกแมปเป็นลำดับบิตที่สั้นกว่า ส่วนอักขระที่พบไม่บ่อยมักถูกแมปเป็นลำดับบิตที่ยาวกว่า
  • ตัวอย่าง: สำหรับสตริง aaab จะมีการแมป a เป็น 1 และ b เป็น 0 จึงบีบอัดได้เป็น 1110

โค้ดแบบไม่มีคำนำหน้า

• โค้ดแบบไม่มีคำนำหน้าคืออะไร?
  • คือการกำหนดให้โค้ดเวิร์ดใด ๆ ไม่เป็นคำนำหน้าของโค้ดเวิร์ดอื่น
  • ตัวอย่าง: สำหรับ aaabc จะมีการแมป a เป็น 1, b เป็น 00, c เป็น 01 จึงบีบอัดได้เป็น 1110001

การสร้างโค้ดแบบไม่มีคำนำหน้า

• วิธีสร้างโค้ดแบบไม่มีคำนำหน้า
  • วางอักขระทั้งหมดไว้เป็นใบของต้นไม้ทวิภาคสมบูรณ์
  • กำกับกิ่งซ้ายเป็น 1 และกิ่งขวาเป็น 0
  • เส้นทางจากรากไปยังใบจะอธิบายโค้ดเวิร์ดของอักขระแต่ละตัว

การเขียนตัวเข้ารหัส

• การนิยามชนิดข้อมูล

  • นิยามชนิด Bit, Code, FreqMap, CodeMap, Weight, HTree
  • HTree ประกอบด้วย Leaf และ Fork

• ฟังก์ชันเข้ารหัส

  • ฟังก์ชันที่แปลงสตริงเป็นบิต
  • ใช้ FreqMap เพื่อคำนวณความถี่ของอักขระแต่ละตัว แล้วสร้างต้นไม้ Huffman จากข้อมูลดังกล่าว
  • สร้างโค้ดเวิร์ดของอักขระแต่ละตัวจากต้นไม้ Huffman

• ฟังก์ชันถอดรหัส

  • ฟังก์ชันที่แปลงบิตกลับเป็นสตริงเดิม
  • ใช้ต้นไม้ Huffman เพื่อถอดรหัสบิตทีละลำดับ

การทำงานร่วมกับไฟล์ไบนารี

• การเข้ารหัสข้อมูลไบนารี
  • ใช้โมดูล Data.ByteString.Char8 เพื่ออ่านไบต์เป็นอักขระ
  • ใช้ตัวเข้ารหัสข้อความเพื่อเข้ารหัสข้อมูลไบนารี

การทำซีเรียลไลซ์

• ฟังก์ชันซีเรียลไลซ์
  • แปลง FreqMap และบิตเป็นไบต์จริงเพื่อบันทึกลงไฟล์
  • ใช้ Put monad เพื่อสร้าง ByteString ได้อย่างมีประสิทธิภาพ

การดีซีเรียลไลซ์

• ฟังก์ชันดีซีเรียลไลซ์
  • แปลงข้อมูลที่อ่านจากไฟล์กลับเป็น FreqMap และบิต
  • ใช้ Get monad เพื่อดีซีเรียลไลซ์ FreqMap

การรวมโค้ดทั้งหมดเข้าด้วยกัน

• ฟังก์ชันบีบอัดและขยายไฟล์
  • ฟังก์ชัน compress: อ่านไฟล์ สร้าง frequency map เข้ารหัสข้อมูล แล้วบันทึกเป็นไฟล์บีบอัด
  • ฟังก์ชัน decompress: อ่านไฟล์บีบอัด ถอดรหัสข้อมูล แล้วบันทึกกลับเป็นไฟล์ต้นฉบับ

สิ่งที่ปรับปรุงได้

• มัลติเธรด

  • ถอดรหัสแต่ละส่วนของไฟล์แบบขนาน
  • เพิ่มตารางที่ระบุขอบเขตของแต่ละส่วนและขนาดที่คาดว่าจะถอดรหัสได้ เพื่อให้ประมวลผลแบบขนานได้

• การเข้ารหัสแบบ single-pass

  • สร้าง frequency map ไปพร้อมกับการเข้ารหัสแบบเรียลไทม์
  • ไม่จำเป็นต้องใส่ frequency map ไว้ที่ส่วนต้นของไฟล์

• โค้ด Huffman แบบ canonical

  • ถอดรหัสด้วยการทำดัชนีเวกเตอร์แทนการไล่ต้นไม้ ทำให้มีความซับซ้อนเวลา O(1)

• การสร้างโค้ดที่เร็วขึ้น

  • หากต้องการลองเข้ารหัสแบบ single-pass จำเป็นต้องเพิ่มความเร็วในการสร้าง code map

ความเห็นของ GN⁺

• ข้อดีของการเข้ารหัส Huffman

  • ทำให้บีบอัดข้อมูลได้อย่างมีประสิทธิภาพด้วยการแมปอักขระที่พบบ่อยเป็นลำดับบิตที่สั้นกว่า
  • สามารถจัดการข้อมูลขนาดใหญ่ได้โดยใช้หน่วยความจำให้น้อยที่สุด

• ข้อดีของ Haskell

  • สามารถเขียนโค้ดแบบแยกเป็นโมดูลได้โดยอาศัยข้อดีของการเขียนโปรแกรมเชิงฟังก์ชัน
  • ปรับการใช้หน่วยความจำให้เหมาะสมได้ผ่านการประเมินผลแบบ lazy

• โปรเจ็กต์ที่มีความสามารถคล้ายกัน

  • มีเครื่องมือบีบอัดข้อมูลหลากหลาย เช่น gzip, bzip2
  • การเปรียบเทียบข้อดีข้อเสียของแต่ละเครื่องมือเพื่อเลือกใช้ให้เหมาะสมเป็นสิ่งสำคัญ

• สิ่งที่ควรคำนึงเมื่อจะนำเทคโนโลยีใหม่มาใช้

  • ควรเลือกอัลกอริทึมที่เหมาะสมโดยพิจารณาทั้งประสิทธิภาพและการใช้หน่วยความจำ
  • สามารถเพิ่มประสิทธิภาพได้ด้วยเทคนิคอย่างการเข้ารหัสแบบ single-pass

[GN⁺]

ความคิดเห็นจาก Hacker News

• มีอัลกอริทึมแบบ in-place ที่อิงกับอาร์เรย์อยู่แล้ว จึงลดความจำเป็นในการจัดสรรทรีและไล่ตามพอยน์เตอร์

  • ตอนเรียนมหาวิทยาลัยไม่รู้เลยว่ามีวิธีอื่นนอกจากแนวทางแบบทรี
  • แนวทางแบบทรีนั้นเข้าใจง่ายและมีประโยชน์ แต่เมื่อจำเป็นต้องประมวลผลข้อมูลจำนวนมากอย่างรวดเร็ว การใช้อาร์เรย์แบบ in-place นั้นสมเหตุสมผลกว่า
  • เอกสารอ้างอิง: "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

• การบอกว่าต้องทำให้โค้ดเวิร์ดไม่เป็น prefix ของโค้ดเวิร์ดอื่นนั้น ในเชิงเทคนิคแล้วไม่ถูกต้อง

  • คลาสของโค้ดที่ถอดรหัสได้อย่างเอกลักษณ์เป็นซูเปอร์เซตของ prefix code
  • ตัวอย่างเช่น ลำดับย้อนกลับของ prefix code ก็ยังถอดรหัสได้อย่างชัดเจน
  • โค้ดตัวอย่าง:

    a 1
    b 00
    c 10
    

  • แม้โค้ดของ 'a' จะเป็น prefix ของโค้ดของ 'c' แต่ถ้าประมวลผลแบบย้อนกลับก็ยังถอดรหัสได้อย่างชัดเจน

• สงสัยว่ามีทิวทอเรียลคล้ายกันที่ครอบคลุมฟีเจอร์ขั้นสูงกว่านี้ในการเขียนโปรแกรม Haskell หรือไม่ (เช่น monad transformers, lenses ฯลฯ)

• คอร์ส Functional Programming ของ Coursera (Scala) มีโจทย์ Huffman coding ที่คล้ายกัน

  • ลิงก์: Coursera Scala Functional Programming

• เคยใช้ Huffman code เพื่อให้โปรแกรมแมโครของโปรเซสเซอร์ MICMAC ทำงานด้วยจำนวน microcycle และ microinstruction ขั้นต่ำ

  • ได้ทำฮิสโตแกรมของ macro instruction แล้วใช้สิ่งนั้นเป็นฐานในการเขียนโปรแกรมไมโครโค้ดแบบ progressive decoding
  • ในทางปฏิบัติ มันคงช้าและใช้งานไม่สะดวก
  • ข้อดีของ Huffman code คือสามารถปรับความลึกของ prefix ตามการกระจายของค่าได้
  • ต้องจัดการ branch prediction ในโมเดลโปรเซสเซอร์แบบไม่โอเวอร์แล็ปไปป์ไลน์

• ข้อมูลเพิ่มเติมเกี่ยวกับ Huffman coding: Rosetta Code Huffman Coding

• คำถามถึงโปรแกรมเมอร์ Haskell: อยากรู้ว่าประสิทธิภาพของ Haskell เป็นอย่างไรสำหรับนักพัฒนาที่ต้องการเขียนโค้ดที่ปรับแต่งอย่างเหมาะสม

  • สนใจเป็นพิเศษเรื่องประสิทธิภาพของการคำนวณเชิงตัวเลขที่ใช้ matrix operations และ SIMD

• ขอบคุณที่แชร์

• มีคำผิดในตารางของส่วน "Creating prefix-free codes"

  • D ควรเป็น '0010' (ตอนนี้ระบุผิดเป็น '0110')
  • นอกเหนือจากนั้นก็เป็นบทความที่อ่านได้ยอดเยี่ยม

• arithmetic coding ดีกว่าแทบทุกด้าน

  • ใช้ RAM และโค้ดน้อยกว่าในการ implement
  • ให้ประสิทธิภาพการบีบอัดและการคลายบีบอัดดีกว่า
  • อัปเดตความน่าจะเป็นที่สัญลักษณ์อื่นจะปรากฏระหว่างสตรีมแบบไดนามิกได้ง่ายกว่า
  • ที่มีการใช้ Huffman code เพราะมันถูกคิดค้นก่อน และ arithmetic coding เคยติดสิทธิบัตร
  • ตอนนี้สิทธิบัตรหมดอายุแล้ว จึงควรใช้การออกแบบที่ดีกว่า