การบีบอัดแบบไม่สูญเสีย

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

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

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

การบีบอัดข้อมูลแบบไม่สูญเสียข้อมูลถูกนำมาใช้ในหลายแอปพลิเคชัน ตัวอย่างเช่น ใช้ใน รูปแบบ ไฟล์ZIPและในเครื่องมือGNU gzip นอกจากนี้ยังมักใช้เป็นส่วนประกอบในเทคโนโลยีการบีบอัดข้อมูลที่สูญหาย (เช่น การประมวลผลล่วงหน้า สเตอริโอร่วมกลาง/ด้านข้าง แบบไม่สูญเสีย โดย ตัวเข้ารหัส MP3และตัวเข้ารหัสเสียงที่สูญเสียอื่นๆ) [2]

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

เทคนิค

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

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

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

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

มัลติมีเดีย

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

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

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

ประเด็นทางกฎหมายในอดีต

วิธีการเหล่านี้หลายวิธีถูกนำไปใช้ในโอเพ่นซอร์สและเครื่องมือที่เป็นกรรมสิทธิ์ โดยเฉพาะ LZW และตัวแปรต่างๆ อัลกอริธึมบางตัวได้รับการจดสิทธิบัตรในสหรัฐอเมริกาและประเทศอื่น ๆ และการใช้งานทางกฎหมายนั้นจำเป็นต้องได้รับใบอนุญาตจากผู้ถือสิทธิบัตร เนื่องจากสิทธิบัตรเกี่ยวกับ การบีบอัด LZW บางประเภท และโดยเฉพาะอย่างยิ่งแนวทางปฏิบัติด้านลิขสิทธิ์โดยผู้ถือสิทธิบัตร Unisys ซึ่งนักพัฒนาจำนวนมากพิจารณาว่าไม่เหมาะสม ผู้เสนอโอเพ่นซอร์สบางรายจึงสนับสนุนให้ผู้คนหลีกเลี่ยงการใช้ Graphics Interchange Format (GIF) สำหรับการบีบอัดไฟล์ภาพนิ่งเพื่อสนับสนุนPortable กราฟิกเครือข่าย (PNG) ซึ่งรวมอัลกอริธึมการยุบแบบLZ77เข้ากับตัวกรองการทำนายเฉพาะโดเมนที่เลือกไว้ อย่างไรก็ตาม สิทธิบัตรของ LZW หมดอายุเมื่อวันที่ 20 มิถุนายน พ.ศ. 2546 [3]

เทคนิคการบีบอัดแบบไม่สูญเสียข้อมูลจำนวนมากที่ใช้สำหรับข้อความยังทำงานได้ดีพอสมควรสำหรับภาพที่จัดทำดัชนีไว้แต่มีเทคนิคอื่นๆ ที่ใช้ไม่ได้กับข้อความทั่วไปซึ่งมีประโยชน์สำหรับภาพบางภาพ (โดยเฉพาะบิตแมปธรรมดา) และเทคนิคอื่นๆ ที่ใช้ประโยชน์จากลักษณะเฉพาะ ลักษณะของภาพ (เช่น ปรากฏการณ์ทั่วไปของพื้นที่ 2 มิติที่ต่อเนื่องกันซึ่งมีโทนสีคล้ายคลึงกัน และความจริงที่ว่าภาพสีมักจะมีความเหนือกว่าในช่วงสีที่จำกัด เกินกว่าที่แสดงในปริภูมิสี)

ตามที่กล่าวไว้ก่อนหน้านี้ การบีบอัดเสียงแบบไม่สูญเสียข้อมูลเป็นพื้นที่ที่ค่อนข้างพิเศษ อัลกอริธึมการบีบอัดเสียงแบบไม่สูญเสียสามารถใช้ประโยชน์จากรูปแบบการทำซ้ำที่แสดงโดยลักษณะคล้ายคลื่นของข้อมูล‍ — ‍ โดย พื้นฐานแล้ว ใช้ แบบจำลอง การถดถอยอัตโนมัติเพื่อทำนายค่า "ถัดไป" และเข้ารหัสความแตกต่าง (หวังว่าจะเล็กน้อย) ระหว่างค่าที่คาดหวังกับค่าจริง ข้อมูล. หากความแตกต่างระหว่างข้อมูลที่คาดการณ์กับข้อมูลจริง (เรียกว่าข้อผิดพลาด ) มีแนวโน้มที่จะน้อย ค่าความแตกต่างบางอย่าง (เช่น 0, +1, −1 ฯลฯ ในค่าตัวอย่าง) จะเกิดขึ้นบ่อยมาก ซึ่งสามารถใช้ประโยชน์ได้โดยการเข้ารหัสข้อมูลเหล่านั้น ในบิตเอาท์พุตไม่กี่บิต

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

