tömörítés és összenyomhatatlan fájlok

tömörítés és összenyomhatatlan fájlok

Az első személyi számítógép volt egy kis lemezes tároló. Ahhoz, hogy a fájlokat és programokat az egyik gépről a másikra, ezek rögzített floppy lemezek kis kapacitású. Memória hiányzott. Hiánya a memória természetesen vezetett, hogy vizsgálja meg annak módját, hogy a számítógép gazdaságos felvételt. Az egyik ilyen módszer volt, a tömörítést, vagy adattömörítést. Kiderült, hogy sok esetben nyújthat be, miután egy speciális programot, hogy sokkal kisebb méretűek. tömörítő program néven vált ismertté az archiváló. Ma már a példa egy furcsa történetet írja le részletesen, mint hasznos funkciókat minden felhasználó számára, mint a tömörítés a fájlok.

Természetesen felmerül a kérdés: miért most kell tömöríteni a fájlokat, ha az összes főbb műszaki jellemzőit két évente megduplázása személyi számítógépek? Memória a modern személyi számítógépek 128-512 megabájt lemezterület általában több tíz gigabájt. Úgy tűnik, hogy akkor nem különösebben aggódnia a fájl méretét.

A második ok az érdeklődés tömörítés, fájlátvitel e-mailben, és a letöltést internetes oldalak hang és grafikus információk. A kapacitás a normál internet vonal nem gyorsan küldeni nagyobb fájlokat, mint néhány megabájt, és így sok szerver egyszerűen nem teszi lehetővé a nagy fájlok vagy mesterségesen korlátozza a felhasználó az adatátviteli sebesség. Ezért tömörítés fájlok továbbra is érvényes.

Archivers csökkenti néhány fájlt a 5-10 alkalommal. Mivel a mi lehetséges annyira csökkenti a fájl méretét? Néhány fájl épülnek nem optimális szempontjából a hangerőt. Például egy közös archiváló tömöríteni nagy Microsoft Word fájlokat 5-6 alkalommal, és a kis majdnem tíz. Olvasni egy tömörített szöveges fájl, meg kell lazítani ugyanazt a programot.

Sok felhasználó először jött a zseniális ötlete -, hogy megpróbálja tömöríteni már megint tömörített fájlokat. Az első kísérlet kiábrándító - tömörített fájlok nem tömörített tovább, minden levéltár. Miért történik ez?

Az a tény, hogy a fájlok a számítógép memóriájában, amíg számokat. Számos adott hosszúságú, általában nem tudja pontosan közvetíteni a számos kisebb hosszúságú, még ha rövidebb csak egy számjegyet. Emiatt az egyetlen módja annak adattömörítés találni bennük valamilyen redundáns információt vagy mintákat. Redundáns információt el lehet távolítani, és minták kódolásához használt hasonló töredékek kevesebb adatforgalmat. Jelentős tömörítés audio fájlokat vált lehetővé, mert a felvett hang az átlagember fül nem tesz, vagy nem irritálja a veszteség egy részét a megbízható információk.

Amikor a program fájlok kezelése megfelelő, talált mintákat, kevés jelentős adatok eltávolítása, majd a második alkalommal volt ez a művelet nem lesz képes megtartani. Ezért, amikor a recompression fájl nem csökken. Furcsának tűnhet, de nincs felesleges információk és véletlenszerű adatokat, mint a rádiófrekvenciás zaj a felvételeken, ahol nincs adóállomások vagy eredményeként a program - a véletlenszám-generátor. A tény az, hogy egy sor valóban véletlenszerű számok archiváló nem találja szabályszerűségeket. Kiderül, hogy egy tömör enciklopédia, és ennek eredményeként fut Sportloto gép nem találja a redundáns információ Encyclopedia - tudás koncentrálódik, és a forgalomban Sport Lottó - hosszú sor véletlen számok.

Tehát az alapelv a tömörítés - a keresés a mintákat. A véletlenszerű minták nem állnak rendelkezésre adatok, ezért elméletileg tömöríteni őket teljesen lehetetlen. Összenyomhatatlan, abból a szempontból, információ elmélet - ez egy alapvető tulajdonsága egy sor véletlen számok. Azonban a tavasszal a tavalyi év volt a történet, amelyben ez a kijelentés volt kitéve súlyos tesztet. Ez a történet sokkal érdekesebb, hogy a főszereplő - nem egy tudós, de a leleményes amatőr, aki érti annak fontosságát, hogy nem csupán az alapelveket, hanem azt is, hogyan a szoftver végrehajtását. De fogunk beszélni mindent annak érdekében.

Internet - egy nagyon kényelmes környezetet kommunikációs szakemberek. Egymástól távol eső szakemberek a különböző országok megvitassák a saját területén. A web jól ismert hálózati hierarchia Usenet. Ez hozza össze több ezer vitafórumok különböző témákban. Ott van, és a csoport az úgynevezett COMP.COMPRESS. Ebben szakértői megvitatják tömörítés, azaz tömörítési információkat. Vegyen részt csoportos beszélgetések igényel jelentős képzést. Ezért alkalmi látogatók COMP.COMPRESS nem marad sokáig. Azonban időről időre valaki az újonnan felvetődött eljáró szakértők kompresszió körülbelül ugyanaz, mint a fizika örökmozgó projektek, és a történészek - Fomenko működik. Hagyományosan, a probléma az úgynevezett „csoda kompresszor”.

