ล้วงความลับการบีบอัดไฟล์

 

เชื่อว่าบรรดาผู้ใช้คอมพิวเตอร์หลายคนคงรู้จักไฟล์ที่ผ่านการบีบอัดเอาไว้ (ไฟล์ที่นามสกุล .Zip นั่นแหละครับ) กันแล้ว และคงจะทราบดีอยู่แล้วว่าสาเหตุที่เราทำการบีบอัดไฟล์นั้น ก็เพื่อลดขนาดของไฟล์ลงเพื่อให้การใช้งานเนื้อที่เก็บข้อมูลของสื่อบันทึกข้อมูลชนิดต่างๆ เช่น ฮาร์ดดิสก์ หรือซีดีรอมเป็นไปอย่างมีประสิทธิภาพมากขึ้น เพราะการที่เราเก็บข้อมูลในรูปของซิปไฟล์ ทำให้เราสามารถบรรจุไฟล์ลงในสื่อบันทึกข้อมูลได้ในปริมาณข้อมูลที่มากขึ้น

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

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

จากนี้ไปเราจะมาทำความเข้าใจกับกระบวนการบีบอัดไฟล์ที่เกิดขึ้นกันว่ามีกลไกและหลักการอย่างไร?

ค้นหาสิ่งหรือข้อมูลที่ซ้ำๆ กันในไฟล์

การบีบอัดไฟล์ เปรียบเหมือนการลดจำนวนบิต (bit) และไบต์ (byte) ของข้อมูลลง และการคลายไฟล์หรือ Unzipไฟล์ ก็คือการสร้างข้อมูลขึ้นมาใหม่จากบิต หรือไบต์ ข้อมูลที่ถูกลดจำนวนลงไปในตอนแรก โดยจะต้องสร้างให้ไฟล์ข้อมูลนั้นๆ เหมือนต้นฉบับเดิม

ขั้นตอนที่โปรแกรมบีบอัดไฟล์ใช้ในการลดขนาดของไฟล์ลง ก็คือการค้นหา "ข้อมูล" ที่ปรากฏซ้ำๆ ภายในไฟล์ต้นฉบับ เพราะไฟล์ส่วนมากที่ใช้กับคอมพิวเตอร์จะประกอบด้วยข้อมูลซ้ำๆ กันเป็นจำนวนมาก หลังจากค้นเจอข้อมูลที่ซ้ำแล้ว เจ้าโปรแกรมที่ใช้ในการบีบอัดไฟล์จะทำการกำจัดข้อมูลที่ซ้ำๆ นั้นออกไป เพื่อความเข้าใจมากขึ้น ผมจะยกตัวอย่างข้อมูลที่เป็นประโยคสุดฮิตซึ่งบางคนอาจจะเคยได้ยินมาแล้ว คือ "Ask not what your country can do for you -- ask what you can do for your country." (อย่าถามว่าประเทศชาติจะให้อะไรแก่ท่าน แต่จงถามตัวเองว่าท่านจะทำอะไรให้ประเทศชาติบ้าง)

ถ้าใครเคยได้ยินมาก่อน ก็จะทราบดีว่าเป็นสุนทรพจน์ของจอห์น เอฟ เคเนดี้ อดีตประธานาธิบดีสหรัฐอเมริกาผู้ล่วงลับไปแล้ว ต่อไปนี้ผมจะเรียกชื่อแบบย่อๆ คือ เจเอฟเค จากคำกล่าวนี้จะพบว่า มีคำในประโยคทั้งหมด 17 คำ ซึ่งเกิดจากตัวอักษรทั้งหมด 61 ตัว, มีช่องว่างหรือ space 16ช่อง, มีเส้นประหนึ่งเส้นประ และมีจุด full stop 1 จุด

