สร้างยูทิลิตีบีบอัดแบบใช้รหัส Huffman ด้วย Haskell

 (lazamar.github.io)
1 คะแนน โดย GN⁺ 2024-07-06 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • สาธิตการสร้างตัวบีบอัด Huffman coding ด้วย Haskell ราว 150 บรรทัด พร้อมโครงสร้างที่รองรับการเข้ารหัสและถอดรหัสไฟล์ไบนารีแบบกำหนดเองโดยใช้หน่วยความจำคงที่
  • รหัส Huffman จะกำหนดลำดับบิตสั้นให้กับค่าที่พบบ่อย และใช้เงื่อนไข prefix-free code เพื่อให้ตัวถอดรหัสตีความลำดับบิตได้อย่างไม่กำกวม
  • การติดตั้งใช้ FreqMap, HTree, CodeMap เพื่อสร้างต้นไม้จากตารางความถี่ และอาศัย lazy evaluation ของ concatMap กับตัวถอดรหัสแบบเรียกซ้ำเพื่อสร้างผลลัพธ์แบบค่อยเป็นค่อยไป
  • ไฟล์ไบนารีถูกจัดการผ่าน Data.ByteString.Char8 โดยมองไบต์เป็น Char และเก็บ ตารางความถี่ ไว้ก่อนข้อมูลบีบอัด พร้อมแพดลำดับบิตให้ครบระดับไบต์ก่อนบันทึก
  • ในการทดสอบ War and Peace ลดจาก 3.2M เหลือ 1.9M ส่วนไบนารี ghcup ขนาด 106M ลดเหลือ 84M และพบว่า maximum resident set size ต่ำกว่า 300KB

ไอเดียพื้นฐานของการบีบอัดด้วยรหัส Huffman

  • เป้าหมายคือสร้างยูทิลิตีบีบอัดข้อมูลด้วย Huffman coding โดยใช้ Haskell ราว 150 บรรทัด
  • โค้ดทั้งหมดเผยแพร่อยู่ใน GitHub repository
  • รหัส Huffman จะกำหนด ลำดับบิต ที่ไม่ซ้ำกันให้กับอักขระหรือค่าแต่ละตัว
    • ค่าที่พบได้บ่อยมักใช้ลำดับบิตที่สั้นกว่า
    • ค่าที่พบได้น้อยจะใช้ลำดับบิตที่ยาวกว่า
    • การที่ค่าที่พบบ่อยถูกแทนด้วยบิตน้อยกว่ารูปแบบเดิมทำให้เกิดการบีบอัด
  • ตัวอย่าง aaab หากกำหนด a = 1, b = 0 จะได้ผลลัพธ์เป็น 1110
    • เป็นตัวอย่างที่แสดงให้เห็นว่าสตริงซึ่งต้องใช้ 4 ไบต์ใน UTF-8 สามารถแทนได้ด้วยครึ่งไบต์

Prefix-free code และต้นไม้ Huffman

  • เพื่อให้การถอดรหัสไม่กำกวม รหัสคำใด ๆ ต้องไม่เป็น คำนำหน้า ของรหัสคำอื่น
    • ตัวอย่างเช่น ใน aaabc หากกำหนด a = 1, b = 10, c = 01 ค่า 101 อาจตีความเป็น ac หรือ ba ก็ได้
  • prefix-free code สามารถสร้างเป็นต้นไม้ทวิภาคแบบสมบูรณ์ได้
    • วางค่าทั้งหมดไว้ที่ใบของต้นไม้
    • กำกับเส้นเชื่อมซ้ายเป็น 1 และขวาเป็น 0
    • เส้นทางจากรากไปยังใบจะกลายเป็นรหัสคำของค่านั้น
  • ต้นไม้ Huffman ถูกสร้างโดยค่อย ๆ รวม ค่าที่มีความถี่ต่ำกว่า จากด้านล่างขึ้นมา
    • สร้างโหนดของแต่ละอักขระพร้อม weight ซึ่งคือจำนวนครั้งที่ปรากฏ
    • นำสองโหนดที่มี weight ต่ำสุดมารวมเป็นต้นไม้เดียว
    • weight ของต้นไม้ใหม่คือผลรวมของ weight ของทั้งสองโหนด
    • ทำซ้ำจนเหลือต้นไม้เพียงต้นเดียว
  • กระบวนการนี้ทำให้ค่าที่ปรากฏบ่อยกว่าอยู่ใกล้รากมากขึ้นและได้รหัสคำที่สั้นกว่า

