halvseriöst försök till komprimering

http://erik.laeskback.com/~yarrick/proj/sqrt/list.php?file=/e...

Du borde nog se över dina script lite..

http://erik.laeskback.com/~yarrick/proj/sqrt/list.php?file=.....

Jasså?

Man ska aldrig få specificera fil så direkt, skapar alltid säkerhetshål.

Nu funkar det inte

Ooo, pimpigt

frånsett att den "komprimerar" till samma storlek och inte klarar alla indata så verkar det lovande....

Bytes to read: 16, CRC bytes to use: 3, Binary searches: 40 (5 bytes)
Read 16 bytes: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
Negative: false, number: 1
CRC32 checksum: 2612820931
Error!
Message: BigInteger divide by zero
Exiting

Hmm. Jag är kanske trött eller nåt, men jag förstår inte. Vi tar ett exempel.

Vi läser ut talet 140 från strömmen. Roten ur 140 är 11,832.. vilket i så fall skulle avrundas till 11. 11^2 är 121. Hur får du reda på att talet egentligen ska vara 140? Jag fattar inte hur en crc kan hjälpa dig i det här fallet. Checksumman har du ju ändå beräknat på "hela strömmen" och inte bara på denna lilla del.

Förutom att jag inte förstår hur det är tänkt att fungera, så tycker jag det är ballt. Det är skönt att se lite riktig programmering här i forumet då och då

Det är väl det att programmet går igenom alla möjliga kombinationer för alla de olika talen... t.ex:

37
int(kvadratroten) = 6
6² = 36
7² = 49

36 <= 37 < 49

49 - 36 = 13 tal att kolla mot CRC:n

Kalla 37 för D, och 6 för C:
C² <= D < (C + 1)²
Antal tal mellan C² o (C + 1)² är
(C + 1)² - C² = 2C + 1

Ta talen: 175, 67
Kvadratrötter: 13, 8
Sökomfång: 27, 17
27 * 17 = 459st olika kombinationer som skulle kunna stämma för den komprimerade datan (13, 8). Därför prövar man varje kombination mot CRC:n. Om en viss kombination stämmer, så är det den rätta(detta förutsätter att CRC:n är tillräckligt lång...)

Som jag förstår det, så tar det där programmet HELA filen, räknar ut CRC, multiplicerar ihop alla bytes, drar kvadratroten ur det talet, samt sparar resultatet + CRC i en fil..

edit:
Varför inte köra unsigned o slippa tänka på om talen blir negativa?

edit2:
Fan, nu blev jag sugen på komprimering... Synd att mitt adaptive-huffman-program gjorde ooptimerade träd och att jag är för lat för att optimera :/
*kastar sig på Lempel-Ziv

Tjoppen: Jo, men skulle det inte innebära att det skulle bli sinnessjukt många kombinationer att kontrollera om den data man ska komprimera är lite längre? På bara ett par bytes är man uppe i miljoner kombinationer.

Jo, men det är där den beryktade binärsökningen kommer in, tror jag bestämt...

edit:
Talet som ska dras kvadratroten ur är oxå ganska sinnessjukt stort..

Jag måste vara i min slow setting idag. Jag fattar inte var en binärsökning kommer in i bilden? Du måste väl ändå jämföra alla kombinationer mot crc:n? Det är ju inte möjligt att veta om en viss kombination är "närmre sanningen" än en annan genom att titta på crc för denna kombination.

Har du gjort en egen implementation för det? Vi hade nån uppgift på högskolan förra året där vi gjorde en implementation av stora heltal i en Java-klass. Jag tror nog iofs bara att den hanterade de fyra räknesätten.

Om jag förstod dig rätt vill du göra om talet X (som är heltalsrepresentationen av hela filen) så till Y så att.

Y = (floor sqrt(X), X - (floor sqrt(x))^2)
d.v.s du sparar heltalsroter ur talet först och sedan "resten".

Varför det inte fungerar:

Säg att du vill komprimera ett tal på 200 bitar.
roten ur detta tal kommer att vara ett tal på hundra bitar.

Resten kommer tyvärr också att vara ett tal på över hundra bitar i genomsnitt.
säg att heltalsroten är 1000....0, en etta följt av 100 nollor. Det sökta talet ligger då mellan (2^100)^2 och(2^100+1)^2. Första konjungatregeln ger att (2^100+1)^2 = 2^200 + 2*2^100 + 1. Skillnaden ("feltermen") kan då bli allt mellan 0 och differensen
mellan dessa två uttryck = 2*2^100 = 2^101.

Redan här har du alltså ökat storleken på filen med en bit. Dessutom tillkommer "headerbitar". T.ex behövs ett tal som anger hur många av bitarna i den komprimerade filen som anger floor sqrt(X).

Man sparar inte resten, man sparar CRC:n. Förutsatt att den är tillräckligt lång, så finns endast en lösning till "ekvationen"

http://erik.laeskback.com/~yarrick/proj/sqrt/list.php?file=51...

Ta en titt på
To go: 10080519
Vilket jag förstår som hur många tal som ska sökas igenom..

Jämför det mot formeln 2C + 1, för:
C ~= 1,92414590 * 10^1285

Man kan lätt se att sökområdet minskar kraftigt..

