การเข้ารหัสแบบความยาวแปรผัน
สรุปใจความสำคัญ
- ใช้รหัสที่มีความยาวต่างกัน โดยสัญลักษณ์ที่พบบ่อยจะใช้รหัสสั้นเพื่อประหยัดพื้นที่
- เป็นพื้นฐานสำคัญของการบีบอัดข้อมูลแบบไม่สูญเสีย (Lossless Compression)
- UTF-8 เป็นตัวอย่างที่แพร่หลายที่สุดของการเข้ารหัสตัวอักษรแบบความยาวแปรผัน
- Prefix codes เป็นประเภทรหัสที่ถอดรหัสได้ง่ายที่สุดเพราะไม่มีรหัสใดเป็นส่วนเริ่มต้นของรหัสอื่น
การเข้ารหัสแบบความยาวแปรผัน (Variable-length encoding) คือรูปแบบการกำหนดรหัสในทฤษฎีการเข้ารหัส (Coding Theory) ที่ใช้รหัสที่มีความยาวแตกต่างกันในการแทนค่าสัญลักษณ์ต่างๆ เพื่อนำไปใช้ในการส่งผ่านช่องทางการสื่อสารหรือจัดเก็บในสื่อบันทึกข้อมูล ในทางวิทยาการคอมพิวเตอร์ แนวคิดนี้มีความเกี่ยวข้องโดยตรงกับการจัดการสายบิต (Bit string) เพื่อให้การใช้พื้นที่จัดเก็บมีประสิทธิภาพสูงสุด
หลักการทำงานและความสำคัญ
จุดเด่นของการเข้ารหัสแบบความยาวแปรผันคือความสามารถในการบีบอัดข้อมูลแบบไม่สูญเสีย (Lossless data compression) โดยการกำหนดให้สัญลักษณ์ที่ปรากฏบ่อยครั้งใช้รหัสที่มีความยาวสั้น และสัญลักษณ์ที่ปรากฏน้อยครั้งใช้รหัสที่มีความยาวมากกว่า ส่งผลให้ค่าเฉลี่ยของความยาวรหัสลดลงและประหยัดพื้นที่จัดเก็บ
แนวคิดนี้แตกต่างจากการเข้ารหัสแบบความยาวคงที่ (Fixed-length coding) ซึ่งข้อมูลทุกตัวจะใช้จำนวนบิตเท่ากัน ทำให้การบีบอัดข้อมูลทำได้ยากกว่าและมักต้องจัดการข้อมูลเป็นบล็อกขนาดใหญ่เพื่อให้เกิดประสิทธิภาพ
การประยุกต์ใช้ในระบบคอมพิวเตอร์
การเข้ารหัสตัวอักษรแบบหลายไบต์ (Multibyte Encodings)
การเข้ารหัสแบบหลายไบต์มักถูกพัฒนาขึ้นเพื่อเพิ่มจำนวนตัวอักษรที่สามารถแทนค่าได้ โดยที่ยังคงความสามารถในการทำงานร่วมกับระบบเก่า (Backward compatibility) ตัวอย่างที่ชัดเจนที่สุดคือ UTF-8 ซึ่งใช้ความยาวแปรผันตั้งแต่ 1 ถึง 4 ไบต์ต่อหนึ่งตัวอักษร
ในระบบ UTF-8 จะมีการแบ่งประเภทของหน่วยข้อมูลออกเป็น 3 ประเภทหลัก ได้แก่:
- Singleton: หน่วยข้อมูลเดี่ยวที่แทนตัวอักษรได้ทันที (เช่น ตัวอักษรภาษาอังกฤษในมาตรฐาน ASCII)
- Lead unit: หน่วยนำหน้าสำหรับตัวอักษรที่ต้องใช้หลายไบต์
- Trail unit: หน่วยตามหลังที่ใช้ร่วมกับหน่วยนำหน้าเพื่อระบุตัวอักษรที่สมบูรณ์
ตัวอย่างเช่น ข้อความ "I♥NY" ในรูปแบบ UTF-8 จะประกอบด้วยรหัสฐานสิบหก 49 E2 99 A5 4E 59 โดยที่ 49, 4E และ 59 เป็น Singleton ในขณะที่ E2 เป็น Lead unit และ 99 กับ A5 เป็น Trail unit ที่รวมกันเพื่อแทนสัญลักษณ์รูปหัวใจ (♥)
กลยุทธ์การเข้ารหัสที่สำคัญ
มีอัลกอริทึมหลายตัวที่ใช้หลักการความยาวแปรผันเพื่อเพิ่มประสิทธิภาพในการบีบอัดข้อมูล เช่น:
- Huffman Coding: การสร้างต้นไม้การเข้ารหัสตามความถี่ของข้อมูล
- Lempel–Ziv Coding: การใช้พจนานุกรมเพื่อแทนที่ลำดับข้อมูลที่ซ้ำกัน
- Arithmetic Coding: การแทนที่ข้อความทั้งหมดด้วยตัวเลขทศนิยมเพียงตัวเดียวในช่วง 0 ถึง 1
- Context-adaptive variable-length coding (CAVLC): การเข้ารหัสที่ปรับเปลี่ยนตามบริบทของข้อมูลรอบข้าง
โครงสร้างทางคณิตศาสตร์และการจำแนกประเภท
ในทางทฤษฎี การขยายของรหัส (Extension of a code) คือการจับคู่ลำดับของสัญลักษณ์จากเซตแหล่งกำเนิด (S) ไปยังสายบิตในเซตเป้าหมาย (T) โดยการนำรหัสของแต่ละสัญลักษณ์มาต่อกัน
รหัสแบบความยาวแปรผันสามารถแบ่งระดับความเข้มงวดได้ดังนี้:
- Non-singular codes: รหัสที่สัญลักษณ์แต่ละตัวถูกแมปไปยังสายบิตที่แตกต่างกัน (Injective mapping) เพื่อป้องกันการสูญเสียข้อมูล
- Uniquely decodable codes: รหัสที่เมื่อนำมาต่อกันเป็นสายยาวแล้ว สามารถถอดรหัสกลับเป็นลำดับสัญลักษณ์เดิมได้อย่างถูกต้องเพียงรูปแบบเดียว
- Prefix codes: รหัสที่ไม่มีรหัสของสัญลักษณ์ใดเป็นส่วนเริ่มต้น (Prefix) ของรหัสสัญลักษณ์อื่น ซึ่งเป็นคุณสมบัติที่ทำให้การถอดรหัสทำได้ง่ายและรวดเร็วที่สุด
คำถามที่พบบ่อย
การเข้ารหัสแบบความยาวแปรผันต่างจากการเข้ารหัสแบบความยาวคงที่อย่างไร?
การเข้ารหัสแบบความยาวคงที่ใช้จำนวนบิตเท่ากันสำหรับทุกสัญลักษณ์ ทำให้ง่ายต่อการเข้าถึงข้อมูลตำแหน่งที่แน่นอน แต่สิ้นเปลืองพื้นที่ ส่วนการเข้ารหัสแบบความยาวแปรผันใช้จำนวนบิตตามความถี่ของข้อมูล ทำให้บีบอัดข้อมูลได้ดีกว่าแต่การถอดรหัสมีความซับซ้อนกว่า
ทำไม UTF-8 ถึงถูกจัดเป็นการเข้ารหัสแบบความยาวแปรผัน?
เพราะ UTF-8 ใช้จำนวนไบต์ในการแทนตัวอักษรไม่เท่ากัน โดยตัวอักษรภาษาอังกฤษพื้นฐานจะใช้เพียง 1 ไบต์ ในขณะที่ตัวอักษรในภาษาอื่นหรือสัญลักษณ์พิเศษอาจใช้ 2 ถึง 4 ไบต์
Prefix Code คืออะไรและสำคัญอย่างไร?
Prefix Code คือรหัสที่ไม่มีรหัสของสัญลักษณ์ใดเป็นจุดเริ่มต้นของรหัสสัญลักษณ์อื่น ทำให้คอมพิวเตอร์สามารถถอดรหัสได้ทันทีที่อ่านบิตจนครบชุดโดยไม่ต้องรออ่านบิตถัดไปเพื่อตรวจสอบ