โครงสร้างตัวเข้ารหัสใน Haskell

  • ชนิดข้อมูลหลักของการติดตั้งคือ Bit, Code, FreqMap, CodeMap, Weight, HTree
    • Bit คือ One หรือ Zero
    • Code คือ [Bit]
    • FreqMap คือ Map Char Int สำหรับเก็บจำนวนครั้งที่อักขระแต่ละตัวปรากฏ
    • CodeMap คือ Map Char Code สำหรับเก็บรหัสคำของอักขระแต่ละตัว
    • HTree คือ Leaf Weight Char หรือ Fork Weight HTree HTree
  • HTree ถูกทำให้เปรียบเทียบตาม weight ได้ เพื่อให้การจัดเรียงและแทรกระหว่างการสร้างต้นไม้ง่ายขึ้น
  • countFrequency ใช้คำนวณจำนวนครั้งที่อักขระแต่ละตัวปรากฏในสตริง
  • buildTree จะแปลง FreqMap เป็นรายการใบ จากนั้นเรียงลำดับและรวมสองโหนดที่เล็กที่สุดซ้ำ ๆ เพื่อสร้าง ต้นไม้ Huffman
  • buildCodes จะเดินต้นไม้และต่อ One ทางซ้าย Zero ทางขวาเพื่อสร้างรหัสคำของอักขระแต่ละตัว
  • encode :: FreqMap -> String -> [Bit] จะสร้างต้นไม้และ code map จาก FreqMap แล้วแทนที่อักขระแต่ละตัวในสตริงอินพุตด้วยรหัสคำเพื่อสร้างรายการบิต

การประมวลผลแบบค่อยเป็นค่อยไปด้วย lazy evaluation

  • การแปลงหลักของการเข้ารหัสคือ concatMap codeFor str
    • ในเชิงแนวคิดคือแปลง [Char] เป็น [[Bit]] แล้ว flatten กลับเป็น [Bit]
    • ด้วย lazy evaluation ของ Haskell มันจึงไม่ทำงานแบบเข้ารหัสอินพุตทั้งหมดก่อนแล้วค่อยรวมทีเดียว
  • ลิสต์ขนาดเล็กจะถูกประมวลผลจากซ้ายไปขวาและ flatten ลงในลิสต์ผลลัพธ์ขนาดใหญ่
    • tail ของลิสต์ผลลัพธ์จะยังคงเป็น thunk ที่ยังไม่ถูกประเมิน
    • ส่วนถัดไปจะถูกคำนวณเมื่อมีการร้องขอค่าที่จำเป็น
  • ตัวถอดรหัสก็สร้างผลลัพธ์แบบค่อยเป็นค่อยไปในลักษณะเดียวกัน
    • decode :: FreqMap -> [Bit] -> String จะเดินซ้ายหรือขวาในต้นไม้ตามค่าบิต
    • เมื่อถึงใบก็จะส่งออกอักขระและเริ่มใหม่จากราก
    • ทำซ้ำจนกว่าจำนวนอักขระที่ถอดรหัสได้ทั้งหมดจะเท่ากับ weight ของต้นไม้ Huffman
  • ตัวถอดรหัสหยุดโดยอิง จำนวนอักขระ ไม่ใช่จุดสิ้นสุดของรายการบิตอินพุต
    • เพราะในขั้นตอน serialization มีการเติมบิตแพดด้านท้ายเพื่อให้จัดแนวเป็นระดับไบต์
  • ฟังก์ชัน go เมื่อถึงใบจะคืนลิสต์ที่รู้ head แล้วพร้อมกับการเรียกซ้ำที่อยู่ใน tail จึงสามารถประเมินผลลัพธ์ได้ก่อนที่การเรียกซ้ำทั้งหมดจะเสร็จสิ้น

