Legjobb tömörítési módszer

Inkább nagy részhalmazát nem? Szinte az összes "tömöritetlen" fájlt lehet tömöriteni (kissebbre),...

Nem. Az összes fájl az tényleg az összes, {0,...,255} számhalmazon értelmezett véges hosszú sorozatoknak megfelelő fájlokból áll. Az összes ilyen sorozatokból álló halmaznak _nagyon_kis_ részhalmaza az, amit használunk, és pont erre optimizálják a tömörítőket.

Ha nem hiszed tégy próbát: generálj 100 darab véletlen hosszúságú fájlt, ami csupa véletlenszámokból áll, és próbáld meg ugyanazzal a tömörítővel betömöríteni őket! (Erre könnyen írhatsz programot is.) Mi lesz az eredmény? (Először próbáld meg megsaccolni! )

Inkább nagy részhalmazát nem? Szinte az összes "tömöritetlen" fájlt lehet tömöriteni (kissebbre), de sok tömöritett fájl mérete is csökkenthető még tovább tömöritéssel (nem a végtelenségig, de egy második tömörités még biztosan csökkenthet.) Ha meg a második-harmadik (sokadik) tömörités már nem csökkent a fájl méretén az inkább azt bizonyitja, hogy jó a tömöritő eljárás, és nem azt hogy rossz. Az meg kevésbé életszerű, hogy valaki minden fájlt tömöritve (esetleg többszörösen tömöritve) tárol. -ha van is ilyen felhasználó, ő a lehetséges felhasználóknak csak "kis részhalmaza".

Én olyasmin gondolkodtam tegnap (de minek?), hogy ha valaki készitene egy képletet, amibe behelyez mondjuk 10 byte-ot és a végeredmény egy olyan mondjuk 5 byte-os érték ami csak erre a 10 byte-ra jön ki, akkor elég tárolni a 5 byte-os eredményt, és kitömöritésnél addig helyettesiteni a byte-okat a képletbe, mig meg nem kapjuk a tárolt eredményt, ha ez megvan akkor megvan a 10 byte amit tömöritettünk.
Először jó ötletnek tünt, aztán arra gondoltam, hogy matematikailag lehetetlen megvalósitani. Valószinűleg lehetetlen, mert akkor ha újra és újra tömöritenénk egy fájlt, akkor a végén egy egész DVD-nyi adat csak 5 byte-ot foglalna. (és onnan már nincs messze a 2 byte-os tömörités.)

Csak azt a programot kellene megtalálni köztük, ami ezt kideríti a többiről, és leírásokat készít hozzájuk.

Najó , csak vicc volt , nehogy komolyan vegyétek

Nemjó , sok ideig tartana kideríteni hogy melyik mit csinál ...

generálni kell egy hatalmas adatbázist , amiben megtalálható az összes működő exe mondjuk 20 megáig . utána ha kell a : windows to linux converter , akkor kiválasztjuk a 3524. fájlt . Ennyi

Igazad van, tomoritett fajl tomoritesere nem gondoltam...

Legyen mondjuk A egy ilyen algoritmus, vagyis A bármely fájlt tömörít, annak tartalmától függetlenül, mágpedig úgy, hogy az kisebb lesz, akár egyetlen egy bájttal is, de kisebb. (Pont, ahogy írtam.)

Ekkor egy tetszőleges F fájlból kindulva A(F) mérete kisebb mint F-é, A(A(F)) mérete kisebb, mint A(F)-é, ami viszint kisebb mint az eredeti F-é volt.

Így egy monoton csökkenő sorozatot kapunk, ami egészen elvisz az 1 bájtos méretig. (Itt látjuk, hogy az eredeti megkötés túl szigorú volt, az 1 bájtos fájlt semmi nem fogja tömöríteni, de ha az egy bájtra elengedjük a feltételt, akkor is igaz a gondolatmenet.)

Vagyis A bármely fájlt betömörít 1 bájtra, ha elég sokszor lefuttatjuk az előző futtatás eredményére.

Ez nyilván ellentmondás, tehát ilyen algoritmus nem létezik.

Az előbbiekből következik, hogy bármilyen nem veszteséges "tömörítő" algoritmus (az előbbiek csak ilyenekre vonatkoznak!) esetán mindig lesznek olyan fájlok, amik nem tömöríthetőek, ezekre lefuttatva az algoritmust nagyobb méretet kapunk, mint az eredeti méret. Sőt, a nem tömöríthető fájlok bizonyos értelemben elsöprő többségben vannak.

Hogy mégis vannak működő, hatékony tömörítések, az annak köszönhető, hogy nem tetszőleges fájlokat használunk, hanem a gyakorlatilag lehetséges fájloknak csak kis részhalmazát, ezekre "szabják testre" ezeket a tömörítőket. (Pl. ismétlődések, gyakori minták, stb.)

Szerintem nem, kifejtened..?

Sőt, azokat is kizárhatjuk ugyanezen elv alapján, amik bármely fájlt, tartalomtól függetlenül (kisebbre) tudnak tömöríteni.

De ugye ezt tudtuk...
Eleve (jozan paraszti esz alapjan) kizarhatunk minden olyan tomoritasi modot ami adott hosszusagu fajlokat tartalomtol fuggetlenul mindig fix meretre tomorit.

Bakker! Nem figyeltem :)

Elnéztem. Az elmélet szerint csak az utolsó karakter változik, így csak annyivak csökken az esély az egyediségre. Ezek szerint nemhogy 26, de 26 millió szint is kevés hozzá...

