วิธีบีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman: 10 ขั้นตอน

สารบัญ:

วิธีบีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman: 10 ขั้นตอน
วิธีบีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman: 10 ขั้นตอน

วีดีโอ: วิธีบีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman: 10 ขั้นตอน

วีดีโอ: วิธีบีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman: 10 ขั้นตอน
วีดีโอ: วิธีล้างมือให้ถูกต้องใน 7ขั้นตอน I รพ.วิชัยเวชฯ หนองแขม 2024, มีนาคม
Anonim

อัลกอริทึมของ Huffman ใช้ในการบีบอัดหรือเข้ารหัสข้อมูล โดยปกติ อักขระแต่ละตัวในไฟล์ข้อความจะถูกจัดเก็บเป็นแปดบิต (ตัวเลข 0 หรือ 1) ที่จับคู่กับอักขระนั้นโดยใช้การเข้ารหัสที่เรียกว่า ASCII ไฟล์ที่เข้ารหัส Huffman จะแบ่งโครงสร้าง 8 บิตที่เข้มงวด เพื่อให้อักขระที่ใช้บ่อยที่สุดถูกจัดเก็บไว้เพียงไม่กี่บิต ('a' อาจเป็น "10" หรือ "1000" แทนที่จะเป็น ASCII ซึ่งก็คือ "01100001"). อักขระทั่วไปที่น้อยที่สุดมักจะใช้มากกว่า 8 บิตมาก ('z' อาจเป็น "00100011010") แต่เนื่องจากมันเกิดขึ้นน้อยมาก การเข้ารหัส Huffman โดยรวมจึงสร้างไฟล์ที่เล็กกว่าต้นฉบับมาก

ขั้นตอน

ส่วนที่ 1 จาก 2: การเข้ารหัส

บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 1
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 1

ขั้นตอนที่ 1 นับความถี่ของอักขระแต่ละตัวในไฟล์ที่จะเข้ารหัส

รวมอักขระจำลองเพื่อทำเครื่องหมายที่ส่วนท้ายของไฟล์ ซึ่งจะมีความสำคัญในภายหลัง สำหรับตอนนี้ ให้เรียกมันว่า EOF (ส่วนท้ายของไฟล์) และทำเครื่องหมายว่ามีความถี่เท่ากับ 1

ตัวอย่างเช่น หากคุณต้องการเข้ารหัสไฟล์ข้อความที่อ่านว่า "ab ab cab " คุณจะต้องมี 'a' พร้อมความถี่ 3, 'b' พร้อมความถี่ 3, ' ' (ช่องว่าง) พร้อมความถี่ 2, 'c' พร้อมความถี่ 1 และ EOF ที่มีความถี่ 1

บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 2
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 2

ขั้นตอนที่ 2 จัดเก็บอักขระเป็นโหนดทรีและใส่ลงในคิวลำดับความสำคัญ

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

  • ต้นไม้ไบนารีเป็นรูปแบบข้อมูลที่แต่ละส่วนของข้อมูลเป็นโหนดที่สามารถมีแม่และลูกสองคน มักถูกวาดเป็นต้นไม้ที่แตกแขนง จึงเป็นที่มาของชื่อ
  • คิวคือการรวบรวมข้อมูลที่มีชื่ออย่างเหมาะสม โดยสิ่งแรกที่ต้องเข้าไปในคิวคือสิ่งแรกที่ออกมาด้วย (เช่น การรอเข้าแถว) ในคิวที่มีลำดับความสำคัญ ข้อมูลจะถูกจัดเก็บตามลำดับความสำคัญ เพื่อให้สิ่งแรกที่ออกมาเป็นสิ่งที่เร่งด่วนที่สุด สิ่งที่มีความสำคัญน้อยที่สุด แทนที่จะเป็นสิ่งแรกที่อยู่ในคิว
  • ในตัวอย่าง "ab ab cab" ลำดับความสำคัญของคุณจะมีลักษณะดังนี้: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 3
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 3

ขั้นตอนที่ 3 เริ่มสร้างต้นไม้ของคุณ

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

ลำดับความสำคัญของคิวตอนนี้มีลักษณะดังนี้: {' ':2, new node:2, 'a':3, 'b':3}

บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 4
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 4