Om det blir roten ur 2 då, då blir heltals delen 1. Problemet är att decimal utvecklingen är oändlig.

Btw, så läste inte jag så noga.

väntar fortfarande på att den ska klara alla indata samt verkligen komprimera

Fan, detta tål att prvas i C++...

Men du.. Du säger att BigInteger bara klara upp till ~2^3000... Om alla bytes är 255, så kan progget endast packa 375B.
Tror jag ska skriva en egen class för stora heltal.. Om jag tänkt rätt, så ska den kunna palla upp till 256^4Gi, mao 4GiB(eller mer)
Problemet är att skriva den... Kommer att bli drygt.

edit:
Istf att binärsöka, kan man inte bara ha ett tal som specificerar ungefär vart mellan C² o (C + 1)² ligger?
Kalla det talet O, och det är procent..
O = (D - C²)/(2C + 1)

Vill man ha O att vara ett DWORD t.ex.:
O = ((D - C²) << 32)/(2C + 1)

Då kan man krympa felmarginalen från
C² <= D <= (C + 1)²
till
C² + (O(2C + 1) >> 32) <= D < C² + ((O + 1)(2C + 1) >> 32)

Ju fler bitar O är, desto mindre marginal, desto snabbare sökning..

edit2:
Felmarginalen minskar omvänt proportionellt mot 2^(antal bitar i O)
Lägg till en bit, halvera söktiden.

Inte behöver du skriva en själv. Kolla in NTL: http://www.shoup.net/ntl/

En kul grej bara:
Nåra av världens mest framgångsrika matematiker samarbetade för att utveckla en ny komprimerings algo.
Då klarade den att komprimera 100MB till 1MB

Det läste jag i en dator tidning för ett år sen kanske. Sen vet jag inget mer om det, men det är ganska fett ändå.

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.

Tog hem en klass som hette HINT(Huge Int), och lekte lite. Här är utmatningen från mitt program som läser in "Apan sitter, apan står.":

edit:
O = 16 bitar

D = 30787738357938930401168957289910750595392685551552655918
Sqrting................................................................................
..................
C^2 = 30787738357938930401168957285429447062712379656933230225
C = 5548669962967605663138258985
diff = 4481303532680305894619425693
O = 26464
30787738357938930401168957289910648292570006496206023370 <= 30787738357938930401
168957289910750595392685551552655918 <= 3078773835793893040116895728991081762453
9091200968692384
.. holds true!

edit2:
Yarrick: Du borde göra så att programmet kollar vidare, så att de vet att det inte finns fler lösningar...

edit3:
Ny utmatning(denna gång med 30 bitar):
D = 30787738357938930401168957289910750595392685551552655918
Sqrting.........................................................................
.........................
44 seconds
C^2 = 30787738357938930401168957285429447062712379656933230225
C = 5548669962967605663138258985
diff = 4481303532680305894619425693
O = 433596074
30787738357938930401168957289910750590411193044530052783 <= 30787738357938930401
168957289910750595392685551552655918 <= 3078773835793893040116895728991075060074
6396235735177458
.. holds true!
newdiff = 10335203191205124675
ratio = 1:433596074

Som dool säger så finns det INGA komprimeringsalgoritmer som packar slumpdata. D.v.s det finns ingen algoritm som kan komprimera filer en enda bit i genomsnitt.

Anledningen till detta är att algoritmen måste vara inverterbar. Säg att vi vill komprimera alla de filer som är 1000 bitar långa. Om vi antar att algoritmen klarar att komprimera alla filer 1 bit så kommer de komprimerade filerna att uppta 999 bitar styck. Hur vi än vänder och vrider på det så kommer då minst en komprimerad bitserie att representera minst två okomprimerade filer. (duvhålsprincipen)

Detta gäller oberoende av algoritm. Vad gäller just din implementation så faller den som sagt på att resten är lika stor som kvadratroten. Att du sen inte uttrycker resten i klartext (varför inte?) utan som en CRC-summa betyder bara att du har förskjutit problemet med att komprimera originalfilen till att komprimera resten. Kom ihåg att varje restterm måste ha en motsvarande CRC-summa, annars är den inte inverterbar. I bästa fall får du ett 1:1 förhållande mellan antal möjliga resttermer och antal möjliga CRC-tal. Förmodligen får du det inte, och den bästa lösningen vore därför att helt enkelt skriva resten i klartext, eller ännu bättre - behålla filen som den är.

Nu kanske någon undrar hur zip kan fungera som bevisligen gör filer mindre? Svaret är helt enkelt att zip inte alls gör alla filer mindre. Tvärtom är det faktiskt så att ganska få filer av alla möjliga filer blir mindre. Testa exempelvis att zippa en fil med slumptal eller ännu enklare: testa att zippa en redan zippad fil...

Men vänta här nu.. Borde det inte vara möjligt att komprimera ganska bra, fast med lite loss?
Iom att det hänger på CRC:ns upplösning, så skulle man kunna komprimera bilder t.ex., och ändå inte behöva bry sig om det blir fel(i motsats till om det skulle vara .exe t.ex.)
Fast det är klart... Jag tror inte att de tal som har samma CRC ligger speciellt nära varandra, så bilderna kommer isf bli helt olika. :/