Wikipédia

„Veszteségmentes tömörítés” változatai közötti eltérés

Laptörténet interaktív böngészése
[nem ellenőrzött változat][nem ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Syp (vitalap | szerkesztései)
járőrök
89 988 szerkesztés
Syp (vitalap | szerkesztései)
járőrök
89 988 szerkesztés
66. sor:
*[[H.264/MPEG-4 AVC]]
 
== A veszteségmentes tömörítés bizonyos fájlok méretét csak ''megnövelni'' tudja ==
{{leford}}▼
<!--▼
 
A veszteségmentes tömörítés nem tud valamilyen tömörítési arányt garantálni minden lehetséges bemeneti adatra. Más szavakkal kifejezve, bármely (veszteségmentes) adattömörítési algoritmus esetében lesz olyan bemeneti adathalmaz, aminek a méretét az algoritmus nem képes csökkenteni. Ez könnyen belátható elemi matematikai eszköz segítségével ([[kombinatorika|megszámlálással]]), a következőképpen:
== Lossless data compression must always make some files ''longer'' ==
Lossless data compression algorithms cannot guarantee compression for all input data sets. In other words, for any (lossless) data compression algorithm, there will be an input data set that does not get smaller when processed by the algorithm. This is easily proven with elementary mathematics using a [[counting argument]], as follows:
 
*Tekintsünk minden fájlt valamilyen tetszőleges hosszúságú bitsorozatként
*Assume that each file is represented as a string of bits of some arbitrary length.
*Tegyük fel, hogy van egy tömörítési algoritmus, ami minden fájlt átalakít egy másik, az eredetinél ''nem hosszabb'' fájllá, és hogy legalább egy fájlt az eredetinél kisebb méretre fog összenyomni.
*Suppose that there is a compression algorithm that transforms every file into a distinct file which is no longer than the original file, and that at least one file will be compressed into something that is shorter than itself.
*LetLegyen <math>M</math> bea thelegkisebb leastolyan numberszám, such that there is aahol fileaz <math>FM</math> withbit lengthhosszúságú <math>MF</math> bitsfájl thatrövidebbre compressesnyomódik to something shorterössze. LetLegyen <math>N</math> be the length (in bits) of the compressed version ofaz <math>F</math> fájl tömörített változatának a hossza, bitben megadva.
 
▲{{leford}}
▲<!--
*Because <math>N<M</math>, '''every''' file of length <math>N</math> keeps its size during compression. There are <math>2^N</math> such files. Together with <math>F</math>, this makes <math>2^N+1</math> files which all compress into one of the <math>2^N</math> files of length <math>N</math>.
*But <math>2^N</math> is smaller than <math>2^N+1</math>, so there must be some file of length <math>N</math> which is simultaneously the output of the compression function on two different inputs. That file cannot be decompressed reliably (which of the two originals should that yield?), which contradicts the assumption that the algorithm was lossless.
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Veszteségmentes_tömörítés”