วิธีการ

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

อัลกอริธึมการบีบอัดแบบไม่สูญเสียข้อมูลที่พบบ่อยที่สุดบางรายการมีดังต่อไปนี้

จุดประสงค์ทั่วไป

เสียง

กราฟิกแรสเตอร์

  • AVIF – รูปแบบไฟล์ภาพ AV1
  • FLIF – รูปแบบภาพ Lossless ฟรี
  • HEIF – รูปแบบไฟล์ภาพที่มีประสิทธิภาพสูง (การบีบอัดแบบไม่สูญเสียข้อมูลหรือสูญเสียข้อมูล โดยใช้HEVC )
  • ILBM – (การบีบอัด RLE แบบไม่สูญเสียของ อิมเมจ Amiga IFF )
  • JBIG2 – (การบีบอัดภาพขาวดำแบบไม่สูญเสียหรือสูญเสีย)
  • JPEG 2000 – (รวมถึงวิธีการบีบอัดแบบไม่สูญเสียข้อมูลผ่าน Le Gall–Tabatabai 5/3 [4] [5] [6] การแปลงเวฟเล็ตจำนวนเต็มแบบย้อนกลับได้)
  • JPEG-LS – (มาตรฐานการบีบอัดแบบไม่สูญเสียข้อมูล/เกือบสูญเสีย)
  • JPEG XL – (การบีบอัดแบบไม่สูญเสียหรือสูญเสีย)
  • JPEG XR – เดิมชื่อWMPhotoและHD Photoมีวิธีการบีบอัดแบบไม่สูญเสียข้อมูล
  • LDCTการแปลงโคไซน์แบบไม่ต่อเนื่องแบบ Lossless [7] (8)
  • PCX – PiCture eXchange
  • PDF – รูปแบบเอกสารพกพา (การบีบอัดแบบไม่สูญเสียข้อมูลหรือการสูญเสียข้อมูล)
  • QOI – รูปแบบภาพค่อนข้างโอเค
  • PNG – กราฟิกเครือข่ายแบบพกพา
  • ทีจีเอ – ทรูวิชั่น ทีจีเอ
  • TIFF – รูปแบบไฟล์ภาพแท็ก (การบีบอัดแบบไม่สูญเสียข้อมูลหรือสูญเสียข้อมูล)
  • WebP – (การบีบอัดภาพ RGB และ RGBA แบบไม่สูญเสียหรือสูญเสีย)

กราฟิก 3 มิติ

  • OpenCTM – การบีบอัดตาข่ายสามเหลี่ยม 3 มิติโดยไม่สูญเสียคุณภาพ

วีดีโอ

ดูรายการตัวแปลงสัญญาณวิดีโอแบบไม่สูญเสียข้อมูล

การเข้ารหัส

Cryptosystemsมักจะบีบอัดข้อมูล ("ข้อความธรรมดา") ก่อนการเข้ารหัสเพื่อเพิ่มความปลอดภัย เมื่อนำไปใช้อย่างถูกต้อง การบีบอัดจะเพิ่มระยะห่างแบบยูนิซิตี้ อย่างมาก โดยการลบรูปแบบที่อาจเอื้อต่อการเข้ารหัส [9]อย่างไรก็ตาม อัลกอริธึมการบีบอัดแบบไม่สูญเสียข้อมูลทั่วไปจำนวนมากจะสร้างส่วนหัว ตัวห่อ ตาราง หรือเอาต์พุตที่คาดเดาได้อื่นๆ ซึ่งอาจจะทำให้การเข้ารหัสง่ายขึ้นแทน ดังนั้น cryptosystems ต้องใช้อัลกอริธึมการบีบอัดซึ่งเอาต์พุตไม่มีรูปแบบที่คาดเดาได้เหล่านี้

พันธุศาสตร์และจีโนมิกส์