ขั้นตอนที่ 4 สร้างต้นไม้ของคุณให้เสร็จ:

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

  • เมื่อคุณทำเสร็จแล้ว โหนดสุดท้ายในคิวจะเป็นรูทของแผนผังการเข้ารหัส โดยโหนดอื่นๆ ทั้งหมดจะแตกแขนงออกจากโหนดนั้น
  • อักขระที่ใช้บ่อยที่สุดจะเป็นใบที่อยู่ใกล้กับยอดต้นไม้มากที่สุด ในขณะที่อักขระที่ไม่ค่อยได้ใช้จะอยู่ที่ด้านล่างของต้นไม้ ห่างจากรากมากขึ้น
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 5
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 5

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

  • ตัวอย่างเช่น เริ่มต้นที่รูท ไปที่ชายด์ด้านซ้ายของรูท จากนั้นไปที่ชายด์ด้านซ้ายของโหนดนั้น เนื่องจากโหนดที่คุณอยู่ตอนนี้ไม่มีลูก คุณจึงมาถึงตัวละครแล้ว นี่คือ ' '. เนื่องจากคุณเดินไปทางซ้ายสองครั้งเพื่อมาที่นี่ การเข้ารหัสสำหรับ ' ' คือ "00"
  • สำหรับแผนผังนี้ แผนที่จะมีลักษณะดังนี้: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 6
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 6

ขั้นตอนที่ 6 ในไฟล์เอาต์พุต รวมแผนที่การเข้ารหัสเป็นส่วนหัว

ซึ่งจะทำให้สามารถถอดรหัสไฟล์ได้

บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่7
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่7

ขั้นตอนที่ 7 เข้ารหัสไฟล์

สำหรับอักขระแต่ละตัวในไฟล์ที่จะเข้ารหัส ให้เขียนลำดับไบนารีที่คุณจัดเก็บไว้ในแผนที่ เมื่อคุณเข้ารหัสไฟล์เสร็จแล้ว อย่าลืมเพิ่ม EOF ต่อท้าย

  • สำหรับไฟล์ "ab ab cab" ไฟล์ที่เข้ารหัสจะมีลักษณะดังนี้: "1011001011000101011011"
  • ไฟล์ถูกจัดเก็บเป็นไบต์ (8 บิตหรือ 8 หลักไบนารี) เนื่องจากอัลกอริธึมการเข้ารหัส Huffman ไม่ได้ใช้รูปแบบ 8 บิต ไฟล์ที่เข้ารหัสมักจะมีความยาวไม่เท่ากับ 8 หลัก ตัวเลขที่เหลือจะถูกเติมด้วย 0 ในกรณีนี้ จะมีการเพิ่ม 0 สองตัวที่ส่วนท้ายของไฟล์ ซึ่งดูเหมือนเป็นช่องว่างอื่น นี่อาจเป็นปัญหา: ตัวถอดรหัสจะรู้ได้อย่างไรว่าเมื่อใดควรหยุดอ่าน อย่างไรก็ตาม เนื่องจากเราได้รวมอักขระท้ายไฟล์ไว้ด้วย ตัวถอดรหัสจะเข้ามาที่ส่วนนี้แล้วหยุด โดยไม่สนใจสิ่งอื่นที่เพิ่มเข้ามาหลังจากนั้น

ส่วนที่ 2 จาก 2: การถอดรหัส

บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 8
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 8

ขั้นตอนที่ 1 อ่านในไฟล์ที่เข้ารหัส Huffman

ขั้นแรก อ่านส่วนหัวซึ่งควรเป็นแผนที่การเข้ารหัส ใช้สิ่งนี้เพื่อสร้างโครงสร้างการถอดรหัสในลักษณะเดียวกับที่คุณสร้างต้นไม้ที่คุณใช้ในการเข้ารหัสไฟล์ ต้นไม้ทั้งสองควรเหมือนกัน

บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 9
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 9

ขั้นตอนที่ 2 อ่านในเลขฐานสองครั้งละหนึ่งหลัก

สำรวจต้นไม้ในขณะที่คุณอ่าน: ถ้าคุณอ่านใน '0' ไปที่ลูกด้านซ้ายของโหนดที่คุณอยู่ และถ้าคุณอ่านใน '1' ให้ไปที่ลูกที่ถูกต้อง เมื่อคุณไปถึงใบไม้ (โหนดที่ไม่มีลูก) แสดงว่าคุณมาถึงตัวละครแล้ว เขียนอักขระลงในไฟล์ถอดรหัส

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

บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 10
บีบอัดข้อมูลโดยใช้การเข้ารหัส Huffman ขั้นตอนที่ 10

ขั้นตอนที่ 3 ทำซ้ำจนกว่าจะถึง EOF

ยินดีด้วย! คุณได้ถอดรหัสไฟล์

แนะนำ: