การบีบอัดข้อมูลแบบไม่สูญเสียข้อมูลทำงานอย่างไร | นิตยสารควอนตั้ม

ด้วยข้อมูลมากกว่า 9 พันล้านกิกะไบต์ที่เดินทางบนอินเทอร์เน็ตทุกวัน นักวิจัยจึงมองหาวิธีใหม่ๆ ในการบีบอัดข้อมูลให้เป็นแพ็คเกจขนาดเล็กลงอย่างต่อเนื่อง เทคนิคที่ทันสมัยมุ่งเน้นไปที่วิธีการที่สูญเสีย ซึ่งบรรลุการบีบอัดโดยเจตนา "สูญเสีย" ข้อมูลจากการส่งสัญญาณ ตัวอย่างเช่น Google เพิ่งเปิดตัวกลยุทธ์การสูญเสียโดยคอมพิวเตอร์ที่ส่งจะทิ้งรายละเอียดจากรูปภาพ และคอมพิวเตอร์ที่รับข้อมูลจะใช้ปัญญาประดิษฐ์เพื่อคาดเดาส่วนที่ขาดหายไป แม้แต่ Netflix ก็ใช้วิธีลดคุณภาพวิดีโอลงทุกครั้งที่บริษัทตรวจพบว่าผู้ใช้รับชมบนอุปกรณ์ที่มีความละเอียดต่ำ

ในทางตรงกันข้าม การวิจัยน้อยมากกำลังดำเนินการตามกลยุทธ์แบบไม่สูญเสีย ซึ่งการส่งสัญญาณมีขนาดเล็กลง แต่ไม่มีเนื้อหาใดถูกเสียสละ เหตุผล? วิธีการที่ไม่สูญเสียนั้นมีประสิทธิภาพอย่างน่าทึ่งอยู่แล้ว พวกเขาขับเคลื่อนทุกอย่างตั้งแต่มาตรฐานภาพ JPEG ไปจนถึงยูทิลิตี้ซอฟต์แวร์ PKZip ที่แพร่หลาย และทั้งหมดนี้เป็นเพราะนักศึกษาระดับบัณฑิตศึกษาคนหนึ่งที่มองหาทางออกจากการสอบปลายภาคที่ยากลำบาก

เมื่อเจ็ดสิบปีที่แล้ว ศาสตราจารย์สถาบันเทคโนโลยีแมสซาชูเซตส์ชื่อ Robert Fano ได้เสนอทางเลือกให้นักเรียนในชั้นเรียนทฤษฎีสารสนเทศของเขา: ทำข้อสอบปลายภาคแบบดั้งเดิม หรือปรับปรุงอัลกอริทึมชั้นนำสำหรับการบีบอัดข้อมูล Fano อาจหรืออาจไม่ได้แจ้งนักเรียนว่าเขาเป็นผู้เขียนอัลกอริทึมที่มีอยู่ หรือว่าเขากำลังค้นหาวิธีปรับปรุงมาหลายปีแล้ว สิ่งที่เรารู้ก็คือ Fano เสนอความท้าทายต่อไปนี้ให้กับนักเรียนของเขา

พิจารณาข้อความที่ประกอบด้วยตัวอักษร ตัวเลข และเครื่องหมายวรรคตอน วิธีที่ตรงไปตรงมาในการเข้ารหัสข้อความดังกล่าวคือกำหนดเลขฐานสองที่ไม่ซ้ำกันให้กับอักขระแต่ละตัว ตัวอย่างเช่น คอมพิวเตอร์อาจแทนตัวอักษร A เป็น 01000001 และเครื่องหมายอัศเจรีย์เป็น 00100001 ผลลัพธ์ที่ได้คือรหัสที่แยกวิเคราะห์ได้ง่าย - ทุก ๆ แปดหลักหรือบิตจะสอดคล้องกับอักขระเฉพาะหนึ่งตัว - แต่ไม่มีประสิทธิภาพอย่างน่ากลัวเพราะมีตัวเลขเดียวกัน ของเลขฐานสองใช้สำหรับทั้งรายการทั่วไปและรายการผิดปกติ แนวทางที่ดีกว่าคือรหัสมอร์ส ซึ่งตัวอักษร E ที่ใช้บ่อยจะแสดงด้วยจุดเพียงจุดเดียว ในขณะที่ Q ที่ใช้กันน้อยกว่าต้องใช้เส้นประที่ยาวกว่าและลำบากกว่า

