ดังที่ได้กล่าวไว้ข้างต้น งานสำคัญประการหนึ่งของการเตรียมข้อมูลเบื้องต้นสำหรับการเข้ารหัสคือการลดความซ้ำซ้อนและจัดรูปแบบทางสถิติของภาษาที่ใช้ การกำจัดความซ้ำซ้อนบางส่วนทำได้โดยการบีบอัดข้อมูล
การบีบอัดข้อมูลคือกระบวนการแปลงข้อความต้นฉบับจากระบบรหัสหนึ่งไปยังอีกระบบหนึ่ง ซึ่งส่งผลให้ ขนาดข้อความ- อัลกอริธึมที่ออกแบบมาสำหรับการบีบอัดข้อมูลสามารถแบ่งออกเป็นสองกลุ่มใหญ่: กลุ่มที่ใช้การบีบอัดแบบไม่สูญเสียข้อมูล (การบีบอัดแบบย้อนกลับ) และกลุ่มที่ใช้การบีบอัดแบบสูญเสีย (การบีบอัดแบบย้อนกลับไม่ได้)
การบีบอัดแบบย้อนกลับหมายถึงการกู้คืนข้อมูลที่แม่นยำอย่างยิ่งหลังจากการถอดรหัสและสามารถใช้เพื่อบีบอัดข้อมูลใด ๆ มันมักจะนำไปสู่การลดปริมาณการไหลของข้อมูลเอาต์พุตโดยไม่เปลี่ยนเนื้อหาข้อมูลนั่นคือโดยไม่สูญเสียโครงสร้างข้อมูล ยิ่งไปกว่านั้น จากสตรีมเอาต์พุตโดยใช้อัลกอริธึมการสร้างใหม่หรือการบีบอัด เราสามารถรับอินพุตได้ และกระบวนการกู้คืนเรียกว่าการบีบอัดหรือการบีบอัด และหลังจากกระบวนการคลายการบีบอัดเท่านั้น ข้อมูลที่เหมาะสมสำหรับการประมวลผลตามรูปแบบภายใน การบีบอัดแบบไม่สูญเสียข้อมูลใช้สำหรับข้อความ ไฟล์ปฏิบัติการ เสียงและกราฟิกคุณภาพสูง
การบีบอัดกลับไม่ได้มักจะมีอัตราส่วนการบีบอัดที่สูงกว่าการเข้ารหัสแบบไม่สูญเสียข้อมูลมาก แต่อนุญาตให้มีการเบี่ยงเบนของข้อมูลที่ถอดรหัสไปจากต้นฉบับได้ ในทางปฏิบัติมีปัญหาในทางปฏิบัติมากมายซึ่งไม่จำเป็นต้องปฏิบัติตามข้อกำหนดในการกู้คืนข้อมูลต้นฉบับที่ถูกต้องหลังจากการบีบอัดข้อมูล โดยเฉพาะอย่างยิ่งสิ่งนี้ใช้กับการบีบอัดข้อมูลมัลติมีเดีย: เสียง ภาพถ่าย หรือภาพวิดีโอ ตัวอย่างเช่น รูปแบบมัลติมีเดีย JPEG และ MPEG ซึ่งใช้การบีบอัดแบบย้อนกลับไม่ได้ถูกนำมาใช้กันอย่างแพร่หลาย การบีบอัดแบบย้อนกลับไม่ได้มักจะไม่ใช้ร่วมกับการเข้ารหัสลับ เนื่องจากข้อกำหนดหลักสำหรับระบบการเข้ารหัสคือข้อมูลที่ถอดรหัสจะเหมือนกับข้อมูลต้นฉบับ อย่างไรก็ตาม เมื่อใช้เทคโนโลยีมัลติมีเดีย ข้อมูลที่แสดงในรูปแบบดิจิทัลมักจะถูกบีบอัดอย่างถาวรก่อนที่จะถูกส่งไปยังระบบการเข้ารหัสเพื่อทำการเข้ารหัส หลังจากที่ข้อมูลถูกส่งไปยังผู้บริโภคและถอดรหัสแล้ว ไฟล์มัลติมีเดียจะถูกใช้ในรูปแบบบีบอัด (นั่นคือ ไฟล์เหล่านี้จะไม่ถูกกู้คืน)
ลองมาดูวิธีการบีบอัดข้อมูลแบบพลิกกลับได้ที่พบบ่อยที่สุดบ้าง
วิธีการและอัลกอริธึมที่เรียบง่ายที่รู้จักกันดีที่สุดสำหรับการบีบอัดข้อมูลในลักษณะย้อนกลับได้คือการเข้ารหัสชุดของลำดับ (การเข้ารหัสความยาวรัน - RLE) สาระสำคัญของวิธีการในแนวทางนี้คือการแทนที่เชนหรือชุดของไบต์ที่ซ้ำกันด้วยไบต์ตัวเข้ารหัสหนึ่งไบต์และตัวนับสำหรับจำนวนการทำซ้ำ ปัญหาของวิธีการที่คล้ายกันทั้งหมดเป็นเพียงการกำหนดวิธีที่อัลกอริธึมการขยายขนาดสามารถแยกแยะชุดที่เข้ารหัสจากลำดับไบต์อื่นที่ไม่ได้เข้ารหัสในสตรีมไบต์ผลลัพธ์ การแก้ปัญหามักจะทำได้โดยการวางเครื่องหมายไว้ที่จุดเริ่มต้นของโค้ดเชน เครื่องหมายดังกล่าวอาจเป็นค่าบิตลักษณะเฉพาะในไบต์แรกของชุดรหัสซึ่งเป็นค่าของไบต์แรกของชุดรหัส ข้อเสียของวิธี RLE คืออัตราส่วนการบีบอัดค่อนข้างต่ำหรือค่าใช้จ่ายในการเข้ารหัสไฟล์ที่มีจำนวนซีรีย์น้อย และที่แย่กว่านั้นคือมีจำนวนไบต์ซ้ำในซีรีย์เพียงเล็กน้อย
ด้วยการเข้ารหัสข้อมูลที่สม่ำเสมอ จำนวนบิตที่เท่ากันจะถูกจัดสรรให้กับข้อความ โดยไม่คำนึงถึงความน่าจะเป็นที่จะเกิดขึ้น ในขณะเดียวกัน ก็สมเหตุสมผลที่จะถือว่าความยาวรวมของข้อความที่ส่งจะลดลงหากข้อความที่เกิดขึ้นบ่อยครั้งถูกเข้ารหัสด้วยคำรหัสสั้น และข้อความที่ไม่ค่อยเกิดขึ้นด้วยข้อความที่ยาวกว่า ปัญหาที่เกิดขึ้นในกรณีนี้เกี่ยวข้องกับความจำเป็นในการใช้งาน รหัสที่มีความยาวคำรหัสแปรผัน- มีหลายวิธีในการสร้างโค้ดดังกล่าว
หนึ่งในวิธีที่ใช้กันอย่างแพร่หลายในทางปฏิบัติคือวิธีการพจนานุกรมซึ่งตัวแทนหลักซึ่งรวมถึงอัลกอริธึมของตระกูล Ziv และ Lempel แนวคิดพื้นฐานของพวกเขาคือชิ้นส่วนของสตรีมอินพุต ("วลี") จะถูกแทนที่ด้วยตัวชี้ไปยังตำแหน่งที่ปรากฏในข้อความก่อนหน้านี้ ในวรรณกรรม อัลกอริธึมดังกล่าวเรียกว่า อัลกอริธึม การบีบอัด LZ.
วิธีนี้จะปรับให้เข้ากับโครงสร้างของข้อความอย่างรวดเร็วและสามารถเข้ารหัสคำฟังก์ชันสั้น ๆ ได้ เนื่องจากคำเหล่านี้ปรากฏบ่อยมาก นอกจากนี้ยังสามารถสร้างคำและวลีใหม่จากส่วนต่างๆ ของคำที่พบก่อนหน้านี้ได้ การถอดรหัสข้อความที่บีบอัดจะดำเนินการโดยตรง - ตัวชี้จะถูกแทนที่ด้วยวลีสำเร็จรูปจากพจนานุกรมที่ชี้ไป ในทางปฏิบัติ วิธี LZ ได้รับการบีบอัดที่ดี คุณสมบัติที่สำคัญคือการทำงานของตัวถอดรหัสที่รวดเร็วมาก
อีกวิธีหนึ่งในการบีบอัดข้อมูลก็คือ รหัสฮัฟฟ์แมนตัวเข้ารหัสและตัวถอดรหัสซึ่งมีการใช้งานฮาร์ดแวร์ที่ค่อนข้างง่าย แนวคิดของอัลกอริทึมมีดังนี้: เมื่อทราบความน่าจะเป็นของสัญลักษณ์ที่ปรากฏในข้อความจึงเป็นไปได้ที่จะอธิบายขั้นตอนการสร้างรหัสที่มีความยาวผันแปรได้ซึ่งประกอบด้วยจำนวนบิตจำนวนเต็ม อักขระมีแนวโน้มที่จะได้รับรหัสที่สั้นกว่า ในขณะที่อักขระที่เกิดไม่บ่อยจะถูกกำหนดรหัสที่ยาวกว่า ด้วยเหตุนี้จึงสามารถลดความยาวโค้ดเวิร์ดโดยเฉลี่ยและประสิทธิภาพการบีบอัดได้มากขึ้น รหัส Huffman มีคำนำหน้าเฉพาะ (จุดเริ่มต้นของคำรหัส) ซึ่งช่วยให้สามารถถอดรหัสได้อย่างชัดเจน แม้จะมีความยาวแปรผันก็ตาม
ขั้นตอนในการสังเคราะห์โค้ด Huffman แบบคลาสสิกจะถือว่ามีข้อมูลเบื้องต้นเกี่ยวกับคุณลักษณะทางสถิติของแหล่งที่มาของข้อความ กล่าวอีกนัยหนึ่ง นักพัฒนาจะต้องทราบความน่าจะเป็นของการเกิดสัญลักษณ์บางอย่างจากข้อความที่ถูกสร้างขึ้น ลองดูการสังเคราะห์โค้ด Huffman โดยใช้ตัวอย่างง่ายๆ
พี(ส 1)=0.2, พี(ส 2)=0.15, พี(ส 3)=0.55, พี(ส 4)=0.1- ลองจัดเรียงสัญลักษณ์ตามลำดับความน่าจะเป็นที่จะเกิดขึ้นจากมากไปหาน้อยและนำเสนอในรูปแบบของตาราง (รูปที่ 14.3, a)
ขั้นตอนการสังเคราะห์โค้ดประกอบด้วยสามขั้นตอนหลัก ในขั้นตอนแรก แถวของตารางจะยุบลง: สองแถวที่สอดคล้องกับอักขระที่มีความน่าจะเป็นน้อยที่สุดจะถูกแทนที่ด้วยแถวที่มีความน่าจะเป็นทั้งหมด หลังจากนั้นตารางจะถูกเรียงลำดับใหม่อีกครั้ง การบิดจะดำเนินต่อไปจนกระทั่งเหลือเพียงแถวเดียวในตารางโดยมีความน่าจะเป็นรวมเท่ากับหนึ่ง (รูปที่ 14.3, b)
ข้าว. 14.3.
ในขั้นตอนที่สอง แผนผังโค้ดจะถูกสร้างขึ้นโดยใช้ตารางที่ถูกยุบ (รูปที่ 14.4, a) ต้นไม้ถูกสร้างขึ้นโดยเริ่มจากคอลัมน์สุดท้ายของตาราง
ข้าว. 14.4.
รากของต้นไม้ถูกสร้างขึ้นโดยหน่วยที่อยู่ในคอลัมน์สุดท้าย ในตัวอย่างที่กำลังพิจารณา หน่วยนี้ถูกสร้างขึ้นจากความน่าจะเป็น 0.55 และ 0.45 ซึ่งแสดงเป็นโหนดต้นไม้สองโหนดที่เกี่ยวข้องกับราก อันแรกสอดคล้องกับสัญลักษณ์ S 3 และดังนั้นจึงไม่มีการแยกย่อยเพิ่มเติมของโหนดนี้
โหนดที่สองซึ่งมีป้ายกำกับว่ามีความน่าจะเป็น 0.45 เชื่อมต่อกับโหนดระดับที่สามสองโหนด โดยมีความน่าจะเป็น 0.25 และ 0.2 ความน่าจะเป็น 0.2 สอดคล้องกับสัญลักษณ์ S 1 และความน่าจะเป็น 0.25 ในทางกลับกันนั้นเกิดจากความน่าจะเป็น 0.15 ของการปรากฏตัวของสัญลักษณ์ S 2 และ 0.1 ของการปรากฏตัวของสัญลักษณ์ S 4 .
ขอบที่เชื่อมต่อแต่ละโหนดของแผนผังโค้ดจะมีหมายเลข 0 และ 1 (เช่น ขอบด้านซ้ายคือ 0 และขอบด้านขวาคือ 1) ในขั้นตอนที่สามซึ่งเป็นขั้นตอนสุดท้าย ตารางจะถูกสร้างขึ้นโดยเปรียบเทียบสัญลักษณ์ต้นฉบับและคำรหัสรหัส Huffman ที่เกี่ยวข้อง คำรหัสเหล่านี้เกิดขึ้นจากการอ่านตัวเลขที่ทำเครื่องหมายขอบที่สร้างเส้นทางจากรากของต้นไม้ไปยังสัญลักษณ์ที่เกี่ยวข้อง สำหรับตัวอย่างที่อยู่ระหว่างการพิจารณา รหัส Huffman จะอยู่ในรูปแบบที่แสดงในตารางทางด้านขวา (รูปที่ 14.4, b)
อย่างไรก็ตาม อัลกอริธึม Huffman แบบคลาสสิกมีข้อเสียเปรียบที่สำคัญประการหนึ่ง หากต้องการสร้างเนื้อหาของข้อความที่บีบอัดขึ้นมาใหม่ ตัวถอดรหัสจะต้องทราบตารางความถี่ที่ตัวเข้ารหัสใช้ ดังนั้น ความยาวของข้อความที่ถูกบีบอัดจะเพิ่มขึ้นตามความยาวของตารางความถี่ที่ต้องส่งก่อนข้อมูล ซึ่งอาจลบล้างความพยายามทั้งหมดในการบีบอัดข้อความ
อีกทางเลือกหนึ่ง การเข้ารหัส Huffman แบบคงที่ประกอบด้วยการดูสตรีมอินพุตและสร้างการเข้ารหัสตามสถิติที่รวบรวม ซึ่งต้องผ่านไฟล์สองครั้ง - หนึ่งสำหรับการดูและรวบรวมข้อมูลทางสถิติ และครั้งที่สองสำหรับการเข้ารหัส ในการเข้ารหัส Huffman แบบคงที่ สัญลักษณ์อินพุต (สายโซ่บิตที่มีความยาวต่างกัน) จะสัมพันธ์กับสายโซ่บิตที่มีความยาวแปรผันเช่นกัน - รหัสของมัน ความยาวของรหัสของแต่ละสัญลักษณ์นั้นถือเป็นสัดส่วนกับลอการิทึมไบนารีของความถี่โดยใช้เครื่องหมายตรงกันข้าม และชุดรวมของสัญลักษณ์ที่แตกต่างกันทั้งหมดที่พบจะถือเป็นตัวอักษรไหล
มีวิธีอื่น - การปรับตัวหรือ การเข้ารหัส Huffman แบบไดนามิก- หลักการทั่วไปของมันคือการเปลี่ยนรูปแบบการเข้ารหัสขึ้นอยู่กับลักษณะของการเปลี่ยนแปลงในอินพุตสตรีม วิธีนี้มีอัลกอริธึมแบบส่งผ่านครั้งเดียวและไม่จำเป็นต้องจัดเก็บข้อมูลเกี่ยวกับการเข้ารหัสที่ใช้อย่างชัดเจน การเข้ารหัสแบบอะแดปทีฟสามารถให้อัตราส่วนการบีบอัดที่สูงกว่าการเข้ารหัสแบบคงที่ เนื่องจากการเปลี่ยนแปลงในความถี่ของสตรีมอินพุตจะถูกนำมาพิจารณาอย่างละเอียดยิ่งขึ้น เมื่อใช้การเข้ารหัส Huffman แบบปรับตัว ความยุ่งยากของอัลกอริทึมคือความจำเป็นในการปรับรหัสต้นไม้และอักขระของตัวอักษรหลักอย่างต่อเนื่องตามสถิติที่เปลี่ยนแปลงของสตรีมอินพุต
วิธีการของ Huffman ให้ความเร็วค่อนข้างสูงและคุณภาพการบีบอัดที่ดีปานกลาง อย่างไรก็ตาม การเข้ารหัสของ Huffman มีความซ้ำซ้อนน้อยที่สุด โดยมีเงื่อนไขว่าอักขระแต่ละตัวจะถูกเข้ารหัสด้วยตัวอักษรรหัสอักขระโดยแยกสตริงสองบิต - (0, 1) ข้อเสียเปรียบหลักของวิธีนี้คือการขึ้นอยู่กับระดับการบีบอัดใกล้กับความน่าจะเป็นของสัญลักษณ์ถึง 2 ในระดับลบซึ่งเกิดจากการที่แต่ละสัญลักษณ์ถูกเข้ารหัสด้วยจำนวนบิตจำนวนเต็ม
นำเสนอโซลูชั่นที่แตกต่างไปจากเดิมอย่างสิ้นเชิง การเข้ารหัสทางคณิตศาสตร์- วิธีนี้มีพื้นฐานมาจากแนวคิดในการแปลงอินพุตสตรีมให้เป็นเลขทศนิยมตัวเดียว การเข้ารหัสทางคณิตศาสตร์เป็นวิธีการที่ช่วยให้สามารถบรรจุอักขระของตัวอักษรอินพุตได้โดยไม่สูญเสีย โดยมีเงื่อนไขว่าต้องทราบการกระจายความถี่ของอักขระเหล่านี้
ลำดับสัญลักษณ์ที่ต้องการเมื่อบีบอัดด้วยการเข้ารหัสทางคณิตศาสตร์ถือเป็นเศษส่วนไบนารีบางส่วนจากช่วงเวลา )
