zlib udfordring

Her er en sjov lille udfordring mens vi venter på jule-aften:

  • Du sidder i Langtbortistan hvor man er ved at bygge et nyt radioteleskop.

  • Dit job er at få data sendt de videnskabelige data hjem til civilizationen så billigt som muligt.

  • Inputdata: En konstant strøm af bytes, som må klippes i stykker hvor som helst, bare rækkefølgen af stumperne bevares.

  • Output data: Floppy diske der hver indeholder præcist en velformet .gz fil.

  • Den maksimale filstørrelse på floppyen skal være en køretidsparameter.

  • Vi ved endnu ikke noget om hvor godt inputdata kan komprimeres.

Skriv et program der komprimerer data således at det minimerer antallet af floppydiske.

phk

Kommentarer (12)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#5 Jacob Christian Munch-Andersen

Først konstaterer vi at Deflate formatet er et relativt dårligt komprimeringsformat designet til at slippe uden om for længst udløbne patenter og kunne anvendes på maskiner med ned til 64 kB ram. Dernæst at du har store mængder data på en specifik form. Der er en markant gevinst at hente hvis du fx kan udnytte at to tal kommer fra det samme sted på himlen med 1 ms imellem.

Jeg går ud fra at data i høj grad må betegnes som støj. Derfor: Lav den bedste forudsigelse s algoritme du kan, træk forudsigelsen fra de faktiske data, og komprimer resultat efter en forventet eller kontinuerligt målt fordeling.

Deflate har de her blokke med Huffman-træer osv. Som gør problemet lidt mere kompliceret, masser af andre formater/algoritmer kan arbitrært afbrydes når output har nået en bestemt størrelse.

Mht. Mark Adlers kode vil jeg umiddelbart mene at en realistisk størrelse på dine "floppy diske" gør at det er relativt ligegyldigt at den sidste blok bliver komprimeret tre gange.

Ved nærmere eftertanke er jeg faktisk ikke engang sikker på at hans metode er optimal.

Uden nærmere eftertanke er jeg helt sikker på at hans metode ikke er optimal. Den er blot god nok til at jeg ikke mener at det er besværet værd at forsøge at gøre det bedre.

  • 2
  • 0
#6 Poul-Henning Kamp Blogger

Først konstaterer vi at Deflate formatet er et relativt dårligt komprimeringsformat designet til at slippe uden om for længst udløbne patenter [...]

Men det er desværre også defakto standarden og indlejret i en masse standarder, så vi hænger på det meget lang tid endnu. (I tilfældet ISO28500 i princippet for evigt.)

Deflate har de her blokke med Huffman-træer osv. Som gør problemet lidt mere kompliceret,

Det er det der gør det til en sjov lille opgave :-)

  • 0
  • 0
#7 Baldur Norddahl

Antag at komprimeret data fylder to diske plus en byte, og din algoritme har maksimeret filstørrelsen på disk 1. Så er det teoretisk muligt at man kan flytte data fra disk 1 til disk 2 og faktisk opnå en smule bedre komprimering. Det er muligt at denne manøvre sparer den ene byte og dermed sparer behovet for disk 3.

Så medmindre man kan føre bevis for at ovenstående ikke er sandt for deflate, så er man nødt til at afprøve alle muligheder for at være sikker på at løsningen er den bedste der er mulig.

  • 0
  • 0
#8 Poul-Henning Kamp Blogger

Så medmindre man kan føre bevis for at ovenstående ikke er sandt for deflate, så er man nødt til at afprøve alle muligheder for at være sikker på at løsningen er den bedste der er mulig.

Der er himmelvid forskel på en lille kappedyst her for at se hvem der kan gøre det bedst, og på at gøre det optimalt.

Mit bedste resultat lige nu er et-pass kode der bare kalder standard zlib og som fylder output op til et sted i de sidste 17 bytes. Så vidt jeg kan se er tabet i komprimering i forhold til "normalt" forsvindende lille.

Optimalt vil så vidt jeg ved kræve en brute-force afsøgning af alle mulige reset-points under selve komprimeringen.

  • 0
  • 0
#9 Henrik Thostrup Jensen

Hvor entropien i dataen er meget høj kan muligvis ikke betale sig at komprimere det. Single pass komprimering og høj entropi giver sjældent gode resultater. Observation med radio teleskop er ikke noget nyt, så nogle må have en ide om dette.