แต่รหัสมอร์สก็ไม่มีประสิทธิภาพเช่นกัน แน่นอน บางรหัสสั้นและบางรหัสยาว แต่เนื่องจากความยาวของรหัสแตกต่างกันไป ข้อความในรหัสมอร์สจึงไม่สามารถเข้าใจได้ เว้นแต่ข้อความเหล่านั้นจะรวมช่วงเวลาสั้นๆ ของความเงียบระหว่างการส่งอักขระแต่ละครั้ง ผู้รับจะไม่มีทางแยกแยะข้อความมอร์ส dash dot-dash-dot dot-dot dash dot (“trite”) จาก dash dot-dash-dot dot-dot-dash dot (“จริง”) ).

Fano ได้แก้ไขปัญหาส่วนนี้แล้ว เขาตระหนักว่าเขาสามารถใช้รหัสที่มีความยาวต่างกันได้โดยไม่จำเป็นต้องมีช่องว่างราคาแพง ตราบใดที่เขาไม่เคยใช้รูปแบบตัวเลขเดียวกันทั้งรหัสที่สมบูรณ์และจุดเริ่มต้นของรหัสอื่น ตัวอย่างเช่น หากตัวอักษร S เป็นเรื่องธรรมดามากในข้อความเฉพาะที่ Fano กำหนดรหัสที่สั้นมากเป็น 01 จะไม่มีตัวอักษรอื่นใดในข้อความนั้นถูกเข้ารหัสด้วยตัวอักษรใดๆ ที่ขึ้นต้นด้วย 01; รหัสเช่น 010, 011 หรือ 0101 จะถูกห้ามทั้งหมด ด้วยเหตุนี้ ข้อความรหัสจึงสามารถอ่านจากซ้ายไปขวาได้โดยไม่มีความคลุมเครือใดๆ ตัวอย่างเช่น ตัวอักษร S กำหนดเป็น 01 ตัวอักษร A กำหนดเป็น 000 ตัวอักษร M กำหนดเป็น 001 และตัวอักษร L กำหนดเป็น 1 จู่ๆ ข้อความ 0100100011 ก็สามารถแปลเป็นคำว่า "เล็ก" ได้ทันที แม้ว่า L จะแทนด้วยหนึ่งตัวก็ตาม หลัก S คูณสองหลัก และตัวอักษรอื่นๆ คูณสาม

ในการกำหนดรหัสจริง Fano ได้สร้างต้นไม้ไบนารีโดยวางตัวอักษรที่จำเป็นแต่ละตัวไว้ที่ส่วนท้ายของกิ่งภาพ จากนั้นรหัสของตัวอักษรแต่ละตัวจะถูกกำหนดโดยเส้นทางจากบนลงล่าง ถ้าพาธแยกไปทางซ้าย Fano จะเพิ่ม 0; กิ่งก้านด้านขวาได้ 1 โครงสร้างของต้นไม้ช่วยให้ Fano หลีกเลี่ยงการทับซ้อนที่ไม่พึงประสงค์เหล่านี้ได้ง่าย: เมื่อ Fano วางตัวอักษรบนต้นไม้ กิ่งก้านนั้นจะสิ้นสุดลง หมายความว่ารหัสในอนาคตไม่สามารถเริ่มต้นในลักษณะเดียวกันได้

เพื่อตัดสินใจว่าตัวอักษรใดจะไปที่ใด Fano สามารถทดสอบทุกรูปแบบที่เป็นไปได้อย่างถี่ถ้วนเพื่อให้ได้ประสิทธิภาพสูงสุด แต่นั่นอาจใช้ไม่ได้จริง ดังนั้น เขาจึงพัฒนาวิธีการประมาณแทน: สำหรับทุกข้อความ เขาจะจัดระเบียบตัวอักษรที่เกี่ยวข้องตามความถี่ จากนั้นจึงกำหนดตัวอักษรให้กับสาขา เพื่อให้ตัวอักษรทางซ้ายในคู่สาขาใดก็ตามถูกใช้ในข้อความโดยคร่าว ๆ ในจำนวนครั้งที่เท่ากันกับ ตัวอักษรด้านขวา ด้วยวิธีนี้ อักขระที่ใช้บ่อยจะลงเอยด้วยสาขาที่สั้นกว่าและมีความหนาแน่นน้อยกว่า ตัวอักษรความถี่สูงจำนวนน้อยจะทำให้ตัวอักษรความถี่ต่ำจำนวนมากสมดุลกันเสมอ

ผลที่ได้คือการบีบอัดที่มีประสิทธิภาพอย่างน่าทึ่ง แต่เป็นเพียงการประมาณเท่านั้น ต้องมีกลยุทธ์การบีบอัดที่ดีกว่า ดังนั้น Fano จึงท้าให้นักเรียนค้นหามัน