อัลกอริธึมการบีบอัดทางพันธุศาสตร์ (เพื่อไม่ให้สับสนกับอัลกอริธึมทางพันธุกรรม ) เป็นอัลกอริธึมแบบไม่สูญเสียรุ่นล่าสุดที่บีบอัดข้อมูล (โดยทั่วไปคือลำดับของนิวคลีโอไทด์) โดยใช้ทั้งอัลกอริธึมการบีบอัดแบบธรรมดาและอัลกอริธึมเฉพาะที่ปรับให้เข้ากับข้อมูลทางพันธุกรรม ในปี 2012 ทีมนักวิทยาศาสตร์จากมหาวิทยาลัย Johns Hopkins ตีพิมพ์อัลกอริธึมการบีบอัดทางพันธุกรรมครั้งแรกที่ไม่ต้องใช้ฐานข้อมูลทางพันธุกรรมภายนอกสำหรับการบีบอัด HAPZIPPER ได้รับการปรับแต่งสำหรับ ข้อมูล HapMapและบรรลุการบีบอัดมากกว่า 20 เท่า (ขนาดไฟล์ลดลง 95%) ให้การบีบอัดที่ดีกว่า 2 ถึง 4 เท่าเร็วกว่าโปรแกรมอรรถประโยชน์การบีบอัดข้อมูลทั่วไปชั้นนำมาก [10]

อัลกอริธึมการบีบอัดลำดับจีโนมหรือที่เรียกว่าเครื่องอัดลำดับ DNA สำรวจข้อเท็จจริงที่ว่าลำดับ DNA มีคุณสมบัติเฉพาะตัว เช่น การทำซ้ำแบบกลับด้าน คอมเพรสเซอร์ที่ประสบความสำเร็จมากที่สุดคือ XM และ GeCo [11]สำหรับยูคาริโอต XM จะดีกว่าเล็กน้อยในอัตราส่วนการบีบอัด แม้ว่าสำหรับลำดับที่ใหญ่กว่า 100 MB ข้อกำหนดในการคำนวณก็ทำไม่ได้ในทางปฏิบัติ

ปฏิบัติการได้

ไฟล์ปฏิบัติการที่ขยายในตัวจะมีแอปพลิเคชันที่บีบอัดและตัวขยายการบีบอัด เมื่อดำเนินการ ตัวขยายการบีบอัดจะขยายขนาดอย่างโปร่งใสและรันแอปพลิเคชันดั้งเดิม โดยเฉพาะอย่างยิ่งมักใช้ใน การ เขียน โค้ด สาธิตซึ่งมีการแข่งขันสำหรับการสาธิตที่มีการจำกัดขนาดที่เข้มงวด โดยมีขนาดเล็กเพียง1k การบีบอัดประเภทนี้ไม่ได้จำกัดอยู่เพียงไฟล์ปฏิบัติการแบบไบนารีเท่านั้น แต่ยังใช้กับสคริปต์ เช่นJavaScriptได้ ด้วย

เกณฑ์มาตรฐาน

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

Matt Mahoney ในหนังสือเล่มเล็ก Data Compression Explainedฉบับเดือนกุมภาพันธ์ 2010 ยังแสดงรายการต่อไปนี้เพิ่มเติม: [12]

  • Calgary Corpusย้อนหลังไปถึงปี 1987 ไม่มีการใช้กันอย่างแพร่หลายอีกต่อไปเนื่องจากมีขนาดเล็ก Matt Mahoney ดูแล Calgary Compression Challenge ซึ่งสร้างและดูแลตั้งแต่วันที่ 21 พฤษภาคม 1996 ถึง 21 พฤษภาคม 2016 โดย Leonid A. Broukhis
  • เกณฑ์มาตรฐานการบีบอัดข้อความขนาดใหญ่[13]และHutter Prize ที่คล้ายกัน ทั้งคู่ใช้ชุดข้อมูลWikipedia XML UTF-8 ที่ถูกตัดทอนแล้ว
  • เกณฑ์มาตรฐานการบีบอัดทั่วไป[14]ดูแลโดย Matt Mahoney ทดสอบการบีบอัดข้อมูลที่สร้างโดยเครื่องทัวริงแบบ สุ่ม
  • Sami Runsas (ผู้เขียน NanoZip) คงระดับการบีบอัด ซึ่งเป็นเกณฑ์มาตรฐานที่คล้ายกับการทดสอบการบีบอัดไฟล์สูงสุดหลายไฟล์ แต่มีข้อกำหนดด้านความเร็วขั้นต่ำ มีเครื่องคิดเลขที่ให้ผู้ใช้สามารถชั่งน้ำหนักความสำคัญของความเร็วและอัตราส่วนการบีบอัดได้ โปรแกรมยอดนิยมมีความแตกต่างกันพอสมควรเนื่องจากความต้องการความเร็ว ในเดือนมกราคม 2010 โปรแกรมยอดนิยมคือ NanoZip ตามด้วยFreeArc , CCM, flashzip และ7- Zip
  • เกณฑ์มาตรฐาน Monster of Compression โดย Nania Francesco Antonio ทดสอบการบีบอัดข้อมูลสาธารณะขนาด 1Gb โดยจำกัดเวลา 40 นาที ในเดือนธันวาคม พ.ศ. 2552 ผู้จัดเก็บอันดับสูงสุดคือ NanoZip 0.07a และโปรแกรมบีบอัดไฟล์เดี่ยวอันดับสูงสุดคือ ccmx 1.30c

