Forum Mjukvara Programmering och digitalt skapande Tråd

halvseriöst försök till komprimering

1 2
Skriv svar
Permalänk
Medlem
●
Citat:

Tvivlar på att det funkar. Det vore bättre att läsa in nåra 100 byte och sen dela upp dom i en träd struktur. Typ som huffman blablabla.

jo, men det är redan gjort. vad är det roliga då?

mala och dool:
denna algoritmen ska kunna packa vilka data som helst, och kunna förminska det. eftersom den datan komprimerade datan inte kan framställas enkelt som i tex Zip utan måste bruteforcas fram varje gång, kanske den inte klassas som en regelrätt kompressionsalgoritm. i zip så finns ju all information i filen som behövs vid uppackandet. så är inte fallet i min algoritm. däremot finns all data som behövs för att arbeta sig fram till startdatan.

säg att jag tar 256bytes, och beräknar en md5-summa på det. den tar 16 bytes att lagra. sedan tar jag roten ur 256bytesen, och sparar heltalsdelen av det tillsammans med md5-summan. då har jag vips gjort 256 byte till 128+16 = 144 byte. ratio 0.5625. det lagrade talet är omkring 1e38. felmarginalen, dvs antal test vi måste göra innan vi hittar rätt, är så hiskeligt stor att det kommer ta mycket lång tid att packa upp. duger inte md5 kan vi ta en ännu kraftigare checksumma som tar ännu mer plats, men vi kommer ändå att hamna under 1 i ratio. saken är bara den att det tar alldeles för lång tid att packa upp. men, om någon gjorde ett seriöst försök tror jag det skulle lyckas.

Senast redigerat
Visa signatur

4 datorer: 9 cpuer (plats för 4 till), 10scsi+1satadisk, 7.75gb ram, bara Linux
http://isitfika.net http://code.kryo.se

Redigera
Citera flera Citera
Permalänk
Medlem
●

Läs detta innan du lägger för mycket job på den

http://www.sweclockers.com/kommentarer/1010590463,83368,.php

kolla också här, varför man inte kan komprimera ALLA strängar, utan bara vissa, med resultat att de andra blir större när man kör sin algoritm på dem.

http://www.faqs.org/faqs/compression-faq/part1/section-8.html

PS: edit:
MD5 betyder "Message Digest" det betyder att från en lååång fil så knaprar den ihop en checksumma, detta betyder att det finns flera filer med samma checksumma, om checksumman är 1 bit kortare än filen och den går att göra på alla filer så kommer det att finnas 2 filer med den checksumman, så med andra ord så är inte CRC komprimering utan bara nerknapring, om du råker hitta fel tal som får samma checksumma så får du fel resultat
DS

Visa signatur

PIX, plx.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Nyckelordet var oberoende av algoritm, men vi kan ta det specifika fallet igen:

Du tar roten ur ett 256byte stort tal.
Roten sqrt(x) blir ett tal på 128bytes. Om jag inte minns fel så har du själv använt första kvadreringsregeln i din beskrivning så du inser att antalet 256-bytes tal som har samma heltalsrot är 2^1024 st eftersom (2^128*8 + 1)^2 - (2^128*8)^2 =~ 2^128*8.

Så varje rot har 2^1024 olika filer som kan ha genererat den. För att algoritmen ska fungera måste vi ha en metod för att kunna packa upp alla dessa 2^1024 filerna utifrån datan i den komprimerade filen.

Med en 16 bytes MDM-summa kan du högst skilja på 2^16*8 = 2^128 olika filer. Det spelar ingen roll hur fiffig funktion denna kontrollsumma är. Varje värde på detta 128bitarstal motsvarar högst en av de 2^1024 filerna, och duvhålsprincipen (eller sunt förnuft) ger att det är omöjligt att kunna mappa alla 2^1024.

Lösningen är, som du själv säger, att göra en kraftigare checksumma. Minimilängden är ganska lätt att räkna ut. Den är helt enkelt 128 bytes i det här fallet.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av alvar
Läs detta innan du lägger för mycket job på den
http://www.sweclockers.com/kommentarer/1010590463,83368,.php

ren BS.. skulle betyda att du kan packa ner 10000 bytes slumpad data till 100 byte men en generell metod.. och därefter köra en vända till ner till 1 byte... knappast troligt..