Fano สร้างต้นไม้ของเขาจากบนลงล่างโดยรักษาความสมมาตรให้มากที่สุดเท่าที่จะเป็นไปได้ระหว่างกิ่งที่จับคู่กัน David Huffman นักเรียนของเขากลับด้านกระบวนการโดยสร้างต้นไม้ประเภทเดียวกันแต่สร้างจากล่างขึ้นบน ข้อมูลเชิงลึกของ Huffman คือไม่ว่าจะเกิดอะไรขึ้น ในโค้ดที่มีประสิทธิภาพ อักขระทั่วไปอย่างน้อยสองตัวควรมีโค้ดที่ยาวที่สุดสองตัว ดังนั้น Huffman จึงระบุอักขระที่พบน้อยที่สุด XNUMX ตัว จัดกลุ่มเข้าด้วยกันเป็นคู่ที่แยกย่อย จากนั้นทำกระบวนการซ้ำ โดยคราวนี้มองหาอักขระที่พบน้อยที่สุด XNUMX ตัวจากอักขระที่เหลือและคู่ที่เขาเพิ่งสร้าง

พิจารณาข้อความที่แนวทาง Fano สะดุด ใน “ห้องเรียน” O ปรากฏขึ้นสี่ครั้ง และ S/C/H/L/R/M ปรากฏขึ้นหนึ่งครั้ง วิธีการสร้างสมดุลของ Fano เริ่มต้นด้วยการกำหนด O และตัวอักษรอีกตัวหนึ่งให้กับสาขาด้านซ้าย โดยการใช้ตัวอักษรเหล่านั้นทั้งหมดห้าตัวจะสร้างความสมดุลให้กับลักษณะที่ปรากฏห้าตัวของตัวอักษรที่เหลือ ข้อความผลลัพธ์ต้องใช้ 27 บิต

ในทางตรงกันข้าม Huffman เริ่มต้นด้วยตัวอักษรสองตัวที่ไม่ธรรมดา เช่น R และ M และจัดกลุ่มเข้าด้วยกันโดยถือว่าทั้งคู่เหมือนเป็นตัวอักษรเดียว

แผนภูมิความถี่ที่อัปเดตแล้วของเขาเสนอตัวเลือกสี่ตัวเลือก: ตัว O ที่ปรากฏสี่ครั้ง โหนด RM แบบรวมใหม่ที่ใช้งานสองครั้ง และตัวอักษรเดี่ยว S, C, H และ L ฮัฟฟ์แมนเลือกตัวเลือกที่พบบ่อยน้อยที่สุดสองตัวเลือกอีกครั้ง โดยการจับคู่ (พูด) H กับ L.

แผนภูมิจะอัปเดตอีกครั้ง: O ยังคงมีน้ำหนักเท่ากับ 4 ตอนนี้ RM และ HL มีน้ำหนักเท่ากับ 2 และตัวอักษร S และ C แยกกัน Huffman ดำเนินการต่อจากนั้น ในแต่ละขั้นตอนจะจัดกลุ่มตัวเลือกที่ใช้บ่อยน้อยที่สุด XNUMX ตัวเลือก จากนั้นจึงอัปเดตทั้งแผนภูมิต้นไม้และแผนภูมิความถี่

ในที่สุด "ห้องเรียน" กลายเป็น 11101111110000110110000101 ซึ่งตัดทอนวิธีการจากบนลงล่างของ Fano ไปเล็กน้อย

หนึ่งบิตอาจฟังดูไม่มาก แต่การประหยัดเพียงเล็กน้อยก็เพิ่มขึ้นอย่างมหาศาลเมื่อปรับขนาดเป็นพันล้านกิกะไบต์

แท้จริงแล้วแนวทางของ Huffman นั้นมีประสิทธิภาพมากจนทุกวันนี้ กลยุทธ์การบีบอัดแบบไม่สูญเสียข้อมูลเกือบทั้งหมดใช้ข้อมูลเชิงลึกของ Huffman ทั้งหมดหรือบางส่วน ต้องการ PKZip เพื่อบีบอัดเอกสาร Word หรือไม่ ขั้นตอนแรกเกี่ยวข้องกับกลยุทธ์ที่ชาญฉลาดอีกวิธีหนึ่งในการระบุการทำซ้ำและด้วยเหตุนี้จึงบีบอัดขนาดข้อความ แต่ขั้นตอนที่สองคือการนำข้อความที่บีบอัดแล้วรันผ่านกระบวนการ Huffman เก็บภาพเป็น JPEG? ขั้นแรก คอมพิวเตอร์ของคุณจะแปลรูปภาพเป็นการแสดงข้อความ จากนั้นจึงใช้การเข้ารหัส Huffman เพื่อบีบอัดข้อความนั้นอีกครั้ง

ไม่เลวสำหรับโครงการที่ได้รับแรงบันดาลใจจากความปรารถนาของนักศึกษาระดับบัณฑิตศึกษาที่จะข้ามการสอบปลายภาค