Forum » Znanost in tehnologija » Kompresija s pomočjo /dev/random
Kompresija s pomočjo /dev/random
Afo ::
Kmalu* bo cela trilogija LOTR zajeta v desetih kilobajtih...
*V nekaj stoletjih
Za to sploh ni treba nekaj stoletij:
"Spišeš kodek", ki je narejen samo za prikazovanje LOTR trilogije. Potem pa po netu pošlješ en bit podatkov: če je 1 ga prikaže, če 0 ga ne.
Slabost je samo v tem, da moraš imet cel LOTR pri sebi na računalniku, prednost pa potreben zelo nizek bandwidth :D
Bolje biti mlad in neumen, kot samo neumen!
jype ::
Riot77> "Spišeš kodek", ki je narejen samo za prikazovanje LOTR trilogije. Potem pa po netu pošlješ en bit podatkov: če je 1 ga prikaže, če 0 ga ne.
Komot napišeš tudi takega, ki deluje za poljubno vsebino: Pošlješ par dovolj kompleksnih rezultatov zgostitvenih funkcij in dolžino dekompresiranega niza, potem pa na cilju bereš /dev/random dokler se ti rezultat ne ujema (in imaš zelo verjetno točno pravo zaporedje bitov).
Komot napišeš tudi takega, ki deluje za poljubno vsebino: Pošlješ par dovolj kompleksnih rezultatov zgostitvenih funkcij in dolžino dekompresiranega niza, potem pa na cilju bereš /dev/random dokler se ti rezultat ne ujema (in imaš zelo verjetno točno pravo zaporedje bitov).
Bistri007 ::
Komot napišeš tudi takega, ki deluje za poljubno vsebino: Pošlješ par dovolj kompleksnih rezultatov zgostitvenih funkcij in dolžino dekompresiranega niza, potem pa na cilju bereš /dev/random dokler se ti rezultat ne ujema (in imaš zelo verjetno točno pravo zaporedje bitov).
Samo moraš vedeti, da se random podatkov ne da kompresirati.
Glej: The Enduring Challenge of Compressing Random Data - http://www.drdobbs.com/architecture-and...
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
jype ::
Sej jih nič ne kompresiraš. Bom poskusil prevest iz slovenščine v nekaj, kar boste razumeli:
Izračunaš npr. sha-3, whirlpool in morda še ripemd-320, pošlješ te tri vrednosti in velikost na cilj, tam pa računalnik bere svoj /dev/random toliko časa, da ven prebere vrednost, ki je enako dolga in s temi tremi hashi vrne enake tri vrednosti.
Edini praktičen problem je časovna zahtevnost dekompresiranja (zaradi očitne neuporabnosti kakršnihkoli pseudoroandom generatorjev).
Izračunaš npr. sha-3, whirlpool in morda še ripemd-320, pošlješ te tri vrednosti in velikost na cilj, tam pa računalnik bere svoj /dev/random toliko časa, da ven prebere vrednost, ki je enako dolga in s temi tremi hashi vrne enake tri vrednosti.
Edini praktičen problem je časovna zahtevnost dekompresiranja (zaradi očitne neuporabnosti kakršnihkoli pseudoroandom generatorjev).
MrStein ::
Riot77> "Spišeš kodek", ki je narejen samo za prikazovanje LOTR trilogije. Potem pa po netu pošlješ en bit podatkov: če je 1 ga prikaže, če 0 ga ne.
Komot napišeš tudi takega, ki deluje za poljubno vsebino: Pošlješ par dovolj kompleksnih rezultatov zgostitvenih funkcij in dolžino dekompresiranega niza, potem pa na cilju bereš /dev/random dokler se ti rezultat ne ujema (in imaš zelo verjetno točno pravo zaporedje bitov).
Ne deluje.
"Osnovna" matematika.
V bistvu ista logika, zakaj random podatkov ni mogoč kompresirati.
Motiti se je človeško.
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!
BaToCarx ::
HaHA koliko časa že nisem slišal tistega dev/random heca. Deluje ne skrbet, samo časovno ni, umm kako bi rekel, "uporabno"
Bistri007 ::
Izračunaš npr. sha-3, whirlpool in morda še ripemd-320, pošlješ te tri vrednosti in velikost na cilj, tam pa računalnik bere svoj /dev/random toliko časa, da ven prebere vrednost, ki je enako dolga in s temi tremi hashi vrne enake tri vrednosti.
Edini praktičen problem je časovna zahtevnost dekompresiranja (zaradi očitne neuporabnosti kakršnihkoli pseudoroandom generatorjev).
Kaj pa kolizije? ShaX praktično označuje unikatno podatke, ker je verjetnost nenamenske kolizije zelo majhna. V resnici pa ne moreš z 20 bajti enoznačno označiti 20gb...
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Bistri007 ::
Heh, če ti je lažje, si namesto shaX predstavljaj običajno 20 bajtno vsoto. Koliko 1kb datotek ima to vsoto? Koliko 20gb datotek ima tako vsoto?
Pri shaX je težje poiskati kolizijo, ker je to kombinacija seštevanja in množenja, ampak to ne pomeni, da je kolizij kaj manj kot pri preprostem CRC.
Pri shaX je težje poiskati kolizijo, ker je to kombinacija seštevanja in množenja, ampak to ne pomeni, da je kolizij kaj manj kot pri preprostem CRC.
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
BaToCarx ::
Hihi, saj je rekel da ni pseudo random "dev/random" je true random generator. Milkiwaya ni več preden boš 1 hash match dobil....
Bistri007 ::
Saj Ivy Bridge ima strojni rnd z izvorom entropije: RdRand @ Wikipedia
Samo kako to karkoli spremeni?
Samo kako to karkoli spremeni?
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
BaToCarx ::
Lej kar je jype rekel je pojeb že v bistvu... se ti ni treba matrat razumet.
Big Bang (random start) -> time + hash (atomčki pa tko) -> vse (mi)
Ti je lažje?
Big Bang (random start) -> time + hash (atomčki pa tko) -> vse (mi)
Ti je lažje?
Lonsarg ::
Jao, sem šel že računat, koliko računske moči za koliko stiskanja, pol sem pa končno porajtal, da se to NE da zaradi kolizije ja.....
Nima veze true random. Enostavno je v 21 bitih za faktor dve več dve kombinacij, kot v 20 bitih, torej se vsak hash(bilokateri) v povprečju pojavi dvakrat.
Če imaš pa recimo 30bitov dolg podatek z 20bitnim hashom(~33% stiskanje) potem imaš v povprečju 2^10krat vsak hash. Torej ne deluje zadeva. Bi delovala, če bi 2^10 ali več različnih hasov dal notri(MD5,SHA-1,...) sam potem nisi nič prostora izgubil, pač pa pridobil...
Nima veze true random. Enostavno je v 21 bitih za faktor dve več dve kombinacij, kot v 20 bitih, torej se vsak hash(bilokateri) v povprečju pojavi dvakrat.
Če imaš pa recimo 30bitov dolg podatek z 20bitnim hashom(~33% stiskanje) potem imaš v povprečju 2^10krat vsak hash. Torej ne deluje zadeva. Bi delovala, če bi 2^10 ali več različnih hasov dal notri(MD5,SHA-1,...) sam potem nisi nič prostora izgubil, pač pa pridobil...
BaToCarx ::
Pozabil si da je povedal eksaktno dolžino... nazaj računat :P
Pa še vse tri hase mora matchat. :D
offtopic: Me je nasmejal kolk se matrate z tem.
Pa še vse tri hase mora matchat. :D
offtopic: Me je nasmejal kolk se matrate z tem.
Lonsarg ::
Jah, je mal problem, če imaš v glavi celo življenje predpostavko, da HASH funkcija 100% uunikatno označi katerikoli file.:)
jype ::
Azgard> Jah, je mal problem, če imaš v glavi celo življenje predpostavko, da HASH funkcija 100% uunikatno označi katerikoli file.:)
Sej zato maš tri, pa potem še magic na začetku fajla.
Če zračunaš verjetnosti, prideš do povsem znosnih vrednosti, do določene količine napak pa prihaja v vsakem primeru.
Sej zato maš tri, pa potem še magic na začetku fajla.
Če zračunaš verjetnosti, prideš do povsem znosnih vrednosti, do določene količine napak pa prihaja v vsakem primeru.
Lonsarg ::
Številko napak bo večje od prišparanega prostora, torej boš v najbolšem primeru, če boš imel ekstremno srečo stisnil na tak način, da boš enostavno odstranil veliko zadev.
Lonsarg ::
Kompresija je pri video nadpomenka za vse metode, tako dejansko stiskanje, kot za odstranitev določenih informacij(manj pomembnih) iz filma. Ampak pri random generatorju bi odstranil random informacije in bi bil rezultat jao slab:)
jype ::
Saj se da izračunat, kolk različnih enako dolgih bitnih nizov ustreza isti vrednosti treh znatno različnih zgoščevalnih funkcij (ki se začnejo z video glavo, na primer).
BaToCarx ::
Predam se, ker si ne znaš ponovit korake v glavi in razumet za kaj se sploh gre.
Btw Player ti tudi nebi predvajal če je narobe pa kolision..
Btw Player ti tudi nebi predvajal če je narobe pa kolision..
Lonsarg ::
Saj se da izračunat, kolk različnih enako dolgih bitnih nizov ustreza isti vrednosti treh znatno različnih zgoščevalnih funkcij (ki se začnejo z video glavo, na primer).
Se da ja:
Če imaš pa recimo 30bitov dolg podatek z 20bitnim hashom(~33% stiskanje) potem imaš v povprečju 2^10krat vsak hash. Torej ne deluje zadeva. Bi delovala, če bi 2^10 ali več različnih hasov dal notri(MD5,SHA-1,...) sam potem nisi nič prostora izgubil, pač pa pridobil...
Potreboval bi 2^10 hash funkcij, ki so VEDNO različne in to pri 30 bitih dolgemu podatku, kaj šele pri 10000000 bit dolgemu podatku...
jype ::
Azgard> Potreboval bi 2^10 hash funkcij, ki so VEDNO različne in to pri 30 bitih dolgemu podatku, kaj šele pri 10000000 bit dolgemu podatku...
Nisi upošteval niti preseka, niti fiksne dolžine. Oboje znatno zmanjša prostor, ki ga imaš za napake.
Nisi upošteval niti preseka, niti fiksne dolžine. Oboje znatno zmanjša prostor, ki ga imaš za napake.
Lonsarg ::
Ja, pa naj zmanjša, to ni bil point... ne kapiraš. Za zapis n podatkov rabiš n podatkov, pa tut če magijo izvajaš. Z x bitom hashom in n bitom podatkov lahko zapišeš x+n bitov podatkov.
Voluharr ::
...dokler ne ugotoviš, da le te tudi enkrat zmanjka.
Backup, VPS, kolokacija: https://reavisys.si
Bistri007 ::
Jah, je mal problem, če imaš v glavi celo življenje predpostavko, da HASH funkcija 100% uunikatno označi katerikoli file.:)
Hja, mene so pri matematičnem krožku v šoli naučili Dirichletov princip.
Pigeonhole principle @ Wikipedia
Pač, če imaš 9 kletk in 10 ptičev, in če so vsi ptiči v kletkah --- potem sta vsaj v eni kletki dva ali več.
Če imaš 1000-mestne podatke in 20-mestno "unikatno" oznako, kaj boš? Z 20-mestno unikatno oznako lahko unikatno zapišeš samo 20 mest. Kar je več, pa prihaja do podvajanj.
Tudi če bi dali kot pogoj, da mora biti rezultat veljavna MPEG datoteka, brez napak (kockanja), bi se zagotovo zgodilo več kolizij, ki bi tudi dale kot rezultat veljavno MPEG datoteko, vendar ne to, katero ti misliš.
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
jype ::
Bistri007> Pač, če imaš 9 kletk in 10 ptičev, in če so vsi ptiči v kletkah --- potem sta vsaj v eni kletki dva ali več.
In imaš devet različnih možnosti. Če pa lahko te ptiče v kletke zložiš na samo tri različne načine, imaš pa še manj različnih možnosti. Če veš še, da ne moreta biti dva ptiča v prvih treh kletkah, je teh še manj.
Prej ali slej prideš do tega, da je možnosti dovolj malo, da so kolizije manj pogoste kot bitne napake - le da je pri bitni napaki stvar običajno obvladljiva, pri zgoraj opisani shemi pa rezultat popolnoma neuporaben.
In imaš devet različnih možnosti. Če pa lahko te ptiče v kletke zložiš na samo tri različne načine, imaš pa še manj različnih možnosti. Če veš še, da ne moreta biti dva ptiča v prvih treh kletkah, je teh še manj.
Prej ali slej prideš do tega, da je možnosti dovolj malo, da so kolizije manj pogoste kot bitne napake - le da je pri bitni napaki stvar običajno obvladljiva, pri zgoraj opisani shemi pa rezultat popolnoma neuporaben.
Lonsarg ::
Pač nisi človek za logiko, sprijazn se, saj 95%+ prebivalstva ni.
Kar se pa tiče dodajanje omejitev pa vsako dodajanje omejitev poleg manjšanja možnosti hkrati tudi poveča velikost podatkov(oziroma zmanjša količina informacij, odvisno kako se zadeve lotiš) in nisi naredil nič.
Kar se pa tiče dodajanje omejitev pa vsako dodajanje omejitev poleg manjšanja možnosti hkrati tudi poveča velikost podatkov(oziroma zmanjša količina informacij, odvisno kako se zadeve lotiš) in nisi naredil nič.
jype ::
Azgard> Kar se pa tiče dodajanje omejitev pa vsako dodajanje omejitev poleg manjšanja možnosti hkrati tudi poveča velikost podatkov(oziroma zmanjša količina informacij, odvisno kako se zadeve lotiš) in nisi naredil nič.
Ne razumeš. Imaš prostor možnih rezultatov, ki je omejen z dosegi teh zgoščevalnih funkcij. Ker so različne, moraš deliti, ne odštevati z njihovimi velikostmi, poleg tega pa moraš zadostiti še pogojem, ki so znani vnaprej (in sicer so podatki, a jih ni treba prenašati), ker gre za znano vrsto in obliko podatkov.
Ne razumeš. Imaš prostor možnih rezultatov, ki je omejen z dosegi teh zgoščevalnih funkcij. Ker so različne, moraš deliti, ne odštevati z njihovimi velikostmi, poleg tega pa moraš zadostiti še pogojem, ki so znani vnaprej (in sicer so podatki, a jih ni treba prenašati), ker gre za znano vrsto in obliko podatkov.
Lonsarg ::
Azgard>
Ne razumeš. Imaš prostor možnih rezultatov, ki je omejen z dosegi teh zgoščevalnih funkcij. Ker so različne, moraš deliti, ne odštevati z njihovimi velikostmi, poleg tega pa moraš zadostiti še pogojem, ki so znani vnaprej (in sicer so podatki, a jih ni treba prenašati), ker gre za znano vrsto in obliko podatkov.
Če se pogovarjamo o bitih potem lahko seštevaš odštevaš, ker je vsak bit neka potenca števila 2. Če pa se pogovarjamo o številkah, potem pa ja, moraš množiti in deliti, samo številke ne povejo velikosti datoteke, biti jo.
8 kletk=2^3, kar so 3 biti.
Zdaj pa če pač dodaš eno omejitev, ki preseka število možnosti za dve moraš res deliti, torej 8/2 = 4, kar sta 2 bita(2^2). Torej komot bi tudi odštel 1 bit. Smo pa mogli tut 1 bit informacije dodati, da smo povedali, za kakšno omejitev gre, torej smo še vedno ostali pri 3 bitih.
Bolš skor ne znam razložiti.
Bistri007 ::
Ne razumeš. Imaš prostor možnih rezultatov, ki je omejen z dosegi teh zgoščevalnih funkcij. Ker so različne, moraš deliti, ne odštevati z njihovimi velikostmi, poleg tega pa moraš zadostiti še pogojem, ki so znani vnaprej (in sicer so podatki, a jih ni treba prenašati), ker gre za znano vrsto in obliko podatkov.
Recimo, da tvoje 3 zgoščevalne funkcije in velikost datoteke imenuješ jype_hash (JH), katerega rezultat je 64 bajtov.
Če bi zgostil vse različne 100 bajtne datoteke, bi imel milijarde milijard kolizij.
Sam sem prej omenil, da bi bil lahko eden izmed pogojev veljavna MPEG datoteka. Ampak v teh milijardah milijard različnih možnosti se najde tudi vsaj več milijonov veljavnih MPEG datotek.
Če gremo na megabajtne velikosti ali celo gigabajtne filme, potem pa sploh. Si predstavljaš, koliko je 2^1.000.000 ali 2^1.000.000.000?
Izračun:
64 bajtov je 512 bitov
Pri 2^1.000.000 imaš s tem hashem 2^999.488 kolizij
Pri 2^1.000.000.000 imaš s tem hashem 2^999.999.488 kolizij
Teh 512 bitov je pri velikostih, običajnih za video datoteke, pljunek v morje. Lahko bi pretvoril v desetiški sistem (logaritmi), ampak rezultat je isti.
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
jype ::
Bistri007> Teh 512 bitov je pri velikostih, običajnih za video datoteke, pljunek v morje. Lahko bi pretvoril v desetiški sistem (logaritmi), ampak rezultat je isti.
Ne, ni.
Pravzaprav bi dobil le majhno naravno število kolizij, ampak da bi to razumel, moraš najprej prebrati, kaj sem zapisal zgoraj.
Ne, ni.
Pravzaprav bi dobil le majhno naravno število kolizij, ampak da bi to razumel, moraš najprej prebrati, kaj sem zapisal zgoraj.
Bistri007 ::
Ne, ni.
To ni ravno neki argument. Razen če misliš, da gre za argument avtoritete
Glej, 2^512 je gromna cifra, 1/2^512 pa zelo majhna.
Ampak 2^milijon ali 2^milijardo pa je za nekaj razredov velikost večja.
Če ti je lažje:
2^512 si predstavljaj kot dvomestno število, npr. 99
2^milijon si predstavljaj kot štirimestno število, npr. 9999
Kako misliš vsa štirimestna števila (9999) enoznačno "identificirati" zgolj z dvomestnim število (99) - oziroma dvomestnim naslovnim prostorom???
In ja, velikost datoteke je del parametra, drugače bi vzel v obzir še vsa 5-, 6-, 7- 8- itd mestna števila.
Dirichletov princip - Pigeonhole principle @ Wikipedia
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
jype ::
Bistri007> Dirichletov princip - Pigeonhole principle @ Wikipedia
Pigeonhole principle nima tako intuitivnih posledic za rigidno strukturirane podatke, kakršni so video zapisi.
Bistri007> Kako misliš vsa štirimestna števila (9999) enoznačno "identificirati" zgolj z dvomestnim število (99) - oziroma dvomestnim naslovnim prostorom???
Ne moreš, ampak veljavnih zapisov je znatno manj kot "vsa štirimestna števila" oziroma komaj kaj.
Pigeonhole principle nima tako intuitivnih posledic za rigidno strukturirane podatke, kakršni so video zapisi.
Bistri007> Kako misliš vsa štirimestna števila (9999) enoznačno "identificirati" zgolj z dvomestnim število (99) - oziroma dvomestnim naslovnim prostorom???
Ne moreš, ampak veljavnih zapisov je znatno manj kot "vsa štirimestna števila" oziroma komaj kaj.
Bistri007 ::
Ne moreš, ampak veljavnih zapisov je znatno manj kot "vsa štirimestna števila" oziroma komaj kaj.
Koliko je to po tvojem znatno manj? Torej, kolikšna je verjetnost, da ima 1GB video datoteka pokvarjen en bit, pa še vedno gre čez vsa CRC preverjanja, ki jih naredi video dekoder?
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Lonsarg ::
Tudi če narediš najbolšo možno umetno inteligenco, ki ve kak približno mora film zgledaz z kvantnim računalnikom za hardware je ŠE VEDNO preveč pravih videov. Igralec bo dal v usta bonbom, in veliko različnih odtenkov(praktično neskončno) za barvo so vsi "pravi". Že samo en sam bombon v celem videu ima več možnih kombinacij, kot jih lahko pokriješ z eno armijo hashov.
Sploh pa mi smo tole debato načeli z dilemo o računski moči in ne pametnemu softwaru, ampak kot vidiš, tudi če bi ga imeli ne gre to skozi.
Sploh pa mi smo tole debato načeli z dilemo o računski moči in ne pametnemu softwaru, ampak kot vidiš, tudi če bi ga imeli ne gre to skozi.
jype ::
Bistri007> Torej, kolikšna je verjetnost, da ima 1GB video datoteka pokvarjen en bit, pa še vedno gre čez vsa CRC preverjanja, ki jih naredi video dekoder?
Če je CRC, potem ogromno. Če je kaj zapletenejšega, potem znatno manj.
Azgard> je ŠE VEDNO preveč pravih videov.
Ni jih preveč, ker biti med seboj še zdaleč niso neodvisni.
Azgard> načeli z dilemo o računski moči
Ja, ampak moj point ni bil, da lahko karkoli zapišeš kot en hash, ampak da lahko video zapis zapišeš kot tri med seboj neodvisne hashe (in imaš možnosti, da ko imaš ustrezajočo veljavno strukturo, tudi video ustreza).
Če je CRC, potem ogromno. Če je kaj zapletenejšega, potem znatno manj.
Azgard> je ŠE VEDNO preveč pravih videov.
Ni jih preveč, ker biti med seboj še zdaleč niso neodvisni.
Azgard> načeli z dilemo o računski moči
Ja, ampak moj point ni bil, da lahko karkoli zapišeš kot en hash, ampak da lahko video zapis zapišeš kot tri med seboj neodvisne hashe (in imaš možnosti, da ko imaš ustrezajočo veljavno strukturo, tudi video ustreza).
Zgodovina sprememb…
- spremenilo: jype ()
Bistri007 ::
Sploh pa mi smo tole debato načeli z dilemo o računski moči in ne pametnemu softwaru, ampak kot vidiš, tudi če bi ga imeli ne gre to skozi.
Azgard, jypa se očitno ne da prepričati. Ampak Dirichletov princip je zakon množice.
Primer:
Imaš npr. 100MB datoteko, tj. 800 milijonov bitov.
- imaš 2^800.000.000 različnih datotek.
- 512-bitnih hashev imaš različnih "samo" 2^512.
Ne me narobe razumeti, ampak 2^512 je ogromna cifra, 1/2^512 pa zelo majhna. Ampak nesignifikantna v primerjavi z 2^800.000.000.
Vsak izmed 512-bitnih hashev ima 2^799.999.488 kolizij. Če npr. rečeš, da je veljavna video datoteka samo vsaka na milijardo milijard, tj vsaka na 2^60 (zelo konzervativno gledano).
Ampak tudi s tem imaš 2^799.999.428 veljavnih video datotek velikosti točno 100MB za vsaki tvoj jype hash.
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Bistri007 ::
EDIT:
Ajde, naj bo po tvoje. Povej točno koliko bitov potrebuješ za:
- velikost datoteke
- hash 1
- hash 2
- hash 3
Kolikšna je po tvojem verjetnost, da dobiš veljavno 100MB video datoteko s pokvarjenim enim bitom. Oceno prosim.
Ja, ampak moj point ni bil, da lahko karkoli zapišeš kot en hash, ampak da lahko video zapis zapišeš kot tri med seboj neodvisne hashe (in imaš možnosti, da ko imaš ustrezajočo veljavno strukturo, tudi video ustreza).
Ajde, naj bo po tvoje. Povej točno koliko bitov potrebuješ za:
- velikost datoteke
- hash 1
- hash 2
- hash 3
Kolikšna je po tvojem verjetnost, da dobiš veljavno 100MB video datoteko s pokvarjenim enim bitom. Oceno prosim.
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...
jype ::
Bistri007> Kolikšna je po tvojem verjetnost, da dobiš veljavno 100MB video datoteko s pokvarjenim enim bitom. Oceno prosim.
Odvisno od zapisa med približno 1/2^10 do 1/2^120 (odvisno predvsem od mehanizmov, ki jih uporablja za odpravo napak).
Odvisno od zapisa med približno 1/2^10 do 1/2^120 (odvisno predvsem od mehanizmov, ki jih uporablja za odpravo napak).
BaToCarx ::
Lahko dam jst moj primer, ka vidim da se vam da računat?
Imamo format video zapisa .bato , ima dolečeno striktno vse kar je noter, je raw format za sliko uporablja 64 bit za (RGB) 120 fps ter uporablja točno zaporedje pixslov v enem frejmu 4K, ki se matematično premikajo na "nerandom" način ( pixel 0,0 v frame 1 je v fajlu na pozicij 0,0 , pixel 0,0 v frame 2 je pa na poziciji 231,666, itd..) za vsakim frame je reedsolomon za prejšnih 10 in naslednjih deset frameov, Vsakih 120 frame je redsolomon za prejšnih 120 ter naseldnjih 120 redsolomonov. Dekoder v primeru nepoprvaljive napake izračuna vmesne slike. Torej pravila so "jasna".
random je kot pipca 0 in 1, to se strinjamo? Torej ko dobimo prvi naliv ki je pravilne velikosti uporabimo CRC32, če je match še SHA-512, če je match še Whirpool, če je match predvajamo. Gut? Če ga ni se prvi 0 ali 1 odstrani in doda naslednji 0 ali 1. Ad infinitum...
Z vsemi kolizijami in pojebi, še vedno dobimo več dobrih pixlov kot z kakršnokoli lossy kompresijo. Ker nas čas ne briga, nas ne briga tudi velikost zato poknemo en par petabajtov (ali kot se nam zdi potrebno, za prihodnje "rodove" XD) z vso zgodbo sveta v moving pix je to zmaga, je pa dumb 100%.
*nerandom = beri wiki ali random.org kako določajo kaj je random kaj pa ne.
Se motim in kje?
Imamo format video zapisa .bato , ima dolečeno striktno vse kar je noter, je raw format za sliko uporablja 64 bit za (RGB) 120 fps ter uporablja točno zaporedje pixslov v enem frejmu 4K, ki se matematično premikajo na "nerandom" način ( pixel 0,0 v frame 1 je v fajlu na pozicij 0,0 , pixel 0,0 v frame 2 je pa na poziciji 231,666, itd..) za vsakim frame je reedsolomon za prejšnih 10 in naslednjih deset frameov, Vsakih 120 frame je redsolomon za prejšnih 120 ter naseldnjih 120 redsolomonov. Dekoder v primeru nepoprvaljive napake izračuna vmesne slike. Torej pravila so "jasna".
random je kot pipca 0 in 1, to se strinjamo? Torej ko dobimo prvi naliv ki je pravilne velikosti uporabimo CRC32, če je match še SHA-512, če je match še Whirpool, če je match predvajamo. Gut? Če ga ni se prvi 0 ali 1 odstrani in doda naslednji 0 ali 1. Ad infinitum...
Z vsemi kolizijami in pojebi, še vedno dobimo več dobrih pixlov kot z kakršnokoli lossy kompresijo. Ker nas čas ne briga, nas ne briga tudi velikost zato poknemo en par petabajtov (ali kot se nam zdi potrebno, za prihodnje "rodove" XD) z vso zgodbo sveta v moving pix je to zmaga, je pa dumb 100%.
*nerandom = beri wiki ali random.org kako določajo kaj je random kaj pa ne.
Se motim in kje?
Jst ::
"Deja-vu." Točno takšno debato smo imeli na IRCu okoli 2000, potem je pa nastal tisti challange če komu uspe stisniti random fajl datoteko.
Ampak to ni random. Imamo točno določeno strukturo in če bi spisali posebno hash funkcijo, ki bi upoštevala točno te karakteristike, je možno, da bi iz hasha lahko ugotovil pravo datoteko - sploh če imaš še pseudo-pseudo-random, ki tudi upošteva karakteristike originalne datoteke. Vendar bi najbrž porabili kakšno galaksijo materiala za dokaz/ovržitev, če bi to reševali z raw computingom.
Če komu uspe, je naredil velik korak k miljonu dolarjev - P=NP millennium prize.
Ampak to ni random. Imamo točno določeno strukturo in če bi spisali posebno hash funkcijo, ki bi upoštevala točno te karakteristike, je možno, da bi iz hasha lahko ugotovil pravo datoteko - sploh če imaš še pseudo-pseudo-random, ki tudi upošteva karakteristike originalne datoteke. Vendar bi najbrž porabili kakšno galaksijo materiala za dokaz/ovržitev, če bi to reševali z raw computingom.
Če komu uspe, je naredil velik korak k miljonu dolarjev - P=NP millennium prize.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|
Gemm ::
Upam da to ni preveč offtopic,..
Če koga zanima kako te stvari dejansko delujejo in so uporabne za kompresijo podatkov, priporočam da naj si prebere kaj o "Compressive sensing". Vsa filozofija temelji na tem, da če je signal kompresibilen (se ga v teoriji da opisati z relativno malo koeficienti v transformiranem prostoru), potem obstaja nek postopek rekonstrukcije.
Hash funkcije ki jih tu uporabljate tu niso pretirano praktične, ker nimajo lepega inverznega transforma.
(Zakaj ima to vezo z /dev/random: tu se precej uporabljajo naključne matrice, ki so precej uporabna ortogonalna baza za opis podatkov z manj-dimenzionalnim zapisom)
Compressed sensing @ Wikipedia
http://dsp.rice.edu/files/cs/baraniukCS...
http://dsp.rice.edu/research/compressiv...
To precej s pridom uporabljam za razne data mining zadeve, ker se z njimi da dobiti zelo dobre aproksimacije podatkov, ki malo zasedejo, ampak so kvantitativno dovolj dobre. To je tudi en tak 'big data' mehanizem, da si lahko zmanjšaš problem - vsaka dobra implementacija compressed sensinga pomeni da se je nekdo uspešno izognil nakupa hadoop clusterja :)
Če koga zanima kako te stvari dejansko delujejo in so uporabne za kompresijo podatkov, priporočam da naj si prebere kaj o "Compressive sensing". Vsa filozofija temelji na tem, da če je signal kompresibilen (se ga v teoriji da opisati z relativno malo koeficienti v transformiranem prostoru), potem obstaja nek postopek rekonstrukcije.
Hash funkcije ki jih tu uporabljate tu niso pretirano praktične, ker nimajo lepega inverznega transforma.
(Zakaj ima to vezo z /dev/random: tu se precej uporabljajo naključne matrice, ki so precej uporabna ortogonalna baza za opis podatkov z manj-dimenzionalnim zapisom)
Compressed sensing @ Wikipedia
http://dsp.rice.edu/files/cs/baraniukCS...
http://dsp.rice.edu/research/compressiv...
To precej s pridom uporabljam za razne data mining zadeve, ker se z njimi da dobiti zelo dobre aproksimacije podatkov, ki malo zasedejo, ampak so kvantitativno dovolj dobre. To je tudi en tak 'big data' mehanizem, da si lahko zmanjšaš problem - vsaka dobra implementacija compressed sensinga pomeni da se je nekdo uspešno izognil nakupa hadoop clusterja :)
jype ::
Jst> če bi spisali posebno hash funkcijo, ki bi upoštevala točno te karakteristike, je možno, da bi iz hasha lahko ugotovil pravo datoteko
Ja, to je ekstremen primer tega. Hash funkcija, ki iz vsakega filma pridela enoznačen niz.
Potem bi z dovolj računske moči končno lahko gledali filme, še preden jih posnamejo, like they did in Spaceballs!
Gemm> Upam da to ni preveč offtopic,..
Niti ne, ampak saj teorija je jasna, prepir je samo o tem, skozi kako kompleksen okvir še lahko stlačiš kose naključno zgrajenega modela. Če je okvir dovolj zapleten (recimo toliko, kot sta h264 in DTS uokvirjena v matroško), zelo malo (v primerjavi z vsemi možnimi - če dovolj malo, da postane uporabno, pa se verjetno nikomur ni ljubilo izračunati).
Ja, to je ekstremen primer tega. Hash funkcija, ki iz vsakega filma pridela enoznačen niz.
Potem bi z dovolj računske moči končno lahko gledali filme, še preden jih posnamejo, like they did in Spaceballs!
Gemm> Upam da to ni preveč offtopic,..
Niti ne, ampak saj teorija je jasna, prepir je samo o tem, skozi kako kompleksen okvir še lahko stlačiš kose naključno zgrajenega modela. Če je okvir dovolj zapleten (recimo toliko, kot sta h264 in DTS uokvirjena v matroško), zelo malo (v primerjavi z vsemi možnimi - če dovolj malo, da postane uporabno, pa se verjetno nikomur ni ljubilo izračunati).
driver_x ::
Riot77> "Spišeš kodek", ki je narejen samo za prikazovanje LOTR trilogije. Potem pa po netu pošlješ en bit podatkov: če je 1 ga prikaže, če 0 ga ne.
Komot napišeš tudi takega, ki deluje za poljubno vsebino: Pošlješ par dovolj kompleksnih rezultatov zgostitvenih funkcij in dolžino dekompresiranega niza, potem pa na cilju bereš /dev/random dokler se ti rezultat ne ujema (in imaš zelo verjetno točno pravo zaporedje bitov).
Sem probal, pa mi Cray Titan v kleti še sedaj nekaj melje.
jype ::
sammy73> Sem probal, pa mi Cray Titan v kleti še sedaj nekaj melje.
A si ponesreč turbo izklopu?
A si ponesreč turbo izklopu?
Jst ::
sammy: če se mi poleti pokvari klima, se lahko pridem hladiti v tvojo klet?
--
>Potem bi z dovolj računske moči končno lahko gledali filme, še preden jih posnamejo,
Če bi pseudo-pseudorandom generator generiral frejme, ne rabiš veliko računske moči. Kaj bi pa gledal, je pa drugo vprašanje.
--
>Potem bi z dovolj računske moči končno lahko gledali filme, še preden jih posnamejo,
Če bi pseudo-pseudorandom generator generiral frejme, ne rabiš veliko računske moči. Kaj bi pa gledal, je pa drugo vprašanje.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Izračunana uspešna kolizija nad SHA-1Oddelek: Novice / Varnost | 8818 (6521) | matijadmin |
| » | [Java] Kako izračunati hash diska.Oddelek: Programiranje | 4711 (3541) | kunigunda |
| » | online davčne blagajne - plagiat hrvaških?Oddelek: Loža | 9847 (8397) | Matako |
| » | SHA1 hash - prevodOddelek: Programiranje | 3901 (3558) | darkolord |
| » | Zgostitveni algoritem SHA-0 razbitOddelek: Novice / Varnost | 4130 (4130) | darkolord |