สมมติว่า แต่ละส่วนประกอบย่อยๆ ที่กล่าวมาจะใช้เนื้อที่ในหน่วยความจำ 1 หน่วยความจำสำหรับแต่ละส่วนประกอบย่อย ดังนั้นเราจึงได้ขนาดของไฟล์ทั้งหมด (Total file size) เป็น 79 หน่วยความจำ

เป็นที่ทราบดีว่า ขั้นตอนที่โปรแกรมบีบอัดไฟล์ใช้ในการลดขนาดของไฟล์ลง ก็คือการค้นหา "ข้อมูล" ที่ปรากฏซ้ำๆ ภายในไฟล์ต้นฉบับ คำถามคือประโยคสุดฮิตของเจเอฟเค มีข้อมูลหรือคำอะไรบ้างที่ปรากฏซ้ำๆ กันบ้าง ? ก็คำพวกนี้ไงครับที่ทำให้ขนาดของไฟล์ใหญ่โตโดยไม่จำเป็น

ask มี 2 คำในประโยค
what มี 2 คำในประโยค
your มี 2 คำในประโยค
country มี 2 คำในประโยค
can มี 2 คำในประโยค
do มี 2 คำในประโยค
for มี 2 คำในประโยค
you มี 2 คำในประโยค

ถ้าเราไม่สนใจตัวอักษรตัวเล็ก หรือตัวใหญ่ที่ปรากฏในข้อความ พิจารณาอย่างคร่าวๆ จะพบว่าจะมีคำซ้ำๆ ที่เกิดขึ้นในประโยครวมแล้วมากกว่าครึ่งของจำนวนคำ (ข้อมูล) ทั้งหมดในประโยค จากคำทั้ง 9 คำที่เกิดขึ้นซ้ำๆ กันนั่นคือคำว่า -- ask, not, what, your, country, can, do, for, you คำพวกนี้ได้บอกให้รู้ถึงใจความข้อมูลส่วนมากที่เราต้องการแล้ว การที่จะสร้างข้อมูลข้อความอีกครึ่งหนึ่งของประโยคนั้น เราจะพิจารณาไปที่คำชุดแรกที่มีขนาดครึ่งหนึ่งของประโยคทั้งหมด โดยจะทำการใส่ช่องว่างระหว่างคำ และการเว้นวรรคตอนของประโยคเข้าไปในการบีบอัดข้อมูลนี้ จากนี้ไปเราจะมาดูกันว่า ระบบการบีบอัดไฟล์จะทำสิ่งที่กล่าวมานี้ได้อย่างไร

กลไกค้นคำจากฐานข้อมูลดิกชันนารีของโปรแกรม

พื้นฐานในการบีบอัดไฟล์ของโปรแกรมบีบอัดไฟล์ จะใช้หลักการอัลกอริธึ่มพื้นฐาน ที่เรียกว่า LZ adaptive dictionary-based algorithm โดยที่ LZ ก็คือชื่อของนาย Lempe lและนาย Ziv ซึ่งเป็นผู้ที่คิดค้นอัลกอลิธึมพื้นฐานที่ใช้ในการบีบอัดข้อมูลที่กล่าวถึงนี้ ส่วนคำว่า dictionary นั้นจะอ้างถึงวิธีในการทำบัญชีรายชื่อของข้อมูลแต่ละชิ้น สำหรับระบบในการจัดเตรียมดิกชันนารีนั้นจะแตกต่างกันไปในแต่ละโปรแกรมบีบอัดไฟล์ แต่ดิกชันนารีของแต่ละโปรแกรมนั้นยังมีจำนวนลิสต์ข้อมูลคำแบบพื้นฐานในดิกชันนารีที่เหมือนๆ กัน

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

นี่คือคำซ้ำทั้งหมดหลังจากที่กำหนดเลขดัชนีให้กับมันแล้ว (เลขดัชนีคือเลข 1, 2, 3...ไปเรื่อยๆ จนถึง 8)

1. ask
2. what
3. your
4. country
5. can
6. do
7. for
8. you