เว็บไซต์การให้คะแนนการบีบอัดเผยแพร่แผนภูมิสรุปของ "ชายแดน" ในอัตราส่วนและเวลาการบีบอัด [15]

เครื่องมือวิเคราะห์การบีบอัด[16]เป็นแอปพลิเคชัน Windows ที่ช่วยให้ผู้ใช้สามารถเปรียบเทียบคุณลักษณะประสิทธิภาพของการใช้งานสตรีมมิ่งของ LZF4, Deflate, ZLIB, GZIP, BZIP2 และ LZMA โดยใช้ข้อมูลของตนเอง โดยสร้างการวัดและแผนภูมิที่ผู้ใช้สามารถเปรียบเทียบความเร็วการบีบอัด ความเร็วในการคลายการบีบอัด และอัตราส่วนการบีบอัดของวิธีการบีบอัดต่างๆ และเพื่อตรวจสอบว่าระดับการบีบอัด ขนาดบัฟเฟอร์ และการดำเนินการฟลัชชิ่งส่งผลต่อผลลัพธ์อย่างไร

ข้อจำกัด

อัลกอริธึมการบีบอัดข้อมูลแบบไม่สูญเสียข้อมูลไม่สามารถรับประกันการบีบอัดสำหรับชุดข้อมูลอินพุตทั้งหมดได้ กล่าวอีกนัยหนึ่ง สำหรับอัลกอริธึมการบีบอัดข้อมูลแบบไม่สูญเสียใดๆ จะมีชุดข้อมูลอินพุตที่ไม่เล็กลงเมื่อประมวลผลโดยอัลกอริธึม และสำหรับอัลกอริธึมการบีบอัดข้อมูลแบบไม่สูญเสียใดๆ ที่ทำให้ไฟล์เล็กลงอย่างน้อยหนึ่งไฟล์ ก็จะมีอย่างน้อยหนึ่งไฟล์ ไฟล์ที่ทำให้มีขนาดใหญ่ขึ้น สิ่งนี้สามารถพิสูจน์ได้อย่างง่ายดายด้วยคณิตศาสตร์ระดับประถมศึกษาโดยใช้อาร์กิวเมนต์การนับที่เรียกว่าหลักการรูนกพิราบดังต่อไปนี้: [17] [18]

  • สมมติว่าแต่ละไฟล์จะแสดงเป็นสตริงของบิตที่มีความยาวตามต้องการ
  • สมมติว่ามีอัลกอริธึมการบีบอัดที่แปลงทุกไฟล์ให้เป็นไฟล์เอาต์พุตที่มีความยาวไม่เกินไฟล์ต้นฉบับ และอย่างน้อยหนึ่งไฟล์จะถูกบีบอัดเป็นไฟล์เอาต์พุตที่สั้นกว่าไฟล์ต้นฉบับ
  • ให้Mเป็นจำนวนที่น้อยที่สุดเพื่อให้มีไฟล์Fที่มีความยาวMบิตที่บีบอัดให้สั้นลง ให้N เป็นความ ยาว(เป็นบิต) ของเวอร์ชันบีบอัดของF
  • เนื่องจากN < M ทุกไฟล์ที่มีความยาวNจะคงขนาดไว้ระหว่างการบีบอัด มีไฟล์ดังกล่าวได้ 2 N เมื่อใช้ร่วมกับFสิ่งนี้จะสร้างไฟล์ 2 N +1 ที่ทั้งหมดบีบอัดเป็นหนึ่งในไฟล์ความยาว 2 N N
  • แต่ 2 Nนั้นเล็กกว่า 2 N +1 ดังนั้นตามหลักการของรูนกพิราบ จะต้องมีไฟล์บางไฟล์ที่มีความยาวNซึ่งเป็นเอาต์พุตของฟังก์ชันการบีบอัดบนอินพุตที่ต่างกันสองตัวพร้อมกัน ไฟล์นั้นไม่สามารถแตกไฟล์ได้อย่างน่าเชื่อถือ (ต้นฉบับใดในสองต้นฉบับที่ควรให้ผลนั้น) ซึ่งขัดแย้งกับสมมติฐานที่ว่าอัลกอริทึมไม่มีการสูญเสีย
  • ดังนั้นเราจึงต้องสรุปว่าสมมติฐานเดิมของเรา (ฟังก์ชันการบีบอัดทำให้ไม่มีไฟล์อีกต่อไป) ไม่จำเป็นต้องเป็นจริง