Ha beszélünk a veszteségmentes tömörítést, akkor már nem volt úttörő munkát. Az elmúlt alapvetően új algoritmust bezpoternogo kompressziós találták a 80-as években, és kevés használt, mert a nagy bonyolultságú. Ezen kívül, mint már említettük, bizonyíték van arra, hogy általában nem lehet összenyomni, veszteség nélkül. Ez egyrészt - véletlenszerű adatokat, másrészt - tömörített korábban. Feltételezve, hogy a kompresszor által veszteségmentes fájlokat, akkor egy fájlt, és csökkenti egyszer, majd ismét áthaladt a kompresszor és csökkenti újra. Ha a művelet megismételni újra és újra, a végén, a fájl zsugorodik egy kicsit, megtartva az összes hasznos információt, hogy természetesen - ez abszurd.

Vagyok hajlandó fizetni ötezer dollárt, hogy bárki, aki a következő feltételeknek kell. Azt mondja meg, hogy milyen méretű lehet tömöríteni a fájlt, és bizonyítani a súlyosság küldjön nekem 100 $. Azt létrehoz egy fájlt, és küldök Önnek. Megtanulod, amit akar, majd tömöríteni, és küldj együtt a program egy kiadás. Kinyitom a fájlt, és ellenőrizze -, hogy az információ nem veszett el. Ha nem volt, és tömörített fájl mellett a kibontó, bár egy kicsit kisebb, mint az eredeti fájlt, fogom fizetni 5000, plusz a 100 $.

Olvastam a javaslatot. Úgy hangzik, nagyon csábító, hogy még mindig érvényben van? Ha igen, azt szeretném tudni, hogy a részleteket a kibontó - meg kell futtatni bármelyik vagy elég bármely platformon, mint például a Linux?

Igen, az ajánlat érvénytelen. Linux, de elég. Azt szeretnénk, hogy a kockázatot?

Én még mindig gondolok rá. Csak akkor kell a tömörített fájlt?

Azt mondják, hogy mekkora szükség van egy fájlt, és küldje el nekem 100 $. Azt létrehoz egy fájlt, és küldök Önnek. Akkor küldje el nekem együtt a sűrített kicsomagoló. Ha a tömörített fájlt a kibontó kisebb, mint az eredeti - küldöm, hogy 5000. Ha nem - akkor újra küldeni nekem 100 $, és próbálja újra.

Tudok küldeni tömörített adatok nem egyetlen fájlt, több részből, valamint egy dekompressziós, amely visszaállítja az eredeti?

Elfogadom a kihívást. Hogyan lehet pénzt küldeni?

Küldj egy csekken vagy banki átutalással. Ha Ön egy nagy fájl, meg kell adnia a megfelelő támogatást. Van úgy döntött, milyen méretű kell?

Én még mindig gondolok az optimális méret, de azt hiszem, ez lesz kevesebb, mint egy gigabyte. Van bárhonnan hozzáférést az ftp-szerver névtelen?

Ember, a kockázat ötezer dollárt kell vigyázni, hogy az adatok összenyomhatatlan. Teljesen összenyomhatatlan információt, mint már említettük - egy sor véletlen számok. De kiderült, garantáltan kap egy sor - nem könnyű feladat. A program mindig szigorúan követi az algoritmus és a nemzetközi munkájának eredménye lehet generálni egy ál-véletlen számokat. Ebben az esetben nem biztos, hogy ez a számsor nem lehet megismételni vagy azok által az ilyen programok. Ez a káosz csak megtalálható az események valós életben.

Mi tette őket Patrik Kreyg? Ő az események, s az interneten elhelyezett:

Itt van, amit jött Patrick. Tegyük fel, hogy egy hosszú véletlen adatfájlt. Találunk ebben a fájlban, így például az „A” betű. Most a „A” betű, vágjuk fel a fájlt két részből áll, és a nagyon levelet a kibocsátást. Kapunk két fájlt, ami együtt lesz egy bájt kisebb, mint az eredeti. Visszaállítani az eredeti, akkor csak meg kell ragasztani mindkét rész, beillesztik azokat a „A” betű.

Természetesen az eredeti fájlt nem lehet vágni két, három és több, mint az „A” választottunk ki, a levél található benne sokszor. Ha van dolgunk véletlenszerű adatokkal, akkor minden karakter találkozik körülbelül minden 255 karakter. Így vágás egy hosszú fájlt azokon a helyeken, ahol ez az „A” betű, és dobott rá, teszünk egy nagy fájlt egy láncot kis megtakarítás négy bájt kilobájtalapon. Az ember csak írni egy egyszerű program, amely lehet egymáshoz ragasztott a különböző kockára vágott egy nagy fájlt, az eredeti.

Patrick, ez a program, amit nevezhetünk a kibontó volt kisebb, mint 156 bájt. A forrás file 3 megabájt, lehet osztani mintegy 3000 darab, de Patrick úgy döntött, hogy megáll a második száz, mivel az algoritmus tiszta volt, és az eredmény nyilvánvaló.

Vágó a fájlt két részre, és öntsük egy bájt a bemetszés helyén, Patrick valóban csökkentette a fájlok tartalmát egy byte. De eltekintve a fő tartalmát, minden fájl egy másik név, dátum és koordinátái a helyét a fizikai lemez, és így tovább. Ennek eredményeként a két fájl hossza egy bájt kisebb, mint a harmadik, több helyet egy igazi lemez, bár a látszólagos mérete úgy tűnik, hogy nekünk kevesebb.

Ez Patrik Kreyg mondta:

Ha az operációs rendszer hosszú fájl kevesebb helyet igényel, mint a két rövid, ez az ő problémája, nem az enyém.

Tiszteletére Patrika Kreyga, nem ragaszkodnak a díjat, és elismerte később, hogy ez nem volt várható, hogy keresni öt ezer dollár. Ennek fő célja az volt, hogy „eszén ravasz” - azt mutatják, hogy magabiztosak Goldman lehet nyerni, annak feltételeit, ha figyelembe vesszük a problémát, mint egy puzzle, egy fuzzy megfogalmazása a probléma.