Ett företag(kommer icke ihåg vilket) utlyste en tävling där du kunde vinna en större summa pengar (eller om det var en bil) om du lyckades komprimera deras data så att den blev mindre än orginalet. Den datan dom gav ut var perfekt slumpad data och ingen lyckades utan att ta till fusk metoder så som att spara delar av filen i filnamnet osv.

EDIT: för mer avancerad BS så hänvisar jag till http://www.dachshundsoftware.com/index.html

Visa signatur

Teeworlds - För dig som gillar gulliga saker med stora vapen.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Ett sätt att minimera CRC-summan skulle vara att först ta kvadratroten och sen söka efter kortast möjliga crc som endast ger det rätta resultatet.

Typ ta kvadratroten på 123456789, vilket är 11111, möjliga rasultat av att kvadrera det är 123454321 - 123476544 vilket är 22223 olika resultat. Nu skulle man kunna börja med en kort crc och gå igenom alla 22223 resultat och se om crc på det resultatet har nån dublett, har den det så ökan man crc:n med en bit och börjar söka igen. Här skulle man kunna hitta korta crc ibland men vissa skulle även bli en bit längre, och instinktivt, utan att veta exakt, så känns det som väldigt få crc:er skulle kunna hittas om är mer än en bit kortare så jag tror hur du än gör så skulle du förlora på den här metoden. Givetvis skulle det finnas nägra sifferkombinationen där du verkligen skulle vinna en del men i det stora hela tror jag det är dödfött.

Visa signatur

-dool

Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av mala
Nyckelordet var oberoende av algoritm, men vi kan ta det specifika fallet igen:

Du tar roten ur ett 256byte stort tal.
Roten sqrt(x) blir ett tal på 128bytes. Om jag inte minns fel så har du själv använt första kvadreringsregeln i din beskrivning så du inser att antalet 256-bytes tal som har samma heltalsrot är 2^1024 st eftersom (2^128*8 + 1)^2 - (2^128*8)^2 =~ 2^128*8.

Så varje rot har 2^1024 olika filer som kan ha genererat den. För att algoritmen ska fungera måste vi ha en metod för att kunna packa upp alla dessa 2^1024 filerna utifrån datan i den komprimerade filen.

Med en 16 bytes MDM-summa kan du högst skilja på 2^16*8 = 2^128 olika filer. Det spelar ingen roll hur fiffig funktion denna kontrollsumma är. Varje värde på detta 128bitarstal motsvarar högst en av de 2^1024 filerna, och duvhålsprincipen (eller sunt förnuft) ger att det är omöjligt att kunna mappa alla 2^1024.

Lösningen är, som du själv säger, att göra en kraftigare checksumma. Minimilängden är ganska lätt att räkna ut. Den är helt enkelt 128 bytes i det här fallet.

jag är medveten om att alla olika framräknade checksummor loopar då och då. poängen med att göra binärsökningen sedan är inte att bara minska antalet tester, utan att begränsa området till ett mycket mindre, ner till ett område så litet att checksumman aldrig loopar där.

okej då, jag kan minska checksumman med en byte när jag lägger på en bytes binärsökning.. hmmm

Visa signatur

4 datorer: 9 cpuer (plats för 4 till), 10scsi+1satadisk, 7.75gb ram, bara Linux
http://isitfika.net http://code.kryo.se

Redigera
Citera flera Citera
Permalänk
Medlem
●

men, om man aldrig kommer under ratio 1 då, kan man inte pröva den på zipfiler, och sedan se om de går att zippa lite till? man kastar ju om alla bytes, så det kanske dyker upp något nytt mönster

Visa signatur

4 datorer: 9 cpuer (plats för 4 till), 10scsi+1satadisk, 7.75gb ram, bara Linux
http://isitfika.net http://code.kryo.se

Redigera
Citera flera Citera
Permalänk
Medlem
●

Du kommer under 1:1 om datan inte är helt slumpartad... Logiskt sett. Ju mindre slumpartad datan är.. Nej, vänta... Det kanske inte stämmer för denna algoritm.
För algoritmer såsom dynamic Huffman, så komprimeras slumpartad data bra mycket sämre än mindre slumpartad data.

Visa signatur

[size="1"]Coder, Absynth Interactive
~ En köpt mod är knappt en mod alls ~ One software - one function(undvik bloat) ~[/size]

Redigera
Citera flera Citera
1 2
Skriv svar