Köszönöm a válaszodat .

Szerintem téma zárható .

Nézzük az elméletet levezetve:

1. Mi a hash (md5, crc, stb.) lényege?
- Olyan azonosítókód létrehozása, mely másolás vagy letöltés során létrehozott adathalmazok eredetiségét ellenőrzi, úgy, hogy a forrás és a céladat azonosítóját összehasonlítva kiadja a teljes forrás illetve céladat azonosságát is.
2. Mi a valószínűsége, hogy több, hash hosszúságnál nagyobb adatnak azonos lehet a hash értéke?
- n hosszúságú adat (ami x féle értéket vehet fel karakterenként) és m hosszúságú hash (ami y értéket vehet fel karakterenként) esetén x^n/y^m az egyhez az esélye, hogy azonos hash érték jön ki. És akkor még nem is beszéltünk a különböző hosszúságú adatokról, de itt most az elmélet szerint lényegtelen is.

Ezek tudatában már számolhatunk.

Vegyük az első szintet, és vegyünk konkrét példákat.
1024 hosszú adat, 256 felvehető értékkel.
64 hosszú hash, 32 felvehető értékkel. (a könnyebb számolhatóság kedvéért)
Esély az egyezőségre: 256^1024/32^64=5,106*10^2369 Szóval nem kicsi.

Második szint.
Azzal, hogy az utolsó karaktert megváltoztatjuk, ugyanennyi azonosság lép fel. Mekkora az esély, hogy a változtatás után ugyanúgy azonos hash értékek jöjjenek létre, mint ahogy változtatás előtt voltak?
36^40*36^40 (az összes lehetséges kombináció), amiből azonos 32^64 lehet (2,135*10^96). Vagyis ennyiszer lesz kisebb második szinten az egyezés. 256^1024/32^64/32^64=256^1024/(32^64)^2=2,390*10^2273

Észrevehető, hogy minden szinten az osztó hatványosan növekszik. A harmadik szintem már 256^1024/(32^64)^3, és így tovább.

Vagyis, ha teljes biztonsággal akarjuk ezt a fajta eljárást végrehajtani, akkor szint=26 esetén a következő számítások jönnek ki:


Vagyis a 26. szinten érjük el azt a biztos szintet, amivel az elmélet szerint visszafejthető kódokat generálnánk. Nézzük, megéri-e.

A 32 lehetöség 5 bitet jelent hash kódonként, vagyis 1 hash kód 64*5=350 bit.
A 256 lehetőség 8 bitet jelent adatonként, vagyis 1024 adat 1024*8=8192 bit.
Mivel nekünk a teljes bizonyossághoz 26 hash kódra volt szükségünk, ezért 350*26=9100 bit kell hozzá. Ez 908 bittel több, mint amennyi adatot tömöríteni akartunk volna, így az elmélet nem állja meg a helyét.

Már látom magam előtt a Furkó Antivírus méltó utódját!

Mi ez a 100 milliárdos ötlet itten?

nem kell ahhoz unatkozni.. ff pluginnal a böngésző kirakja a valid/invalid ikont az alsó sarokba.

Nem is én csináltam

Haha , nagyon unatkozhatsz , ha nincs job dolgod ennél

nem valid az oldal!

Nem ezért irtam , a sértődős korszakomon már túl vagyok egy ide*e

*j vagy ly

Ne sértődj meg.

Ez most fontos volt.

Muszáj.

Csinal o ilyent...

Egyik topikomat teleflamelted ok nélkül , még régebben .
De lehet hogy csak épp rossz kedved volt akkor , nem tudom

Sajnos ezt nem tudom kiszámolni , az alap xp-s számológép még az 1Mb-os fájl számolásánál is kiakad .

Mi is volt az?
/és ki gyözött?

Ott meg már minek tömöriteni?

Ha rosszul irtam le először , akkor itt egy példa a működés lényegére :

veszünk egy stringet ( példa kedvéért rövidet ) :

abcdefgh md5=e8dc4081b13434b45189a720b77b6818
utána: md5(ord(utolsó karakter)+1)=második md5 kód :
abcdefgi md5=bac5271550431024d9dcda7724f78674
abcdefgj md5=fea42466698b2f0eee6b69f5f57e8ac3
string hossza:8 karakter

"tömörítés" kimenete:

e8dc4081b13434b45189a720b77b6818,bac5271550431024d9dcda7724f78674,fea42466698b2f0eee6b69f5f57e8ac3,8

"kitömörítés" :

legeneráljuk sorban az összes stringet , ami 8 karakter hosszú , és összehasonlítjuk az első md5 kóddal:

aaasfgjui md5<>eredeti md5 , ezért eldobjuk és generáljuk a következőt ... így tovább , és a memóriában eltároljuk az összeset , aminek az md5-je egyezik az első eltárolt md5-tel .

példa kedvéért most a aaaaaaaa md5-je megegyezik az első eltárold md5-tel.

szóval a memóriában lévő stringek : aaaaaaaa , abcdefgh

utolsó karaktert megváltoztatjuk , és összehasonlítjuk a stringeket a következő md5-tel : aaaaaaab<>2. md5 , ezért őt eldobjuk , és maradt egy string , ami megfelelt a feltételeknek , kiirjuk egy fájlba és kész .

Persze ennek így nincs értelme , csak akkor lenne ha mega/gigabájtokról lenne itt szó .

De maga az elmélet helyes , szerintem .

Természetesen nem muszály md5 , akármilyen más ilyen típusu eljárással működhetne .