อัลกอริธึมการบีบอัดที่ใช้งานได้จริงส่วนใหญ่จัดให้มีเครื่องมือ "escape" ที่สามารถปิดการเข้ารหัสปกติสำหรับไฟล์ที่จะมีความยาวมากขึ้นจากการเข้ารหัส ตามทฤษฎีแล้ว จำเป็นต้องใช้บิตเพิ่มเติมเพียงบิตเดียวเพื่อบอกตัวถอดรหัสว่าการเข้ารหัสปกติถูกปิดสำหรับอินพุตทั้งหมดแล้ว อย่างไรก็ตาม อัลกอริธึมการเข้ารหัสส่วนใหญ่ใช้ไบต์เต็มอย่างน้อยหนึ่งไบต์ (และโดยทั่วไปจะมากกว่าหนึ่งไบต์) เพื่อจุดประสงค์นี้ ตัวอย่างเช่น ไฟล์ บีบอัดแบบยุบไม่จำเป็นต้องขยายเกิน 5 ไบต์ต่ออินพุต 65,535 ไบต์

ในความเป็นจริง ถ้าเราพิจารณาไฟล์ที่มีความยาว N หากไฟล์ทั้งหมดมีความเป็นไปได้เท่ากัน ดังนั้นสำหรับการบีบอัดแบบไม่สูญเสียข้อมูลใดๆ ที่ลดขนาดของไฟล์บางไฟล์ ความยาวที่คาดหวังของไฟล์บีบอัด (โดยเฉลี่ยของไฟล์ที่เป็นไปได้ทั้งหมดที่มีความยาว N) จะต้องจำเป็น มากกว่าN [19] ดังนั้นถ้าเราไม่รู้อะไรเกี่ยวกับคุณสมบัติของข้อมูลที่เรากำลังบีบอัด เราก็อาจ จะไม่บีบอัดมันเลย อัลกอริธึมการบีบอัดแบบไม่สูญเสียข้อมูลจะมีประโยชน์ก็ต่อเมื่อเรามีแนวโน้มที่จะบีบอัดไฟล์บางประเภทมากกว่าประเภทอื่น จากนั้นอัลกอริทึมสามารถออกแบบให้บีบอัดข้อมูลประเภทเหล่านั้นได้ดีขึ้น

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

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

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

เป็นไปไม่ได้เลยที่จะสร้างอัลกอริทึมที่สามารถบีบอัดข้อมูลใดๆ โดยไม่สูญเสียคุณภาพได้ แม้ว่าจะมีข้อกล่าวอ้างมากมายตลอดหลายปีที่ผ่านมาของบริษัทต่างๆ ที่ประสบความสำเร็จ "การบีบอัดที่สมบูรณ์แบบ" โดยที่หมายเลขNของบิตสุ่มสามารถบีบอัดให้เป็นN  - 1 บิตได้เสมอ การกล่าวอ้างประเภทนี้สามารถละทิ้งได้อย่างปลอดภัยโดยไม่ต้องพิจารณารายละเอียดเพิ่มเติมใดๆ ที่เกี่ยวข้องกับ รูปแบบการบีบอัดที่อ้างว่า อัลกอริธึมดังกล่าวขัดแย้งกับกฎพื้นฐานของคณิตศาสตร์ เพราะหากมีอยู่จริง ก็สามารถนำมาใช้ซ้ำๆ เพื่อลดไฟล์ใดๆ ให้มีความยาว 1 โดยไม่สูญเสียคุณภาพได้[18]

ในทางกลับกัน มันได้รับการพิสูจน์แล้ว[21]ว่าไม่มีอัลกอริธึมในการพิจารณาว่าไฟล์นั้นไม่สามารถบีบอัดได้หรือไม่ในแง่ของความซับซ้อนของ Kolmogorov ดังนั้นจึงเป็นไปได้ว่าไฟล์ใด ๆ แม้ว่าจะดูเหมือนสุ่มก็ตาม อาจถูกบีบอัดอย่างมีนัยสำคัญ แม้จะรวมถึงขนาดของตัวขยายการบีบอัดด้วยก็ตาม ตัวอย่างคือตัวเลขของค่าคงที่ทางคณิตศาสตร์piซึ่งปรากฏแบบสุ่มแต่สามารถสร้างขึ้นได้ด้วยโปรแกรมขนาดเล็กมาก อย่างไรก็ตาม แม้ว่าจะไม่สามารถระบุได้ว่าไฟล์ใดไฟล์หนึ่งไม่สามารถบีบอัดได้หรือไม่ แต่ทฤษฎีบทง่ายๆ เกี่ยวกับสตริงที่ไม่สามารถบีบอัดได้แสดงให้เห็นว่ามากกว่า 99% ของไฟล์ที่มีความยาวใดๆ ก็ตามไม่สามารถบีบอัดได้มากกว่าหนึ่งไบต์ (รวมถึงขนาดของตัวขยายการบีบอัด)