การจัดการไฟล์ไบนารีและการทำ serialization

  • ข้อมูลไบนารีสามารถมองได้ว่าเป็นการซ้ำกันของหนึ่งใน 256 ค่าไบต์ที่เป็นไปได้
  • Data.ByteString.Char8 ช่วยให้จัดการ ByteString ด้วยการดำเนินการแบบ Char ได้ โดย Char ทุกตัวจะถูกตัดให้เหลือ 8 บิต
    • คุณสมบัตินี้ทำให้สามารถนำตัวเข้ารหัสสำหรับข้อความมาใช้กับ ข้อมูลไบนารี ได้โดยแทบไม่ต้องแก้มาก
  • ในไฟล์บีบอัดจะเก็บ FreqMap ที่จำเป็นต่อการถอดรหัสไว้ก่อน แล้วตามด้วยลำดับบิตที่เข้ารหัสแล้ว
  • serializeFreqMap จะบันทึกตารางความถี่ในรูปแบบดังนี้
    • ความยาวของแมปถูกเก็บเป็น Word8 แต่ลบ 1 ก่อนเก็บเพื่อชดเชยช่วงค่าที่แทนได้
    • แต่ละรายการจะเก็บคีย์เป็น Word8 และค่า frequency เป็นจำนวนเต็ม 64 บิตแบบ big-endian
  • serialize ใช้ Put monad ของแพ็กเกจ binary เพื่อสร้าง ByteString
    • อ่านบิตทีละตัวเพื่อเติมหนึ่งไบต์ให้ครบ
    • เมื่อครบ 8 บิตก็เขียนด้วย putWord8
    • ไบต์สุดท้ายจะเติมพื้นที่ที่เหลือด้วย Zero

การทำ deserialization และกลยุทธ์หน่วยความจำคงที่

  • deserializeFreqMap ใช้ Data.Binary.Get เพื่ออ่านตารางความถี่ที่ถูก serialize ไว้
    • เริ่มจากอ่านความยาวแล้วบวก 1 เพื่อคำนวณจำนวนรายการจริง
    • จากนั้นอ่านคีย์ Word8 และค่า frequency 64 บิตของแต่ละรายการเพื่อกู้คืน FreqMap
  • อินพุตส่วนที่เหลือจะไม่ถูกประมวลผลด้วย Get ทั้งหมด แต่ดึงส่วนหลัง offset ออกจาก ByteString แล้วแปลงเป็นรายการบิตแทน
  • deserialize จะคืนค่า (FreqMap, [Bit]) โดย [Bit] เป็น ลิสต์แบบ lazy ที่ไม่ได้ถูกคำนวณทั้งหมดในทันที
    • จึงควรหลีกเลี่ยงการขอความยาวของลิสต์นี้ เพราะจะบังคับให้ต้องประเมินทั้งลิสต์
  • เหตุผลที่ไม่ใช้ Get กับอินพุตทั้งหมดคือ bind ของ monad จะบังคับลำดับการประมวลผล
    • ทำให้โครงสร้างกลายเป็นว่าต้องประมวลผลอินพุตทั้งหมดให้เสร็จก่อนจึงจะคืนลิสต์ได้
  • กลยุทธ์หน่วยความจำคงที่คือประเมินอินพุตทีละส่วนเล็กถัดไปทุกครั้งที่ต้องเขียนบิตเอาต์พุต
    • ByteString บางส่วนจะถูกประเมินและชิ้นไฟล์ส่วนนั้นจะถูกอ่าน
    • เอาต์พุตที่ประมวลผลแล้วจะถูกเขียนลงไฟล์
    • ชิ้นอินพุตและรายการบิตที่ไม่ถูกอ้างถึงแล้วสามารถถูกเก็บกวาดโดย garbage collector ได้
  • FreqMap มีได้มากสุด 256 รายการในกรณีของไบต์ จึงมี overhead ขนาดคงที่

CLI สำหรับบีบอัดและคลายบีบอัดไฟล์

  • compress จะอ่านไฟล์อินพุตสองรอบ
    • รอบแรกสร้าง FreqMap
    • รอบที่สองเข้ารหัสข้อมูลด้วย FreqMap นั้น
  • หากอ่านไฟล์เพียงครั้งเดียวแล้วส่ง reference เดิมให้ encode ก็จะต้องเก็บ reference ถึงไฟล์อินพุตทั้งหมดไว้แม้หลังสร้างตารางความถี่เสร็จแล้ว ทำให้ต้องถือไฟล์ทั้งก้อนไว้ในหน่วยความจำ
  • วิธีอ่านสองรอบช่วยให้ทั้งตอนสร้างตารางความถี่และตอนเข้ารหัสสามารถปล่อยหน่วยความจำของส่วนที่ประมวลผลไปแล้วได้ระหว่างทาง
  • decompress จะอ่านไฟล์บีบอัด ใช้ deserialize เพื่อดึง FreqMap กับรายการบิตออกมา แล้วบันทึกผล decode ลงไฟล์
  • CLI รับอาร์กิวเมนต์ดังนี้
    • compress FILE FILE
    • decompress FILE FILE
  • ใช้เฉพาะแพ็กเกจที่มาพร้อมกับ GHC จึงคอมไพล์ได้ด้วย ghc -O2 Main.hs -o main โดยไม่ต้องใช้ cabal

