การบีบอัดข้อมูล
แนะนำใหม่| English | ความหมาย |
|---|---|
| compression/kəmˈpreʃn/ | การบีบอัด |
| lossless/ˈlɒsləs/ | แบบไม่สูญเสียข้อมูล |
| lossy/ˈlɒsi/ | แบบสูญเสียข้อมูล |
| bandwidth/ˈbændwɪdθ/ | แบนด์วิดท์ |
| run-length encoding/rʌn leŋθ enˈkəʊdɪŋ/ | การเข้ารหัสความยาวของลำดับ |
| dictionary coding/ˈdɪkʃənəri ˈkəʊdɪŋ/ | การเข้ารหัสด้วยพจนานุกรม |
| Huffman coding/ˈhʌfmən ˈkəʊdɪŋ/ | การเข้ารหัสฮูฟแมน |
| spatial/ˈspeɪʃl/ | เชิงพื้นที่ |
| temporal/ˈtempərəl/ | เชิงเวลา |
Ba chữ cái khiến web trở nên khả thi
- Năm 1987, một lập trình viên tên Phil Katz viết chương trình nén và đưa định dạng file vào phạm vi công cộng. Ông gọi nó là ZIP. Ông ấy 24 tuổi
- Không có gì về web hoạt động nếu không có ý tưởng đó. Một giây video HD không nén là khoảng 187 MB; một bộ phim hai giờ sẽ là 1.3 terabytes. Phát trực tuyến qua kết nối nhà là bất khả thi về mặt toán học
- Các bộ phim bạn xem có lẽ chỉ bằng một phần nghìn của con số đó, và chúng vẫn trông đúng, vì việc nén loại bỏ những thứ mắt bạn chưa bao giờ chú ý đến
- Bài học này là nén: hai họ, ba phương pháp không mất dữ liệu, và cách biện minh cho một phương pháp đối với một file cụ thể
Mất dữ liệu và không mất dữ liệu
- Nén giảm kích thước file, tiết kiệm không gian lưu trữ và băng thông truyền dẫn, và làm cho tải xuống và phát trực tuyến nhanh hơn
- Lossless (ไม่สูญเสียข้อมูล) คือการบีบอัดที่ recovering ข้อมูลต้นฉบับได้ ครบถ้วนตามเดิม ZIP และ PNG เป็น lossless
- Lossy (สูญเสียข้อมูล) เป็นการลบข้อมูลบางส่วนอย่างถาวร ทำให้ ไม่สามารถ recover ข้อมูลต้นฉบับได้ JPEG, MP3 และวิดีโอแบบสตรีมมิ่งเป็น lossy
Recover exactly, or shrink much further -> Recover ได้ครบถ้วน หรือหดขนาดได้มากกว่านั้น
การบีบอัดข้อมูลที่ไม่สูญเสียข้อมูลหมายถึง:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การบีบอัดข้อมูลที่ไม่สูญเสียข้อมูลช่วยให้สามารถสร้างข้อมูลต้นฉบับออกมาได้พอดี — จำเป็นสำหรับข้อความ โปรแกรม และ ZIP/PNG
จับคู่แนวคิดการบีบอัดแต่ละอย่างกับความหมาย
Difficulty 2/5 · 140 coins + a small bonus on first completion today
การบีบอัดที่ไม่สูญเสียข้อมูลเก็บทุกบิต (จำเป็นสำหรับข้อความ/โค้ด); การบีบอัดแบบสูญเสียข้อมูลแลกคุณภาพด้วย文件大小 (ภาพถ่าย, เสียง)
การบีบอัดข้อมูลที่ไม่สูญเสียข้อมูลสร้างข้อมูลต้นฉบับออกมาได้พอดี (จำเป็นสำหรับข้อความและโปรแกรม) ในขณะที่การบีบอัดแบบสูญเสียข้อมูลทิ้งข้อมูลบางส่วนออกไปเพื่อลด文件大小 (ใช้สำหรับภาพถ่ายและเสียง)
Difficulty 1/5 · 100 coins + a small bonus on first completion today
นั่นเป็นเหตุผลว่าทำไมโปรแกรมหรือ ZIP ต้องเป็นการบีบอัดที่ไม่สูญเสียข้อมูล แต่ภาพถ่ายหรือเพลงสามารถใช้การบีบอัดแบบสูญเสียข้อมูลได้
ตัวอย่างวิธีทำ: ให้เหตุผลในการเลือก
- บริษัทจัดเก็บสเปรดชีตบัญชี Which kind of compression, and why? Lossless, เพราะสเปรดชีตต้องถูก restore กลับมาได้อย่างถูกต้อง; การเปลี่ยนค่าเพียงค่าเดียวจะทำให้บัญชีผิดเพี้ยน
- 摄影师 uploads holiday photographs to a phone gallery. Lossy, เพราะรูปภาพถูกดูบนหน้าจอขนาดเล็กที่ detail ที่ drop ไปมองไม่เห็น, และไฟล์เล็กลง upload เร็วขึ้นและใช้พื้นที่จัดเก็บน้อยลง
- ชื่อประเภท แล้วให้เหตุผล จากสถานการณ์ "Lossy is smaller" เพียงอย่างเดียวไม่ใช่เหตุผลที่ยอมรับได้
ไฟล์ใดควรบีบอัดโดยไม่สูญเสียข้อมูล?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
โค้ดแหล่งกำเนิดต้องกู้คืนได้พอดี — ตัวอักษรเปลี่ยนเพียงตัวเดียวก็อาจทำให้มันพังได้ — ดังนั้นจึงต้องการการบีบอัดที่ไม่สูญเสียข้อมูล
Run-length encoding
- Run-length encoding (RLE) แทนที่ run ของค่าซ้ำกันด้วยค่าหนึ่งและ count: แทนที่จะเก็บ 8 white pixels เดียวกัน เก็บ "8, white"
- มีประสิทธิภาพสูงกับข้อมูลที่มี run ยาว เช่น icons, diagrams, scans ขาวดำ และพื้นที่สีแบน
- ใช้ไม่ได้ และอาจทำให้ไฟล์ ใหญ่ขึ้น กับ noisy data เช่น Photographs, ที่เกือบไม่มีค่าเพื่อนข้างกันเท่ากันเลย
Each row becomes counts and colours -> แต่ละแถวกลายเป็น counts และ colors
Run-length encoding ทำงานได้ดีที่สุดกับข้อมูลที่มี:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
RLE แทนชุดค่าซ้ำซ้อนด้วยจำนวนนับ + ค่า ดังนั้นมันจึงโดดเด่นในพื้นที่เรียบและไร้ประโยชน์กับข้อมูลที่มีสัญญาณรบกวน
Worked example: encode a row with RLE
- แถวหนึ่งของภาพขาวดำขนาด 8 พิกเซลอ่านได้ดังนี้: ขาว ขาว ขาว ดำ ดำ ขาว ขาว ขาว.编码ด้วย RLE.
- ขาวสามตัว, ดำสองตัว, ขาวสามตัว, ดังนั้นคือ
3W 2B 3W, หรือเป็นคู่ๆ คือ(3, 0) (2, 1) (3, 0)ถ้าขาวคือ 0. - ค่าแปดค่ากลายเป็นสามคู่ ตอนนี้ให้เข้ารหัส
W B W B W B W BEight runs of one:1W 1B 1W 1B 1W 1B 1W 1B, ซึ่งจัดเก็บ มากกว่า ข้อมูลต้นฉบับ นั่นคือเหตุผลที่ RLE ไม่ถูกนำไปใช้กับภาพถ่าย
Run-length encoding (วิธีที่ไม่สูญเสียข้อมูล)
Run-length encoding แทนชุดค่าซ้ำซ้อนด้วยค่าหนึ่งบวกกับจำนวนนับ เป็นวิธีที่ไม่สูญเสียข้อมูล — สามารถสร้างข้อมูลต้นฉบับออกมาได้อย่างสมบูรณ์ — แต่จะลดขนาดข้อมูลที่มีชุดซ้ำยาวเท่านั้น
เข้ารหัสแถวพิกเซล W W W B B W W W ด้วย run-length encoding โดยใช้รูปแบบ 3W 2B 3W
Difficulty 1/5 · 100 coins + a small bonus on first completion today
สามสีขาว สองสีดำ สามสีขาว แปดค่ากลายเป็นสามคู่ แต่ถ้าเป็นแถวสลับกันจะเป็นแปดคู่และ文件大小จะเพิ่มขึ้น
Run-length encoding จะทำให้ไฟล์เล็กลงเสมอ
Difficulty 1/5 · 100 coins + a small bonus on first completion today
บนข้อมูลที่ไม่มีชุดซ้ำ เช่น ภาพถ่ายหรือแพทเทิร์นสลับกัน ทุกชุดมีความยาวเป็นหนึ่งและการเข้ารหัสจะเก็บมากกว่าต้นฉบับ
Dictionary coding and Huffman coding
- Dictionary coding, ใช้โดย ZIP และ PNG, สร้าง dictionary ของ byte sequences ที่ซ้ำแล้วแทนที่ทุก occurrence ด้วย index สั้น เหมาะกับ text และ program code, ที่ words และ patterns ซ้ำกัน
- Huffman coding ให้ short codes กับ common symbols และ long codes กับ rare ones, sehingga average code length ลดลง ใน "BANANA" A เป็น最常见的和最 frequently และได้รับ shortest code
- ทั้งสองเป็น lossless: decoder rebuilds ต้นฉบับ byte ต่อ byte
*การรวมโหนดที่มีความถี่ต่ำสุดสองโหนดซ้ำๆ สร้างต้นไม้; การอ่าน 0 ซ้ายและ 1 ขวา ลงไปยังแต่ละตัวอักษรทำให้ตัวอักษรที่พบบ่อยที่สุดมีรหัสสั้นที่สุด。
Huffman coding ลดขนาด bằng cách:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Huffman assign รหัสที่สั้นที่สุดให้กับสัญลักษณ์ที่พบบ่อยที่สุด ลดความยาวรหัสเฉลี่ย
จับคู่วิธีการบีบอัดแบบไม่สูญเสียข้อมูลแต่ละชนิดเข้ากับหลักการทำงาน
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ทั้งสามวิธีเป็นแบบไม่สูญเสียข้อมูล: ตัวถอดรหัสจะสร้างกลับเป็นไบต์เดิมทั้งหมด
Lossy methods
- Images (JPEG): detail เล็กน้อยและความแตกต่างของสีที่ตาแทบจะไม่สังเกตเห็นจะถูก drop
- Sound (MP3, AAC): pitches ที่เราฟังไม่ดี会被remove,连同quiet sounds被louder ones masked at the same time.
- Video: spatial compression ทำงานภายในแต่ละ frame, เหมือน JPEG, และ temporal compression เก็บส่วนใหญ่ frames เป็นเพียง differences จาก frame ก่อนหน้า, เนื่องจาก consecutive frames เกือบจะเหมือนกัน
การบีบอัดตามเวลาของวิดีโอทำงานโดย:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การบีบอัดตามเวลาระบุว่าแต่ละเฟรมแตกต่างจากเฟรมก่อนหน้าอย่างไร เนื่องจากภาพส่วนใหญ่คงที่ระหว่างเฟรม (การบีบอัดตามพื้นที่จัดการรายละเอียดภายในเฟรม)
ตัวอย่างวิธีทำ: ไฟล์แต่ละประเภทถูกบีบอัดอย่างไร
- Text file: dictionary และ Huffman coding เปลี่ยนคำซ้ำและตัวอักษรที่พบบ่อยเป็น short codes. ต้องคง lossless ไว้, เพราะการเปลี่ยน character หนึ่งตัวเปลี่ยนความหมาย
- Bitmap image: RLE สำหรับ runs ของ identical pixels ใน icons และ diagrams; lossy JPEG สำหรับ photographs; หรือลด colour depth หรือ resolution, ซึ่งเป็น lossy เช่นกัน
- Vector graphic: drawing list มีขนาดเล็กอยู่แล้ว. ลบ drawing objects ที่ไม่จำเป็นออก, เก็บ coordinates เป็นทศนิยมน้อยลง, หรือใช้วิธี lossless เช่น ZIP กับไฟล์
- Sound file: lossy MP3 หรือ AAC removesสิ่งที่หูฟังไม่ได้; ลด sampling rate หรือ resolution ก็เป็น lossy; formats lossless เก็บทุก sample และหดขนาดได้น้อยกว่ามาก
ไฟล์กราฟิกเวกเตอร์สามารถทำให้เล็กลงได้อย่างไร? เลือก ทุก ข้อที่ถูกต้อง
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ไฟล์เวกเตอร์คือรายการวาด ไม่ใช่พิกเซล จึงไม่มีค่าความลึกสี ความลึกสีเป็นของคุณสมบัติของภาพbitmap
Why streaming must be lossy
- Raw HD video มี gigabytes ต่อนาที, และการเชื่อมต่อ home มี megabits ต่อวินาทีไม่กี่兆
- Lossless compression กับ video อาจ achieves factor ของสอง, ห่างไกลจากพอ,ดังนั้นpicture จะหยุด buffering ต่อเนื่อง
- Lossy compression achieves factor ของร้อยหรือมากกว่า bằng cách discarding detail ที่ผู้ชมไม่สังเกตเห็นในความเร็วปกติ. Reason ชี้ถึง bandwidth และ data rate, ไม่ใช่แค่ "มันเล็กลง"
ทำไมการสตรีมวิดีโอแบบเรียลไทม์จึงใช้การบีบอัดแบบสูญเสียข้อมูล?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
วิดีโอ HD แบบดิบมีขนาดกิกabytes ต่อนาที การบีบอัดแบบสูญเสียข้อมูลเพียงอย่างเดียวที่หดขนาดได้พอสำหรับการสตรีมแบบเรียลไทม์โดยไม่สะดุด
คะแนนที่หลุดหายไป
- Lossless แปลว่า recover ต้นฉบับได้ ครบถ้วน; lossy แปลว่า ไม่สามารถ. "Lossy loses quality" ลืมไปว่าข้อมูลหายไปถาวร
- RLE สามารถทำให้ noisy file ใหญ่ขึ้น. บอกว่าทำงานได้ดีที่ไหนและไม่ดีที่ไหน
- Video compression เป็น spatial และ temporal; temporal เก็บ differences ระหว่าง frames
- คำตอบ "justify" เชื่อมต่อ method เข้ากับการใช้งาน: ความแม่นยำสำหรับบัญชีและ medical images, ขนาดสำหรับ streaming และ phone galleries
คุณเข้าใจแล้ว
- compression ประหยัด storage และ bandwidth; lossless recover ต้นฉบับได้ครบถ้วน, lossy ลบข้อมูลออกไปอย่างถาวร
- lossless methods: RLE (value และ count, ดีกับ runs, แย่กับ noise), dictionary coding (repeated sequences เป็น short indices), Huffman coding (short codes สำหรับ common symbols)
- lossy methods drop สิ่งที่ตาหรือหูพลาด; video เพิ่ม spatial ภายใน frame และ temporal ระหว่าง frames
- justify จากการใช้งาน: exact data แปลว่า lossless, limited bandwidth สำหรับ streaming แปลว่า lossy