Det lugter lidt af VLBI, så jeg ville starte med at spørge nogen der ved noget om VLBI data håndtering. De har i mange år gemt observationsdata på diske og sendt det. Der må findes nogle hos JIVE i Holland, eller ved observatoriet på Svalbard (UNINETT har for nyligt lagt fiber fra Longyearbyen til observatoriet, men der må stadig findes folk der ved noget om det da det har opereret i shipping mode i en del tid svjv.).

I stedet for zlib ville jeg prøve zx, og tillade den at bruge en del hukommelse, så den kan lave tabeller. Da dataene er over tid, kunne det være interessant at se om den kunne encodes til wav og køres gennem en flac encoder (film codecs gemmer primært deltaer, så jeg vil tro at audio codecs vil gøre det bedre). Er signalet to-dimensionelt (tid og spektrum) eller kan gemmes flere ting?

Der mangler en beskrivelse af om man miste data - eller hvor meget man må miste. Ved VLBI kan det nogle gange accepteres, men ved nogle eksperimenter fx IceCube observatoriet har man ikke lyst til at miste data hvis det er ved en neutrino observation.

Hvis man skal beskytte sig mod defekte medier, ville man køre det gennem noget raid 5/6, men så bliver det ret indviklet at sørge for at de komprimerede output streams hvis man laver kompression sidst. Derfor vil det være bedre at lave det af komprimerede filer og så gemme pariteten på et nyt medie.

  • 0
  • 0
#10 Ivan Skytte Jørgensen

Optimalt vil så vidt jeg ved kræve en brute-force afsøgning af alle mulige reset-points under selve komprimeringen.

Korrekt. Hvis data hidtil har indeholdt mange forekomster af "girafsliber" men få af "girafhalstørklæde", så vil huffmann-koden for girafsliber være kortere end for girafhalstørklæde (*1). Så når man kun har 1 bit tilbage på disketten og man står med data "giraf" så er man nødt til at processere det efterfølgende data for at finde ud af om det er "girafsliber" med en huffman-kode på 1 bit (som vil passe på disketten), eller det er "girafhalstørklæde" som har en huffman-kode længere end 1 bit og dermed kræver flush til disketten og reset tilbage til "giraf".

Det vil dog ikke kræve afsøgning af alle mulige reset-points. Ved ikke-komprimerbar data er overheadet 3bit pr. 64KB, så vi ved at man som minimum kan presse 22½ blokee ned på disketten med et overhead på 23*3bit = 7 bytes. Ved meget komprimerbar data kan man maksimalt prese 1.5GB ned på disketten. Så en binær søgning af hvormeget inputdata rammer præcist diskettens størrelse vil højst kræve 31 forsøg.

Det kan yderligere forberedes ved at udnytte kendskabet til deflate/LZ78, så vi ved at data komprimeres i blokke af 32KB, så den binære søgning skal maksimalt bruge 15 forsøg.

Men inden man bruger for meget tid på det, så bør man nok lige overveje om det ikke var nemmere at lægge tingene på et USB-drev :-)

Note 1: Det er en simplificering. Deflate-formatet bruger huffman-encoding af symbolerne, så det vil faktisk være huffman-koden for back-reference til første forekomst af "girafsliber" indenfor blokken.

  • 0
  • 0
#11 Allan Jensen

Lyder som et gammelt problem. Det var et standard problem på USENETs binære kanaler. Så vidt jeg husker blev defacto standard at bruge RAR istedet for zip fordi den understøtter det naturligt, derudover gjorde man ikke opdelining optimal, men brugte en paritets eller error-correction format (vist not SFV), så man kunne gendanne tabte eller korrupter posts eller floppy disks.

  • 1
  • 0
#12 Jacob Larsen

brugte en paritets eller error-correction format (vist not SFV), så man kunne gendanne tabte eller korrupter posts eller floppy disks.

SFV er kun en fil med CRC32 checksums. Dem brugte man vist godtnok engang til at checke for fejl, men der er ingen error correction i det format. Senere begyndte man at bruge PAR formatet efterfulgt af PAR2. De indeholder begge redundant data til fejlkorrektion, men PAR2 er mere fleksibelt. Hvis data skal overføres via et potentielt upålideligt medie, så vil det være en god idé at inkludere noget redundans med nogle PAR2 filer.

  • 0
  • 0
Log ind eller Opret konto for at kommentere