พื้นหลังทางคณิตศาสตร์

โดยสรุป อัลกอริธึมการบีบอัดสามารถดูได้เป็นฟังก์ชันในลำดับ (ปกติของออคเต็ต) การบีบอัดจะสำเร็จหากลำดับผลลัพธ์สั้นกว่าลำดับดั้งเดิม (และคำแนะนำสำหรับแผนผังการบีบอัด) เพื่อให้อัลกอริธึมการบีบอัดไม่สูญเสียข้อมูล แมปการบีบอัดจะต้องสร้างลำดับบิตแบบ "ธรรมดา" ถึง "บีบอัด" หลักการของรูนกพิราบห้ามไม่ให้มีการบิดเบี้ยวระหว่างการรวบรวมลำดับที่มีความยาวNและเซตย่อยใดๆ ของการรวบรวมลำดับที่มีความยาวN −1 ดังนั้นจึงเป็นไปไม่ได้ที่จะสร้างอัลกอริธึมแบบไม่สูญเสียซึ่งจะลดขนาดของลำดับอินพุตที่เป็นไปได้ทั้งหมด [22]

จุดประยุกต์ในทฤษฎีการบีบอัดจริง

ผู้ออกแบบอัลกอริธึมการบีบอัดที่แท้จริงยอมรับว่ากระแสข้อมูลเอนโทรปีสูงไม่สามารถบีบอัดได้ และด้วยเหตุนี้จึงได้รวมสิ่งอำนวยความสะดวกในการตรวจจับและจัดการกับสภาวะนี้ไว้ด้วย วิธีการตรวจจับที่ชัดเจนคือการใช้อัลกอริธึมการบีบอัดแบบ Raw และทดสอบว่าเอาต์พุตมีขนาดเล็กกว่าอินพุตหรือไม่ บางครั้ง การตรวจ จับทำได้โดยการวิเคราะห์พฤติกรรม ตัวอย่างเช่น แอปพลิเคชันการบีบอัดอาจพิจารณาไฟล์ที่มีชื่อลงท้ายด้วย ".zip", ".arj" หรือ ".lha" ที่ไม่สามารถบีบอัดได้โดยไม่มีการตรวจจับที่ซับซ้อนกว่านี้ วิธีทั่วไปในการจัดการกับสถานการณ์นี้คือการอ้างอิงอินพุต หรือส่วนที่ไม่สามารถบีบอัดของอินพุตในเอาต์พุต เพื่อลดค่าใช้จ่ายในการบีบอัดให้เหลือน้อยที่สุด ตัวอย่างเช่น รูปแบบข้อมูล zipระบุ 'วิธีการบีบอัด' ของ 'จัดเก็บ' สำหรับไฟล์อินพุตที่ถูกคัดลอกไปยังไฟล์เก็บถาวรคำต่อคำ [23]

ความท้าทายล้านหลักสุ่ม

เพื่อตอบสนองต่อคำกล่าวอ้างของอัลกอริธึมการบีบอัด "เวทย์มนตร์" ที่ปรากฏใน comp.compression ได้สร้างไฟล์ไบนารี่ขนาด 415,241 ไบต์ที่มีเนื้อหาเอนโทรปิกสูง และออกการท้าทายสาธารณะเป็นเงิน 100 ดอลลาร์แก่ใครก็ตามที่จะเขียนโปรแกรมที่ร่วมกับข้อมูลอินพุตของมัน จะเล็กกว่าข้อมูลไบนารีที่เขาให้มา แต่ก็สามารถสร้างขึ้นใหม่ได้โดยไม่มีข้อผิดพลาด ความท้าทายที่ คล้าย กันซึ่งมีรางวัล 5,000 ดอลลาร์ออกโดย Mike Goldman [25]

ดูสิ่งนี้ด้วย

