รหัสฮัฟฟ์แมน
รหัส Huffman ถูกกำหนดให้เป็นประเภทเฉพาะของรหัสนำหน้าที่เหมาะสมที่สุดซึ่งมักใช้สำหรับการบีบอัดข้อมูลแบบไม่สูญเสียข้อมูล
กระบวนการในการค้นหาหรือใช้รหัสดังกล่าวดำเนินการโดยใช้การเข้ารหัส Huffman ซึ่งเป็นอัลกอริทึมที่พัฒนาโดย David A. Huffman ขณะที่เขาเป็น Sc.D. เป็นนักศึกษาที่ MIT และตีพิมพ์ในบทความปี 1952 เรื่อง "A Method for the Construction of Minimum-Redundancy Codes"
เอาต์พุตจากอัลกอริธึมของ Huffman สามารถแสดงเป็นตารางรหัสความยาวผันแปรสำหรับการเข้ารหัสสัญลักษณ์ต้นทาง (เช่น อักขระในไฟล์) อัลกอริธึมสร้างตารางนี้จากความน่าจะเป็นโดยประมาณหรือความถี่ของการเกิด (น้ำหนัก) สำหรับแต่ละค่าที่เป็นไปได้ของสัญลักษณ์แหล่งที่มา เช่นเดียวกับวิธีการเข้ารหัสเอนโทรปีอื่น ๆ สัญลักษณ์ทั่วไปมักจะแสดงโดยใช้บิตน้อยกว่าสัญลักษณ์ทั่วไป วิธีการของฮัฟฟ์แมนสามารถนำไปใช้ได้อย่างมีประสิทธิภาพ โดยค้นหาโค้ดในเวลาที่เชิงเส้นตรงกับจำนวนน้ำหนักอินพุต หากมีการจัดเรียงตุ้มน้ำหนักเหล่านี้
เอนโทรปี
ในทฤษฎีข้อมูล ทฤษฎีบทการเข้ารหัสที่มาของแชนนอน (หรือทฤษฎีการเข้ารหัสแบบไร้เสียง) สามารถสร้างขีดจำกัดของการบีบอัดข้อมูลที่เป็นไปได้ และความหมายในการดำเนินงานของเอนโทรปีของแชนนอน
ทฤษฎีบทรหัสต้นทางแสดงให้เห็นว่า (ในขีดจำกัด เนื่องจากความยาวของสตรีมข้อมูลตัวแปรสุ่มอิสระและกระจายเหมือนกัน (i.i.d. ) ข้อมูลมีแนวโน้มที่จะไม่สิ้นสุด) เป็นไปไม่ได้ที่จะบีบอัดข้อมูลเพื่อให้อัตราโค้ด (จำนวนเฉลี่ยของ บิตต่อสัญลักษณ์) มีขนาดเล็กกว่าเอนโทรปีของแชนนอนของแหล่งที่มา โดยที่แทบไม่มั่นใจว่าข้อมูลจะสูญหายไป อย่างไรก็ตาม เป็นไปได้ที่จะได้รับอัตราโค้ดโดยพลการใกล้กับเอนโทรปีของแชนนอน โดยมีความเป็นไปได้ที่จะสูญเสียเพียงเล็กน้อย
เอนโทรปีข้อมูลถูกกำหนดให้เป็นอัตราเฉลี่ยที่ข้อมูลถูกสร้างขึ้นโดยแหล่งข้อมูลสุ่ม
คำนวณเอนโทรปีสำหรับตัวแปรสุ่ม
นอกจากนี้เรายังสามารถคำนวณจำนวนข้อมูลที่มีอยู่ในตัวแปรสุ่มได้อีกด้วย
ตัวอย่างเช่น หากเราต้องการคำนวณข้อมูลสำหรับตัวแปรสุ่ม X ที่มีการแจกแจงความน่าจะเป็น p ค่านี้อาจถูกเขียนเป็นฟังก์ชัน H(); ตัวอย่างเช่น:H(X)
ผลก็คือ การคำนวณข้อมูลสำหรับตัวแปรสุ่มจะเหมือนกับการคำนวณข้อมูลสำหรับการแจกแจงความน่าจะเป็นของเหตุการณ์สำหรับตัวแปรสุ่ม
การคำนวณข้อมูลสำหรับตัวแปรสุ่มจะแสดงเป็น “เอนโทรปีข้อมูล” “แชนนอนเอนโทรปี” หรือเพียงแค่ “เอนโทรปี“
มันเกี่ยวข้องกับแนวคิดเรื่องเอนโทรปีจากฟิสิกส์โดยการเปรียบเทียบ โดยที่ทั้งสองเกี่ยวข้องกับความไม่แน่นอนของคำศัพท์
สัญชาตญาณของเอนโทรปีคือมันถูกกำหนดให้เป็นจำนวนบิตเฉลี่ยที่จำเป็นในการแสดงหรือส่งเหตุการณ์ที่ดึงมาจากการแจกแจงความน่าจะเป็นสำหรับตัวแปรสุ่ม
เอนโทรปีของแชนนอนของการแจกแจงถูกกำหนดให้เป็นจำนวนข้อมูลที่คาดหวังในเหตุการณ์ที่ดึงมาจากการแจกแจงนั้น
ให้ขอบเขตที่ต่ำกว่าสำหรับจำนวนบิตที่ต้องการโดยเฉลี่ยในการเข้ารหัสสัญลักษณ์ที่ดึงมาจากการกระจาย P.
สามารถคำนวณเอนโทรปีสำหรับตัวแปรสุ่ม X ที่มี k ในสถานะไม่ต่อเนื่องของ K ดังนี้
H(X) = -sum(each k in K p(k) * log(p(k)))
นั่นหมายถึงค่าลบของผลรวมของความน่าจะเป็นของแต่ละเหตุการณ์คูณด้วยล็อกของความน่าจะเป็นของแต่ละเหตุการณ์
เช่นเดียวกับข้อมูล ฟังก์ชัน log() ใช้งาน base-2 และหน่วยเป็นบิต สามารถใช้ลอการิทึมธรรมชาติแทนได้
เอนโทรปีต่ำสุดคำนวณหาตัวแปรสุ่มที่มีเหตุการณ์เดียวที่มีความน่าจะเป็น 1.0 ซึ่งเป็นค่าที่แน่นอน เอนโทรปีที่ใหญ่ที่สุดสำหรับตัวแปรสุ่มจะเกิดขึ้นได้หากเหตุการณ์ทั้งหมดมีความเป็นไปได้เท่ากัน