ผลการรันและการใช้หน่วยความจำ

  • ในการทดสอบกับไฟล์ข้อความ War and Peace ของ Tolstoy หลังบีบอัดและคลายบีบอัดแล้ว ผล diff ตรงกัน
    • ต้นฉบับ WarAndPeace.txt: 3.2M
    • ไฟล์บีบอัด: 1.9M
    • ไฟล์ที่คลายบีบอัดแล้ว: 3.2M
    • ขนาดลดลงประมาณ 40%
  • การบีบอัดและคลายบีบอัดทำงานได้กับไฟล์ไบนารีขนาดใหญ่ ghcup เช่นกัน
    • ต้นฉบับ ghcup: 106M
    • ไฟล์บีบอัด: 84M
    • ไฟล์ที่คลายบีบอัดแล้ว: 106M
    • เวลาในการบีบอัดประมาณ 15.173 วินาที และเวลาในการคลายบีบอัดประมาณ 14.555 วินาที
  • ตาม +RTS -s ค่า maximum resident set size ระหว่างประมวลผล ghcup ต่ำกว่า 300KB
  • ทั้งสองโปรเซสใช้หน่วยความจำต่ำกว่า 10MB ในการทำงาน
  • จุดที่ใช้เวลาอยู่สามารถดูได้จาก โปรไฟล์ แยกต่างหาก