อ้างอิง

  1. "หน่วยที่ 4 ห้องปฏิบัติการ 4: การแสดงข้อมูลและการบีบอัด, หน้า 6". bjc.edc.org . สืบค้นเมื่อวันที่ 9 เมษายน 2022 .
  2. ไพรซ์, แอนดี้ (3 มีนาคม พ.ศ. 2565) "สตรีมมิ่งแบบ Lossless – อนาคตของเสียงความละเอียดสูง" ออดิโอ มีเดีย อินเตอร์เนชั่นแนล
  3. ^ "ข้อมูลสิทธิบัตร LZW" เกี่ยวกับยูนิซิยูนิซิส. เก็บถาวรจากต้นฉบับเมื่อวันที่ 2 มิถุนายน 2552
  4. ซัลลิแวน, แกรี (8–12 ธันวาคม พ.ศ. 2546) "ลักษณะทั่วไปและข้อควรพิจารณาในการออกแบบสำหรับการเข้ารหัสวิดีโอย่านความถี่ย่อยชั่วคราว" ไอทู-ที . กลุ่มผู้เชี่ยวชาญด้านการเข้ารหัสวิดีโอ สืบค้นเมื่อวันที่ 13 กันยายน 2019 .
  5. อันเซอร์, ม.; บลู ต. (2003) "คุณสมบัติทางคณิตศาสตร์ของตัวกรองเวฟเล็ต JPEG2000" ( PDF) ธุรกรรม IEEE ในการประมวลผลภาพ 12 (9): 1080–1090. Bibcode :2003ITIP...12.1080U. ดอย :10.1109/TIP.2003.812329. PMID  18237979. S2CID  2765169. เก็บถาวรจากต้นฉบับ(PDF)เมื่อวันที่ 13 ตุลาคม 2019
  6. โบวิค, อลัน ซี. (2009) คู่มือสำคัญในการประมวลผลวิดีโอ สำนักพิมพ์วิชาการ . พี 355. ไอเอสบีเอ็น 9780080922508.
  7. อาเหม็ด, นาซีร์ ; มานยัม, กิริธาร์ ดี.; มาโกตรา, นีราช (17 เมษายน 2538) โรดริเกซ, อาร์ตูโร เอ.; ซาฟราเน็ก, โรเบิร์ต เจ.; เดลป์, เอ็ดเวิร์ด เจ. (บรรณาธิการ). "รูปแบบที่ใช้ DCT สำหรับการบีบอัดภาพแบบไม่สูญเสียข้อมูล" การบีบอัดวิดีโอดิจิทัล: อัลกอริทึมและเทคโนโลยี 2538 สมาคมระหว่างประเทศเพื่อทัศนศาสตร์และโฟโตนิกส์ 2419 : 474–478. รหัสสินค้า :1995SPIE.2419..474M. ดอย :10.1117/12.206386. S2CID  13894279.
  8. โคมัตสึ เค.; เซซากิ, คาโอรุ (1998) "การแปลงโคไซน์แบบไม่ต่อเนื่องแบบผันกลับได้" การดำเนินการของการประชุมนานาชาติ IEEE ว่าด้วยการประมวลผลเสียง คำพูด และสัญญาณ ปี 1998, ICASSP '98 (Cat. No.98CH36181 ) ฉบับที่ 3. หน้า 1769–1772 เล่ม 3. ดอย :10.1109/ICASSP.1998.681802. ไอเอสบีเอ็น 0-7803-4428-6. S2CID  17045923.
  9. อัลเฟรด เจ. เมเนเซส; พอล ซี. ฟาน ออร์ชอต; สกอตต์ เอ. แวนสโตน (16 ตุลาคม 2539) คู่มือการเข้ารหัสประยุกต์ ซีอาร์ซี เพรส. ไอเอสบีเอ็น 978-1-4398-2191-6.
  10. จันดา, ป.; เอลฮาอิก อี.; เบเดอร์, เจเอส (2012) "HapZipper: การแบ่งปันประชากร HapMap ง่ายขึ้น" กรดนิวคลี อิกRes 40 (20): 1–7. ดอย :10.1093/nar/gks709. PMC 3488212 . PMID22844100  . 
  11. ปราทาส ด.; ปินโญ่, เอเจ; เฟอร์ไรรา, PJSG (2016) "การบีบอัดลำดับจีโนมอย่างมีประสิทธิภาพ" การประชุมการบีบอัดข้อมูล(PDF ) สโนว์เบิร์ด, ยูทาห์{{cite book}}: CS1 maint: location missing publisher (link)
  12. แมตต์ มาฮอนี่ย์ (2010) "คำอธิบายการบีบอัดข้อมูล" (PDF ) หน้า 3–5.
  13. ^ "เกณฑ์มาตรฐานการบีบอัดข้อความขนาดใหญ่" mattmahoney.net _
  14. ^ "เกณฑ์มาตรฐานการบีบอัดทั่วไป" mattmahoney.net _
  15. ^ "บทสรุป". 1 กันยายน 2016 เก็บถาวรจากต้นฉบับเมื่อวันที่ 1 กันยายน 2016
  16. ^ "เครื่องมือวิเคราะห์การบีบอัด" เครื่องมือฟรี โนเอแม็กซ์ เทคโนโลยีส์
  17. ซายูด 2002, p. 41.
  18. ↑ อับ เบลล์, ทิม (28 กันยายน – 1 ตุลาคม พ.ศ. 2558) สารสนเทศในโรงเรียน หลักสูตร ความสามารถ และการแข่งขัน บันทึกการบรรยายทางวิทยาการคอมพิวเตอร์ ฉบับที่ 9378. สปริงเกอร์ . หน้า 8–9. ดอย :10.1007/978-3-319-25396-1. ไอเอสบีเอ็น 978-3-319-25396-1. S2CID  26313283 . สืบค้นเมื่อ 24 สิงหาคม 2021 . {{cite book}}: |journal=ละเว้น ( ช่วยด้วย )
  19. ^ "การบีบอัดแบบไม่สูญเสียข้อมูล - ภาพรวม | หัวข้อ ScienceDirect" www.sciencedirect.com . สืบค้นเมื่อวันที่ 30 ตุลาคม 2565 .
  20. ซายูด 2002, p. 38.
  21. หลี่ หมิง; วิตันยี, พอล (1993) ความรู้เบื้องต้นเกี่ยวกับความซับซ้อนของ Kolmogorov และการประยุกต์ นิวยอร์ก: สปริงเกอร์. พี 102. ไอเอสบีเอ็น 0-387-94053-7. ทฤษฎีบท 2.6 ฟังก์ชันนี้ไม่ใช่การเรียกซ้ำบางส่วน
  22. Joshi, Mark S. (18 มีนาคม 2558). "หลักการรังนกพิราบ". รูปแบบการพิสูจน์ สปริงเกอร์ . พี 21. ดอย :10.1007/978-3-319-16250-8_3. ไอเอสบีเอ็น 978-3-319-16250-8. S2CID  116983697 . สืบค้นเมื่อ 24 สิงหาคม 2021 .
  23. "ข้อกำหนดรูปแบบไฟล์ .ZIP" PKWARE, Inc.บทที่ V, ส่วน J
  24. เนลสัน, มาร์ก (20 มิถุนายน พ.ศ. 2549). "การท้าทายเลขสุ่มหลักล้านกลับมาอีกครั้ง"
  25. เครก, แพทริค. "การแข่งขันอัดเงิน 5,000 ดอลลาร์" สืบค้นเมื่อวันที่ 8 มิถุนายน 2552 .

อ่านเพิ่มเติม

ลิงค์ภายนอก

  • "รูปแบบการบีบอัด LZF" GitHub _ สืบค้นเมื่อวันที่ 17 ตุลาคม 2017 .
  • ฟามโด, นัม. "ทฤษฎีการบีบอัดข้อมูล". การบีบอัดข้อมูล เก็บถาวรจากต้นฉบับเมื่อวันที่ 8 พฤษภาคม 2016 . สืบค้นเมื่อวันที่ 17 ตุลาคม 2017 .
  • "การเปรียบเทียบที่ไม่สูญเสีย" ฐานความรู้ไฮโดรเจนออดิโอ 5 มกราคม 2558 . สืบค้นเมื่อวันที่ 17 ตุลาคม 2017 .
  • "รูปแบบเสียงที่ไม่สูญเสียและสูญเสียสำหรับเพลง" โบบูลัส เซ็นทรัล . 6 พฤศจิกายน พ.ศ. 2546 . สืบค้นเมื่อวันที่ 17 ตุลาคม 2017 .
  • "เกณฑ์มาตรฐานการบีบอัดภาพ" เก็บถาวรจากต้นฉบับเมื่อวันที่ 10 กุมภาพันธ์ 2013ภาพรวมของ
    • สิทธิบัตรสหรัฐอเมริกา #7,096,360 ถูกเก็บถาวรเมื่อวันที่ 2 กุมภาพันธ์ 2017 ที่Wayback Machine , "[a]n "วิธีการบีบอัดข้อมูลตามเวลาความถี่" ซึ่งสนับสนุนการบีบอัด การเข้ารหัส การบีบอัดข้อมูล และการถอดรหัส และการคงอยู่ของเลขฐานสองจำนวนมากผ่านความถี่ที่แต่ละความถี่ แสดงถึงหลายบิต"
Retrieved from "https://en.wikipedia.org/w/index.php?title=Lossless_compression&oldid=1200158278"