จุดที่ยังปรับปรุงได้เพิ่มเติม

  • เป้าหมายของการติดตั้งนี้คือยูทิลิตีบีบอัดที่เรียบง่ายและชัดเจนที่สุดเท่าที่ทำได้ และหากต้องการประสิทธิภาพที่สูงขึ้นก็จำเป็นต้องเพิ่มความซับซ้อนของการติดตั้ง
  • แนวทางที่อาจปรับปรุงได้มีดังนี้
    • Multithreading: ถอดรหัสช่วงต่าง ๆ ของไฟล์แบบขนาน แต่เนื่องจากไม่สามารถรู้ขอบเขตรหัสคำจากตำแหน่งสุ่มได้ จึงต้องเพิ่มตารางขอบเขตช่วงและขนาดที่คาดว่าจะถอดรหัสได้ไว้ด้านหน้าของไฟล์บีบอัด
    • Single-pass encoding: เริ่มจากตารางความถี่ตั้งต้นที่ทุกไบต์มีความถี่ 1 แล้วเมื่อพบไบต์แต่ละตัวก็เข้ารหัสก่อน จากนั้นค่อยอัปเดตตารางความถี่
    • Canonical Huffman codes: แทนที่จะไล่ต้นไม้เพื่อถอดรหัสใน O(log n) สามารถใช้รหัสเป็นดัชนีของเวกเตอร์เพื่อหวังการเข้าถึงแบบ O(1) ได้ โดยดูรายละเอียดเพิ่มเติมได้ที่ Canonical Huffman code
    • การสร้างรหัสที่เร็วขึ้น: ในการเข้ารหัสแบบ single-pass จำเป็นต้องสร้าง CodeMap ให้เร็วขึ้นมาก และยังมีวิธีสร้างรหัสคำที่เร็วกว่าโดยไม่ต้องสร้างต้นไม้
  • ในอนาคต หากใช้ LZ77 ซึ่งเป็นวิธีพจนานุกรมแบบปรับตัวได้ร่วมกับรหัส Huffman ก็จะสามารถสร้าง gzip ได้

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-07-06
ความคิดเห็นบน Hacker News

  • สำหรับงานนี้มี อัลกอริทึมแบบทำในที่เดิมโดยใช้อาร์เรย์ ที่ช่วยลดการจัดสรรทรีและการไล่ตามพอยน์เตอร์
    ตอนเรียนแนวทางแบบใช้ทรีในมหาวิทยาลัย ผมไม่รู้ว่ามีวิธีอื่นอยู่ และสงสัยว่าคนอื่น ๆ ก็เป็นแบบนั้นหรือเปล่า
    วิธีแบบทรีนั้นเข้าใจได้ง่ายและช่วยให้เห็นภาพ แต่สถานการณ์ที่การบีบอัดสำคัญที่สุดมักเป็นตอนที่มีข้อมูลจำนวนมากและอยากให้ทำงานเร็ว ดังนั้นการจัดการด้วยอาร์เรย์แบบ in-place อาจสมเหตุสมผลกว่า
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • โดยทั่วไป On the Implementation of Minimum Redundancy Prefix Codes ของ Moffat และ Turpin ก็น่าอ่านเช่นกัน
      Charles Bloom แนะนำอย่างหนักแน่น และภายหลังก็เขียนคำอธิบายเพิ่มเติมไว้ด้วย
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • มาตรฐาน JPEG ITU T.81 (1992) อธิบายอัลกอริทึมนี้ไว้เป็นผังงาน ดังนั้นความรู้เกี่ยวกับ Huffman แบบใช้อาร์เรย์น่าจะเป็นที่รู้จักกันในระดับหนึ่งมาตั้งแต่ยุค 80 แล้ว
    • มีการกล่าวถึงไว้ท้ายบทความ และปล่อยไว้เป็นแบบฝึกหัดสำหรับผู้อ่าน
    • ประโยค “สงสัยว่ามันเป็นแบบนั้นกับพวกคุณกี่คนด้วย” ฟังดูเหมือน list comprehension

  • คำกล่าวที่ว่า “ต้องทำให้ไม่มี code word ใดเป็น prefix ของ code word อื่น จึงจะไม่กำกวม” นั้นพูดอย่างเคร่งครัดแล้วไม่ถูกต้อง
    สิ่งที่เรียกว่า รหัสที่ถอดรหัสได้อย่างเอกเทศ นั้นไม่กำกวม และเป็นเซตที่กว้างกว่ารหัส prefix
    ตัวอย่างง่าย ๆ คือรหัสที่กลับด้านจากรหัส prefix ถ้าใช้ตัวอย่างในบทความก็จะเป็น a 1, b 00, c 10
    แม้รหัสของ a จะเป็น prefix ของรหัส c แต่ถ้าประมวลผลลำดับรหัสย้อนกลับ ก็ยังถอดรหัสได้โดยไม่กำกวมอยู่ดี คงน่าสนใจถ้าได้เห็นรหัสที่ถอดรหัสได้อย่างเอกเทศซึ่งไม่ใช่ทั้งรหัส prefix และไม่ใช่แบบย้อนกลับของมัน

    • ถ้าประกอบรหัส prefix กับ รหัส suffix เข้าด้วยกัน ก็สามารถสร้างรหัสแบบนั้นได้โดยไม่ไร้ประสิทธิภาพเกินจำเป็น
      ให้ A 0, B 01, C 11 แล้วกำหนดต่อเป็น a A 0, b BA 010, c BB 0101, d BC 0111, e C 11 ก็จะได้ {a=0,b=010,c=0101,d=0111,e=11}
      เห็นได้ชัดว่าถอดรหัสได้อย่างเอกเทศ เพราะถอดรหัสจากด้านหลังแบบเอกเทศเช่น 0->A แล้วถอดรหัสอีกครั้งจากด้านหน้าแบบเอกเทศเช่น A->a ก็พอ
      ในแง่ความยาว มันเท่ากับรหัส prefix ที่เหมาะที่สุด {a=0,b=110,c=1110,d=1111,e=10} ดังนั้นจึงเป็นหนึ่งในหลายรหัสที่เหมาะที่สุดสำหรับการแจกแจงความน่าจะเป็นเดียวกัน
      ขณะเดียวกัน เพราะมี a=0, b=010 จึงไม่ใช่ทั้งรหัส prefix และรหัส suffix จริง ๆ แล้วโดยทั่วไปไม่สามารถถอดรหัสแบบค่อยเป็นค่อยไปได้จากทิศทางใดเลย และในการแยกแยะ cee...ee? กับ bee...ee?, ?cc...cca กับ ?cc...ccb อาจต้องมองล่วงหน้าอย่างไม่มีที่สิ้นสุดแม้เพียงเพื่อระบุสัญลักษณ์เดียว
      ผมไม่รู้ว่าถ้านำรหัส prefix ที่เหมาะที่สุดโดยอิสระกับรหัส suffix ที่เหมาะที่สุดโดยอิสระมาประกอบกัน จะยังคงความเหมาะที่สุดเสมอหรือไม่ แต่ในกรณีที่ง่ายที่สุดที่นึกออก ยกเว้นรหัส 1:1 แบบเสื่อมสภาพ มันทำงานได้ดี
    • เป็นปัญหาที่น่าสนใจกว่าที่คิด คำตอบแบบยียวนก่อนก็คือตัวอย่างอย่าง a 101, b 1 เป็นไปได้
      แต่นั่นเป็นรหัสที่แย่ เพราะกำหนดเป็น a=1, b=0 เสมอย่อมดีกว่า
      อสมการ Kraft บอกเซตของความยาวรหัสที่สามารถทำให้ถอดรหัสได้อย่างเอกเทศ และการเข้ารหัส Huffman ก็ทำให้ได้ทุกเซตเช่นนั้น ดังนั้นถ้ากำลังเข้ารหัสสัญลักษณ์ ก็ไม่มีเหตุผลให้ใช้รหัสที่ไม่ใช่ prefix เว้นแต่จะเปลี่ยนไปใช้วิธีอื่นอย่าง ANS หรือ arithmetic coding
      อย่างไรก็ดี ผมไม่รู้ว่ามีรหัสที่ถอดรหัสได้อย่างเอกเทศ ซึ่งมีเซตความยาวเดียวกับรหัส Huffman ที่เหมาะที่สุด แต่ไม่ใช่ทั้งรหัส prefix และไม่ใช่รหัส suffix ซึ่งเป็นแบบกลับด้านของมันหรือไม่
      ถ้ามีเวลา ผมน่าจะดู https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm แล้วลองหา counterexample แบบ brute force หรือคิดบทพิสูจน์จากวิธีทำงานของอัลกอริทึม
    • เป็นตัวอย่างแปลก ๆ แต่ a 1, b 101 จะเป็นอย่างไรนะ
      มันไม่ใช่ทั้ง prefix-free และ suffix-free แต่ทุกครั้งที่มี 0 ปรากฏ ก็สอดคล้องกับการที่มี b ปรากฏ
      แน่นอนว่ามันไม่มีประสิทธิภาพอย่างชัดเจน ดังนั้นสุดท้ายสิ่งที่สงสัยคือมี รหัสที่เหมาะที่สุด ที่ไม่ใช่ทั้ง prefix-free และ suffix-free หรือไม่
      ลองค้นดูแล้ว https://blog.plover.com/CS/udcodes.html ยกตัวอย่างรหัสที่ถอดรหัสได้อย่างเอกเทศว่า a 0011, b 011, c 11, d 1110
      ความสัมพันธ์แบบ prefix มีเพียงกรณีเดียวคือ c เป็น prefix ของ d จึง “แทบจะ” prefix-free ถ้าข้อความเริ่มด้วย 1 ก็น่าจะหา 0 ตัวแรก แล้วดูว่าจำนวน 1 ก่อนหน้านั้นเป็นเลขคี่หรือเลขคู่ จึงพอเข้าใจได้ว่าถอดรหัสได้อย่างเอกเทศ
      แต่ผมจำไม่ได้แล้วว่าจะพิสูจน์อย่างไรว่ามันเหมาะที่สุดสำหรับการแจกแจงความน่าจะเป็นแบบใด เพราะความรู้ด้านวิทยาการรหัสของผมขึ้นสนิมไปมาก
    • น่าสนใจ แต่เหตุผลที่มักไม่ใช้กันน่าจะเป็นเพราะอาจต้องอ่านบิตสตริงที่ยาวมากจนกว่าจะเจอ บิตที่คลี่คลายความกำกวม
      เช่นในกรณี 100000000000000001 ถ้าจะรู้ว่ารหัสแรกคือ a หรือ c ก็ต้องอ่านไปจนถึงจุดที่ศูนย์ทั้งหมดสิ้นสุด

  • สงสัยว่ามีบทเรียนคล้าย ๆ กันที่ค่อย ๆ เขียนโปรแกรม Haskell แบบบทความนี้ แต่ครอบคลุมฟีเจอร์ขั้นสูงกว่าอย่าง monad transformer หรือ lens ไหม

    • แนะนำหนังสือ Haskell in Depth บทที่ 6 ว่าด้วย monad transformer ส่วน lens อยู่ในบทที่ 3 และ 14
      ยังครอบคลุมฟีเจอร์ขั้นสูงอื่น ๆ เช่น Template Haskell, concurrency และมีบทเกี่ยวกับการใช้งานฐานข้อมูล SQL ใน Haskell ด้วย
    • https://github.com/turion/rhine-koans ก็น่าดู
      เป็นบทเรียนสำหรับ ไลบรารี FRP Rhine และมีคอมเมนต์กับเทสต์เขียนไว้ดี

  • ในคอร์ส Functional Programming ที่ใช้ Scala ของ Coursera ก็มีโจทย์เกี่ยวกับ Huffman coding ที่ค่อนข้างคล้ายกัน และมีตัวตรวจให้คะแนนอัตโนมัติด้วย จึงเหมาะสำหรับคนที่อยากลองแก้เอง
    https://www.coursera.org/learn/scala-functional-programming?...

  • ครั้งสุดท้ายที่ใช้ Huffman code คือใน macroprogram ของ โปรเซสเซอร์ MICMAC หรือก็คือเพื่อรันข้อความ assembly ด้วยจำนวน microcycle และ microinstruction น้อยที่สุด
    เริ่มจาก histogram ของ macroinstruction ที่ถูกเรียกใช้ และเท่าที่จำได้ ตอนแรกเขียน interpreter ด้วย C เพื่อคอยนับว่าแต่ละคำสั่งถูกเรียกใช้กี่ครั้ง
    จากนั้นจึงสร้างโปรแกรม microcode แบบถอดรหัสทีละขั้นที่ implement macro operation ของ ISA ที่จำเป็นทั้งหมด ISA ของ macroinstruction ที่สร้างขึ้นน่าจะเป็นแบบระดับบิต ไม่ใช่ byte-oriented
    ในโลกจริงมันคงช้าและใช้งานไม่สะดวก แต่ข้อดีของ Huffman code คือสามารถปรับความลึกของ prefix ตามการกระจายของค่าได้ จึงไม่จำเป็นต้องสร้าง code ที่เอนเอียงไปด้านใดด้านหนึ่งเพราะ prefix 1 บิต
    นอกจากนี้ microprogram ยังเป็นโมเดลโปรเซสเซอร์ pipeline แบบไม่ใช่ superscalar จึงต้องจัดการ branch prediction ด้วย หากทำนาย branch ผิด ก็จะเสีย cycle ไปกับ pipeline stall ระหว่างที่ branch ที่ถูกต้องถูกส่งต่อไปข้างหน้า

  • https://rosettacode.org/wiki/Huffman_coding

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

    • ความเร็วของ Haskell แข่งกับภาษาเชิงระบบได้ แต่ควรจำไว้ว่าจุดแข็งหลักคือ ความง่ายในการทำ abstraction
      แก่นสำคัญคือการประกอบหลายส่วนให้เป็นโปรแกรมที่สอดคล้องและจัดระเบียบดีได้ง่าย เรื่องนี้สำคัญกับทั้งโปรแกรม ไม่ใช่แค่ลูปแน่น ๆ เท่านั้น
      Haskell มี FFI ที่ดี ดังนั้นส่วนที่โดยเนื้อแท้แล้วต้องการการปรับแต่งแบบ imperative ก็สามารถลงไปใช้ภาษาที่ไม่มี garbage collection ได้ ถ้าห่อส่วนนั้นเป็นไลบรารีที่มี type ดี ๆ โค้ด Haskell ที่ type ตรงกันตรงไหนก็สามารถใช้ประสิทธิภาพดิบระดับนั้นได้
      ตอนทำแอปพลิเคชัน Haskell ประสิทธิภาพสูงที่ Meta ก็ทำแบบนั้น คือเขียนโปรแกรม Haskell ที่สวย ใหญ่ และเร็ว แต่ใส่คอมโพเนนต์ C++ ในบางส่วนที่เฉพาะทาง เวลา 99% ใช้ไปกับฝั่ง Haskell เพื่อประกอบให้เป็นแอปพลิเคชันที่มีประโยชน์มากขึ้น
    • สำหรับงาน backend, web, CLI ทั่วไป ผมพอใจกับประสิทธิภาพของ Haskell แต่พอเขียนโค้ดที่เน้นประสิทธิภาพจริง ๆ จะลงไปใช้ Rust
      ถึงอย่างนั้น Haskell ก็ไม่ถือว่าช้า ตัวอย่างเช่นโปรแกรมเล็ก ๆ ที่นับจำนวนบิต 1 ในไฟล์
      ถ้าคอมไพล์ด้วย -msse4.2 ก็ใช้คำสั่งฮาร์ดแวร์ popcount ได้ถูกต้อง และประมวลผลไฟล์อินพุต 1GB ใน 0m0,090s ใช้ heap เป็น 0 เมื่อปัดเป็นหน่วย MB
      ถ้าคอมไพล์โดยไม่มี -msse4.2 จะใช้เวลา 0m0,293s
      การคำนวณเมทริกซ์ผมยังไม่ได้ลองเอง แต่ถ้าเป็นจุดเริ่มต้นคงไปดู repa, accelerate, massiv
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • ที่ ZuriHac ผมได้เจอ Sam Derbyshire และได้ยินมาว่างานสถาปัตยกรรมยาก ๆ ทั้งหมดสำหรับ การรองรับ SIMD เสร็จแล้ว
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      อาจจะเข้า GHC 9.12 ก็ได้ แต่จะมุ่งเป้าแค่เวกเตอร์ 128 บิต และถ้าไม่มีคนอื่นมาช่วย contribute ก็น่าจะเน้นการคำนวณเลขทศนิยมเป็นหลัก
      แพตช์อยู่ที่นี่
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • ในความเป็นจริง ไม่ว่าจะเป็นภาษาใดรวมถึง C โค้ดที่คอมไพเลอร์ optimize ให้ก็ไม่มีทางเร็วเท่ากับ โค้ดที่ปรับแต่งด้วยมือ ของไลบรารีอย่าง BLAS
      เมื่อถึงระดับหนึ่ง การเลือกภาษา host ก็ไม่ได้สำคัญมากนัก เพราะถ้าจริงจังกับความเร็วจริง ๆ สุดท้ายก็จะโยนการคำนวณออกไปให้ภายนอกอยู่ดี
      เหตุผลเดียวกันนี้ทำให้โค้ด AI ซึ่งมีแนวโน้มจะเป็นหนึ่งในงานที่ใช้ทรัพยากรคำนวณมากที่สุดในโลก สามารถเขียนด้วย Python ได้ ยกเว้นไลบรารีคำนวณระดับต่ำ
      ถ้าตอบตรง ๆ คอมไพเลอร์ GHC นั้นดีมาก โค้ดระดับสูงทำงานได้ค่อนข้างดี และในแอปพลิเคชันจริงส่วนใหญ่ คอขวดด้านประสิทธิภาพไม่ใช่เรื่องการคำนวณความกว้างเดี่ยวเทียบกับ SIMD แต่เป็นปัญหาด้านสถาปัตยกรรม “ความเป็นมิตรต่อเชิงกำกับด้านสถาปัตยกรรม” ของ Haskell ค่อนข้างได้เปรียบ
      ผมคิดว่า GHC มีหรือกำลังจะมีการรองรับ SIMD แต่คงไม่เอาเรื่องนั้นเป็นจุดโฟกัสตอนประเมินประสิทธิภาพ
      ผมคงไม่เขียนอัลกอริทึมคูณเมทริกซ์เองด้วย Haskell แต่ถ้าจริงจังเรื่องความเร็ว ผมก็จะไม่เขียนเองด้วย Rust หรือ C เช่นกัน
      หลายคนมักใช้การคำนวณเชิงตัวเลขเป็นตัวชี้วัดประสิทธิภาพ แต่ในความเป็นจริงมีคนน้อยมากที่คอขวดไปอยู่ตรงนั้น และถ้ามันเป็นคอขวดจริง ๆ การใช้ภาษาระดับสูงภาษาไหนก็ไม่ค่อยสำคัญนัก
    • Haskell เปล่งประกายจริง ๆ เมื่อคุณอยากเขียน โค้ดเชิงประกาศ ระดับสูง
      ประสิทธิภาพของสไตล์แบบนี้โดยทั่วไปเพียงพอสำหรับงาน CLI หรือ backend เว็บ มีเครื่องมือให้เขียนโค้ดระดับต่ำที่ค่อนข้างเร็วด้วย แต่ค่อนข้างกระด้าง ดังนั้นถ้าอยากใช้แค่นั้นอย่างเดียว ก็น่าจะไม่ใช่เครื่องมือที่ดีที่สุด
      อย่างไรก็ตาม ถ้ามี hotspot กระจุกตัวอยู่ไม่กี่จุดที่ต้อง optimize ก็ถือว่าใช้ได้ดีทีเดียว
      เครื่องมือ profiling CPU ดี ทำให้การหาและ optimize hotspot ของ CPU ค่อนข้างสบาย ในทางกลับกัน การตามรอย memory leak แปลก ๆ ที่เกิดได้ง่ายขึ้นเพราะ lazy evaluation อาจชวนหงุดหงิดมาก
      ดูผลจาก benchmarks game แล้ว implementation Haskell ที่เร็วที่สุดส่วนใหญ่โดยทั่วไปช้ากว่าเวอร์ชัน C ที่เร็วที่สุดประมาณ 2–5 เท่า และเขียนในสไตล์ imperative มาก
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • ตารางในส่วน “Creating prefix-free codes” ดูเหมือนจะมีพิมพ์ผิด D ควรเป็น 0010 ไม่ใช่ 0110

    • เลยนั่งงงอยู่นานว่า 0110 จะไม่กำกวมได้ยังไง ตอนนี้เข้าใจแล้ว

  • สงสัยว่าบนเสื้อของผู้หญิงในภาพคืออะไร
    ลิงก์โดยตรง: https://lazamar.github.io/images/data-compressor.svg