[C++/Hex] Offsets lezen en schrijven van hex-pairs

[Arcane Apex]

Verwijderd schreef op maandag 16 augustus 2010 @ 17:00:
[...]

Wie zegt dat "alle situaties" betekent dat alle ASCII tekens kunnen voorkomen? Alle situaties kan ook duiden op alle willekeurige woorden van willekeurige lengte opgebouwd uit alfabetische karakters... En het lukt je niet om een bestand met "hallo" en tussen iedere letter 1 miljard spaties te reduceren tot 5 bytes.

De leraar was vrij duidelijk over dat het alle karakters betreft in zowel de ASCII alswel Extended ASCII set. De term "alle situaties" gebruikte ik zelf om het uit te kunnen leggen, maar dat waren niet de exacte woorden van de leraar. Mijn excuses als het allemaal wat vaag overkomt.

[danslo]

Naieve implementatie en een beetje voorkauwen, maar was toch wel even leuk om m'n C kennis weer even naar boven te halen

[ Voor 18% gewijzigd door danslo op 16-08-2010 20:50 . Reden: pastebin expired ]

[Killemov]

Je kunt het vraagstuk filteren of lossless comprimeren niet onbeantwoord laten.

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:48[/message]:
De spaties moeten er inderdaad gewoon tussenuit, maar het proces moet niet onomkeerbaar zijn.
Tevens dient men in het geoptimaliseerde bestand de tekst gewoon te kunnen lezen zonder de spaties.
Dus de volgorde van de karakters dient in het geoptimaliseerde bestand gewaarborgd te blijven.

... je hebt het over filteren.

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:48[/message]:
De crux is dat er voor de spaties geen extra bits of bytes gebruikt mogen worden in het geoptimaliseerde bestand, vandaar dat ik dus dacht/denk dat de oplossing op de 1 of andere manier ligt in wellicht de afstand tussen de bytes en/of de adressering van de bytes. Men moet de data van die spaties toch ergens kwijt.

... je impliceert compressie.

[.oisyn]

Verwijderd schreef op maandag 16 augustus 2010 @ 17:05:
@oisyn: voor het gemak "vindt" ik dat een bestandsnaam ook een bestand is, alleen op een andere plek.

Prima dat jij dat vindt, maar de opdracht heeft het duidelijk over het minimaliseren van de bestandsgrootte van de .txt file. De bestandsnaam is niet per se 1:1 gekoppeld aan het bestand en telt al helemaal niet mee in de grootte van dat bestand in menig filesysteem.

[ Voor 18% gewijzigd door .oisyn op 16-08-2010 17:11 ]

[EddoH]

.oisyn schreef op maandag 16 augustus 2010 @ 17:10:
[...]

... maar de opdracht heeft het duidelijk.....

[Arcane Apex]

.oisyn schreef op maandag 16 augustus 2010 @ 17:01:
3) je mag de bestandsnaam gebruiken om informatie in op te slaan.

Daarmee zou dan wel een regel van de opdracht overtreden worden, want de leraar kan ons een 100MB .txt bestand gaan voorschotelen. Ik vermoed dat men nooit genoeg data in de bestandsnaam en zelfs bestandsattributen kwijt zal kunnen om de klus voor zo'n groot bestand te klaren.

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 17:08:
[...]


De leraar was vrij duidelijk over dat het alle karakters betreft in zowel de ASCII alswel Extended ASCII set. De term "alle situaties" gebruikte ik zelf om het uit te kunnen leggen, maar dat waren niet de exacte woorden van de leraar. Mijn excuses als het allemaal wat vaag overkomt.

Goed in dat geval: "Een willekeurige reeks bytes bevat een grote hoeveelheid 0x20 bytes. Maak een algoritme dat hierop compressie toepast. De efficientie is niet van belang."

In dit geval is de oplossing:
"Sla één 1-bit op, de volgende 8 bit (die dus over 2 bytes verdeeld is) bevatten een bytewaarde. Sla een 0-bit op, de volgende 8 bit (die dus over 2 bytes verdeeld is) bevatten het aantal 0x20 bytes. Combineer deze twee regels zodat het overeen komt met de gegeven input string."

Deze oplossing kan vrij eenvoudig grotere bestanden tot gevolg hebben dan het origineel en levert bovendien niets leesbaars op. Natuurlijk kan het een en ander gehusseld worden om de leesbaarheid te verbeteren. Bijvoorbeeld eerst alle niet-0x20 bytes, dan een reeks bytes die de genoemde 1-bits en 0-bits bevat en dan de 0x20 langte-bytes.

[Verwijderd]

@TS:

Probeer eens de opdracht van begin tot einde nogmaals te beschrijven waarbij je de verwoording van de docent los weergeeft van jouw eigen interpretatie.

Nu snapt niemand er iets van eigenlijk, waarschijnlijk jij zelf ook niet.

[.oisyn]

EddoH schreef op maandag 16 augustus 2010 @ 17:11:
[...]

Dat de opdracht op zich niet duidelijk is wil niet zeggen dat het verder ook geen duidelijke punten aanstipt.

Het doel is optimalisatie van de bestandsgrootte.

[ Voor 10% gewijzigd door .oisyn op 16-08-2010 17:16 ]

[Killemov]

.oisyn schreef op maandag 16 augustus 2010 @ 17:10:
Prima dat jij dat vindt, maar de opdracht heeft het duidelijk over het minimaliseren van de bestandsgrootte van de .txt file. De bestandsnaam is niet per se 1:1 gekoppeld aan het bestand en telt al helemaal niet mee in de grootte van dat bestand in menig filesysteem.

+1

Zolang de TS geen uitsluitsel geeft in de keuze tussen filteren en compressie blijft het allemaal giswerk.

[EddoH]

.oisyn schreef op maandag 16 augustus 2010 @ 17:14:
[...]

Dat de opdracht op zich niet duidelijk is wil niet zeggen dat het verder ook geen duidelijke punten aanstipt.

Weet ik, ik moest alleen even lachen. Je opmerking makes sense

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 17:13:
[...]


Daarmee zou dan wel een regel van de opdracht overtreden worden, want de leraar kan ons een 100MB .txt bestand gaan voorschotelen. Ik vermoed dat men nooit genoeg data in de bestandsnaam en zelfs bestandsattributen kwijt zal kunnen om de klus voor zo'n groot bestand te klaren.

Dat ligt dus aan het filesystem, maar toch: je gebruikt bytes voor de bestandsnaam en dus schijfruimte. In feite wordt dus geen compresie toegepast.

Als je perse die weg op wilt: "Neem het bestand hallo.txt. Codeer de inhoud van het bestand volgens BASE-64 codering. Hernoem het bestand naar het resultaat van deze codering. Vul de inhoud van het bestand met het woord hallo."

Dit "voldoet" volgens jou aan de beschrijving, maar zorgt ervoor dat iedere 3 bytes bestand 4 bytes filename innemen, terwijl de inhoud van het bestand geen informatie meer bevat...

[Killemov]

Verwijderd schreef op maandag 16 augustus 2010 @ 17:13:
"Sla één 1-bit op, de volgende 8 bit (die dus over 2 bytes verdeeld is) bevatten een bytewaarde. Sla een 0-bit op, de volgende 8 bit (die dus over 2 bytes verdeeld is) bevatten het aantal 0x20 bytes. Combineer deze twee regels zodat het overeen komt met de gegeven input string."

Dat is de run-length variant van mijn eerder genoemde dictionary oplossing.

[Verwijderd]

Killemov schreef op maandag 16 augustus 2010 @ 17:20:
[...]


Dat is de run-length variant van mijn eerder genoemde dictionary oplossing.

Ik gebruik geen dictionary, maar harcode de functie van 0x20 in hat algoritme

[RobIII]

Gebruik een ADS (Simpele uitleg)
Ik wed dat je menig leraar versteld kunt laten staan dat je meerdere Gb in 1 byte-grote files kunt stoppen (En dat je de inhoud van die ene byte ook nog vrij kunt aanpassen en je "decompressie" toch blijft werken )

Verder: Het is inmiddels wel duidelijk dat of je interpretatie van de opdracht niet klopt, of de opdracht niet klopt. Either way: hier klopt iets heel erg niet.

[ Voor 41% gewijzigd door RobIII op 16-08-2010 17:30 ]

[.oisyn]

Verwijderd schreef op maandag 16 augustus 2010 @ 17:23:
[...]

Ik gebruik geen dictionary, maar harcode de functie van 0x20 in hat algoritme

Het zijn beiden huffman codings, waarbij Killemov een enkele spatie in 1 bit op kan slaan, terwijl jij
1 t/m 256 spaties in 9 bits op kan slaan.

Dat de dictionary niet dynamisch is impliceert niet meteen dat hij er niet is . Bij Killemov was hij trouwens ook statisch.

[ Voor 56% gewijzigd door .oisyn op 16-08-2010 17:34 ]

[Mini-me]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:53:
[...]

Op de opleiding Computer Science moeten we voor het vak compressie bestandsgroottes leren optimaliseren. Zoals je waarschijnlijk wel hebt gelezen dient dit op een hele specifieke manier te gebeuren waarbij we niet mogen cheaten en de opdracht dus heel specifiek afgebakend is. Het algoritme moet wel echt werken voor alle situaties, dus alle karakters van de ASCII set en Extended ASCII set.

Optimalisatie is 1 van de onderdelen van compressie.

Misschien een stomme vraag, maar welke algoritmes zijn er tot nu toe in je college voorbij gekomen? Is er niet toevallig eentje die je simpelweg hier kunt gebruiken?

[Janoz]

Ik heb een donker bruin vermoeden dat de grootste denkfout in dit topic is dat de vreemde eigenschappen van het voorbeeld onterecht worden geextrapoleerd naar alle oplossingen. Volgens mij is de eis dat de originele tekens in dezelfde volgorde moeten blijven staan, maar dan zonder spaties een interpretatie van de topicstarter zelf die met open ogen in de valkuil trapt die de docent neergelegd heeft voor deze opdracht.

Dat h__a_l___l____o toevallig hallo oplevert betekent niet automatisch dat alle andere tekstbestanden ook leesbaar moeten blijven.

[Verwijderd]

Genoeg ideeën om compressie/optimalisatie en decompressie toe te passen. Het loopt stuk op 1 ding: wat zijn de eisen voor de compressed file? Heb het topic nu 3 keer nagelezen maar er zit minimaal 1 fout in de voorwaarden voor de compressed file. Zonder een nieuwe, juiste en volledige omschrijving gaan we hier niet uit komen.

edit: voor de 4e keer de opdracht doorgenomen (Arcane Apex in "\[C++/Hex] Offsets lezen en schrijven van...")

Het blijft even een gokje maar ik denk dat het voorbeeld wat bij deze post staat niet bij de orginele opdracht hoort.

Het antwoord van RoadRunner84 (Verwijderd in "\[C++/Hex] Offsets lezen en schrijven van...") zou wel eens je best passende antwoord kunnen zijn. (cq die van CLS, zie hieronder)

[ Voor 42% gewijzigd door Verwijderd op 16-08-2010 20:54 ]

[danslo]

cls schreef op maandag 16 augustus 2010 @ 17:09:
Naieve implementatie en een beetje voorkauwen, maar was toch wel even leuk om m'n C kennis weer even naar boven te halen

C:

#include <stdio.h>
#include <string.h>

typedef char i8;
typedef unsigned short u16;
typedef unsigned int u32;

void dump(char *data, u32 size) {
    u32 i = 0;
    for(;i < size; i++) {
        printf("%.2X ", data[i]);
    }
    putchar(10);
}

int compress(i8 *data, u32 size, i8 *out) {
    // We don't allow data to start with a space.
    if(*data == 32) {
        return -1;
    }
    
    i8 *p = data;
    while(p != data + size) {
        // Only a-z are valid.
        if(*p < 'a' || *p > 'z') {
            fprintf(stderr, "Encountered invalid character: %.2X\n", *p);
            return -1;
        }
        
        // Base character.
        *out = *p - 'a';
        
        // Count spaces after current character.
        u32 spaces = 0;
        while(*(++p) == 32) {
            spaces++;
        }
        
        // Only have room for a maximum of 7 spaces.
        if(spaces > 7) {
            fprintf(stderr, "This implementation only allows a maximum of 7 spaces after every character.\n");
            return -1;
        }
        
        // Write the result.
        *(out++) |= (spaces << 5);
    }
    return 0;
}

void decompress(i8 *data, u32 size, i8 *out) {
    i8 *p = data;
    while(p != data + size) {
        // Extract 5 right-most bits.
        *(out++) = (*p & 31) + 'a';
        
        // Append spaces.
        u32 i = 0;
        for(; i < *p >> 5; i++) {
            *(++out) = 32;
        }
        p++;    
    }
}

int main() {
    i8 in[12] = "h   el  l  o";
    i8 out[5]; 
    
    // Show compression.
    dump(in, sizeof(in));
    if(compress(in, sizeof(in), out) < 0) {
        fprintf(stderr, "Compression failed.\n");
        return -1;
    }
    dump(out, sizeof(out));
    
    // Show decompression.
    memset(in, 0, sizeof(in));
    decompress(out, sizeof(out), in);
    dump(in, sizeof(in));

    return 0;
}

Toch maar even zo, pastebin doet hier nogal vaag (expiren terwijl ik hem gewoon op Forever had )

[ReenL]

Wat we weten is hoe de originele tekst eruit ziet en hoe het gecomprimeerde bestand eruit moet zien.

Het is duidelijk dat 33% compressie dus niet te garanderen valt. Het aantal spaties kan immers variabel zijn. Hoe ga je dat doen met een bestand zonder spaties? Daarvan is de output immers _exact_ de input.

Wat me opvalt is dat iedereen probeert spaties te verwijderen en dan posities op te slaan.

Waarom gaat niemand ervan uit dat "ha" de meta data is en "llo" de gecomprimeerde data? Natuurlijk kan dat ook op bit niveau. Om de scheiding tussen data en meta-data dan aan te geven kun je het bestand een nummer als bestandsnaam geven, dit nummer geeft aan vanaf welk teken (of bit) de data begint.

Helaas is mijn theoretische kennis van comprimeren beperkt tot base64 (?!) en huffman. Maar ik hoop dat ik hiermee een zetje in de goede richting geef.

[RobIII]

ReenL schreef op maandag 16 augustus 2010 @ 21:32:
Helaas is mijn theoretische kennis van comprimeren beperkt tot base64 (?!)

Base64 is geen compressie maar een encoding If anything dan wordt een bestand na base64 zelfs groter (gemiddeld ~1.333333 keer)

[ Voor 19% gewijzigd door RobIII op 16-08-2010 21:46 ]

[ReenL]

RobIII schreef op maandag 16 augustus 2010 @ 21:36:
[...]

Bas64 is geen compressie maar een encoding If anything dan wordt een bestand na base64 zelfs groter (gemiddeld ~1.333333 keer)

Weet ik. Lees ook de "(?!)"...

[wijsneus]Je statement met de ~1.333333 telt alleen voor lange teksten de == neemt ook ruimte in. Tenzij de lengte van je invoer altijd deelbaar door 3 is. Significantie?[/wijsneus]

[RobIII]

ReenL schreef op maandag 16 augustus 2010 @ 21:45:
[wijsneus]Je statement met de ~1.333333 telt alleen voor lange teksten de == neemt ook ruimte in

De == is enkel padding aan 't eind van een base64 string en altijd max. 2 omdat het een base64 string altijd een veelvoud van 3 tekens lang is. En dus zul je gemiddeld genomen "rond" ( vandaar de ~ ) de 1.333333 uit komen En inderdaad is de padding een een stuk siginficanter op data van 1 of 10 bytes dan op data van 2 Mb.

Zie ook:

quote: http://en.wikipedia.org/wiki/Base64

Note that given an input of n bytes, the output will be (n + 2 - ((n + 2) % 3)) / 3 * 4 bytes long, which converges to n * 4 / 3 or 1.33333n for large n.

[ Voor 45% gewijzigd door RobIII op 16-08-2010 21:52 ]

[ReenL]

RobIII schreef op maandag 16 augustus 2010 @ 21:46:
[...]

De == is enkel padding aan 't eind van een base64 string en altijd max. 2 omdat het een base64 string altijd een veelvoud van 3 tekens lang is. En dus zul je gemiddeld genomen "rond" ( vandaar de ~ ) de 1.333333 uit komen En inderdaad is de padding een een stuk siginficanter op data van 1 of 10 bytes dan op data van 2 Mb.

Zie ook:

[...]

I know, I know, maar wat vond je van mn punt zegmaar?

[pedorus]

Verwijderd schreef op maandag 16 augustus 2010 @ 17:13:
Goed in dat geval: "Een willekeurige reeks bytes bevat een grote hoeveelheid 0x20 bytes. Maak een algoritme dat hierop compressie toepast. De efficientie is niet van belang."
[...]
Deze oplossing kan vrij eenvoudig grotere bestanden tot gevolg hebben dan het origineel en levert bovendien niets leesbaars op.

Mm, je geeft nu wel een erg lange oplossing. Ik zou dat iets anders oplossen, en neem als extra voorwaarde dat de tekst zonder spaties in het resultaat moet voorkomen. Stel je hebt de oorspronkelijke voorbeeldreeks:

68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F

We kijken nu naar de positie van de spaties (1 bij spatie, +1 extra 1 om op een hele byte uit te komen):

0 1 1 0 1 0 1 1 1 0 1 1 1 1 0 0

Dit geeft 6B BC. Toevoegen aan reeks zonder spaties geeft 6B BC 68 61 6C 6C 6F. Header staat vooraan, als header evenveel of meer 0-bits heeft als het aantal resterende tekens, dan is de header afgelopen. Zoals je ziet zijn er twee extra bytes nodig voor de positie van de spaties, maar een aantal bytes daarvoor is sowieso onoverkomelijk, of je moet Jan Sloot heten.

Voor de spaties is de compressie in dit voorbeeld overigens 8/10, dus er blijft zelfs minder dan 1/3 over..

[Reptile209]

Pedorus: grappige aanpak! Je mist alleen iets van een scheidingsteken (00 bijv) om de 'spaties' van de 'tekst' te scheiden. Nu heb je voorkennis dat de header 2 bytes is, bij een 100 MB tekstfile heb je die kennis niet.

Je redt overigens de compressie tot 33% niet, omdat je nu van 15 naar 2+5=7 bytes gaat (47%).

[Verwijderd]

mooie aanpak pedorus!

[Verwijderd]

Reptile209 schreef op dinsdag 17 augustus 2010 @ 06:51:
Pedorus: grappige aanpak! Je mist alleen iets van een scheidingsteken (00 bijv) om de 'spaties' van de 'tekst' te scheiden. Nu heb je voorkennis dat de header 2 bytes is, bij een 100 MB tekstfile heb je die kennis niet.

Je redt overigens de compressie tot 33% niet, omdat je nu van 15 naar 2+5=7 bytes gaat (47%).

Nee hoor, dat doet ie niet. Hij meldt ook: het aantal 0-bits in de header moet overeenkomen met de restgrootte van het bestand. Door dus te weten dat 7 bytes - 2 bytes = 5 bytes en het aantal 0-bits in diezelfde eerste twee bytes gelijk is aan 5 er dus een match van 5 == 5 is en daarmee de header afgelopen.

[.oisyn]

Het aantal 0-bits is trouwens 6, door padding, maar dat maakt op zich niet uit, je moet tellen tot je op het aantal restbytes uitkomt.

Overigens is de oplossing van pedorus net zo efficient als die van RoadRunner Killemov, met het verschil dat de tekst in de oplossing van pedorus leesbaar blijft.

[Woy]

Op zich een leuke oplossing voor een van de interpretaties van het probleem, maar de kern van het verhaal lijkt me nog steeds dat het belangrijk is om helder te krijgen wat de opdracht nou exact is.

Zonder een duidelijke opdracht is de kans ook erg klein dat je een gewenste oplossing krijgt

[Soultaker]

.oisyn schreef op dinsdag 17 augustus 2010 @ 10:42:
Overigens is de oplossing van pedorus net zo efficient als die van RoadRunner, met het verschil dat de tekst in de oplossing van pedorus leesbaar blijft.

Je bedoelt Killemov in plaats van RoadRunner denk ik? Roadrunner suggereerde een run-length encoding van spaties die minder efficiënt is voor gewone tekst waarbij series van meer dan één spatie zeldzaam zijn.

Ik zie persoonlijk het nut van het partitioneren van de codes niet zo. Als je toch een Huffman coding doet, zou ik gewoon bytes vertalen naar bitstrings en die achter elkaar plakken à la Killemov. Zou je eventueel nog een zinnige codering kunnen kiezen voor de andere karakters dan spaties, maar dat maakt 't natuurlijk wel iets ingewikkelder.

[.oisyn]

Soultaker schreef op dinsdag 17 augustus 2010 @ 11:59:
[...]

Je bedoelt Killemov in plaats van RoadRunner denk ik?

Euh ja idd, helemaal gelijk in.

Ik zie persoonlijk het nut van het partitioneren van de codes niet zo. Als je toch een Huffman coding doet, zou ik gewoon bytes vertalen naar bitstrings en die achter elkaar plakken à la Killemov. Zou je eventueel nog een zinnige codering kunnen kiezen voor de andere karakters dan spaties, maar dat maakt 't natuurlijk wel iets ingewikkelder.

Eens

[pedorus]

offtopic:
knip onzin

[ Voor 97% gewijzigd door pedorus op 17-08-2010 18:18 ]

[davince72]

@Arcane Apex / @TS Kun je even een update geven? Deze hele topic begon uiterst ongelukkig, maar er bleek uiteindelijk een leuke opdracht aan ten grondslag te liggen. Nu ben ik nieuwsgierig. Dus geef svp een update omtrent de exacte opdrachtformulering, want nu wil ik ook weten of ik voor het (juiste) probleem een oplossing kan bedenken.

@RobIII: bedankt voor het verwijzen naar ADS. Nice!

[Soultaker]

pedorus schreef op dinsdag 17 augustus 2010 @ 14:23:
Overigens is er nog wel een randgeval als het bestand eindigt op meer spaties dan er padding over is, zeg h__a_l___l____o__. In dat geval moet de [originele bytestream zonder spaties] aangevuld worden met 1 spatie, dus dan krijg je 6B BD 00 68 61 6C 6C 6F 20.

Nee, niet. Dan kun je prima padden of eindigen met 0. In jouw voorbeeld codeer je: 01101011, 10111101, 10xxxxxx, 'h', 'a', 'l', 'l', 'o' (waarbij de waade van x eigenlijk niet uitmaakt, maar laten we zeggen x=0).

De padding van Killemov kan op precies dezelfde manier werken. Dat is niet zo gek omdat .oisyn al had vastgesteld dat jullie precies hetzelfde doen. Jij kiest er alleen voor om de eerste bit van elke code helemaal naar links te schuiven.

[ Voor 23% gewijzigd door Soultaker op 17-08-2010 15:54 ]

[pedorus]

Soultaker schreef op dinsdag 17 augustus 2010 @ 15:50:
[...]

Nee, niet. Dan kun je prima padden of eindigen met 0. In jouw voorbeeld codeer je: 01101011, 10111101, 10xxxxxx, 'h', 'a', 'l', 'l', 'o' (waarbij de waade van x eigenlijk niet uitmaakt, maar laten we zeggen x=0).

De padding van Killemov kan op precies dezelfde manier werken. Dat is niet zo gek omdat .oisyn al had vastgesteld dat jullie precies hetzelfde doen. Jij kiest er alleen voor om de eerste bit van elke code helemaal naar links te schuiven.

Hmm, ik zat inderdaad naar problemen te kijken die er niet zijn (niet genoeg bij de les he ). Als de header eentje langer wordt, dan ben je natuurlijk niet genoeg niet gezette bits tegengekomen om te denken dat je klaar bent. Killemov doet in principe hetzelfde inderdaad, enkel die oplossing geeft niet de originele bytes natuurlijk.

Verder blijft het afwachten wat nu de echte probleemstelling is.

[Arcane Apex]

Ok, ik heb antwoord van de leraar. (Hij heeft de thread gelezen)

Ik begrijp het volgens hem wel correct alleen heb ik de voorwaarden van de opdracht door de thread heen verspreid. Niet alle voorwaarden staan dus in de 1ste post, maar die heb ik dan weer in latere replies neergezet waardoor het niet direct compleet duidelijk is voor de mensen die alleen de 1ste post lezen, dus wellicht is het handig dat ik de 1ste post aanpas of een nieuwe reply maak met alle voorwaarden netjes op een rijtje ipv verspreid over de thread. Desondanks hebben veel mensen in de thread toch de opdracht begrepen, ook al heb ik het wat onduidelijk uitgelegd.

Excuses als ik het wat vaag opgeschreven heb, want we hebben dus geen opdrachtsheet gekregen voor deze opdracht, maar het is wel in de les uitgelegd.

Ik ben inmiddels wel een stukje verder. Ik heb aan iemand met verstand van filesystems gevraagd of het mogelijk
is om een byte heel specifiek op een bepaalde adres op de schijf op te slaan en het adres als (extra) data te gebruiken om informatie in kwijt te kunnen van de spaties. Dit schijnt niet mogelijk te zijn, want je kan ten eerste een byte niet (zomaar) plaatsen op de plek waar je zelf wilt. Dit zou niet alleen de data op de schijf in gevaar brengen, maar technisch gezien is het gewoon niet mogelijk om in een filesystem te gaan fragmenteren op sub-sector of sub-block niveau, want dat is in essentie wat ik voorstelde. De (API's van de) bestandssystemen schijnen hier niet op ontworpen te zijn. Ik ga daarbij uit van de expertise van iemand anders, maar dat betekent uiteraard niet dat het niet mogelijk zou zijn wanneer zo'n filesystem wel geschreven zou worden voor een dergelijke toepassing, maar ik denk niet dat dat de bedoeling is van
de opdracht.

Wel kan men gaan schuiven met bytes dmv hex-editors, maar dat heeft slechts effect op de relatieve offsets van een byte in een bestand, maar dat wist ik al wel.

Dus het gebruiken van byte-adressen als data sluit ik hiermee uit als optie. Wellicht zou het op 1 of andere manier wel mogelijk zijn door een filesystem daarvoor aan te passen of een filesystem specifiek voor dat doel te schrijven, maar dat gaat de opdracht denk ik te boven.

[ Voor 5% gewijzigd door Arcane Apex op 17-08-2010 23:40 ]

[RobIII]

Arcane Apex schreef op dinsdag 17 augustus 2010 @ 23:26:
Ik ben inmiddels wel een stukje verder. Ik heb aan iemand met verstand van filesystems gevraagd of het mogelijk is om een byte heel specifiek op een bepaalde adres op de schijf op te slaan en het adres als (extra) data te gebruiken om informatie in kwijt te kunnen van de spaties. Dit schijnt niet mogelijk te zijn, want je kan ten eerste een byte niet (zomaar) plaatsen op de plek waar je zelf wilt. Dit zou niet alleen de data op de schijf in gevaar brengen, maar technisch gezien is het gewoon niet mogelijk om in een filesystem te gaan fragmenteren op sub-sector of sub-block niveau, want dat is in essentie wat ik voorstelde. De (API's van de) bestandssystemen schijnen hier niet op ontworpen te zijn. Ik ga daarbij uit van de expertise van iemand anders, maar dat betekent uiteraard niet dat het niet mogelijk zou zijn wanneer zo'n filesystem wel geschreven zou worden voor een dergelijke toepassing, maar ik denk niet dat dat de bedoeling is van
de opdracht.

Zijn we nou écht weer terug bij filesystems, bytes op offsets en die kraam? Was het je écht nog niet duidelijk uit dit topic dan?

Arcane Apex schreef op dinsdag 17 augustus 2010 @ 23:26:
Wel kan men gaan schuiven met bytes dmv hex-editors, maar dat heeft slechts effect op de relatieve offsets van een byte in een bestand, maar dat wist ik al wel.

WTF heeft dat met compressie te maken? Ik snap met de seconde minder van dit topic...

Arcane Apex schreef op dinsdag 17 augustus 2010 @ 23:26:
Dus het gebruiken van byte-adressen als data sluit ik hiermee uit als optie. Wellicht zou het op 1 of andere manier wel mogelijk zijn door een filesystem daarvoor aan te passen of een filesystem specifiek voor dat doel te schrijven, maar dat gaat de opdracht denk ik te boven.

Laat.
Dat.
Filesystem.
Idee.
Nou.
GAAN.

Arcane Apex schreef op dinsdag 17 augustus 2010 @ 23:26:
PS: Deze opdracht is niet voor een cijfer maar gewoon huiswerk.

PS: Laat die leraar aub even de opdracht plaatsen zoals 'ie bedoeld is. Hier is werkelijk koek noch hout van de klepelen.

Arcane Apex schreef op dinsdag 17 augustus 2010 @ 23:26:
Ok, ik heb antwoord van de leraar. (Hij heeft de thread gelezen)

PS2: Laat hem ook even reageren en posten wat 'ie vindt van de thread. Ik kan haast niet wachten te horen wat 'ie te zeggen heeft

[ Voor 6% gewijzigd door RobIII op 17-08-2010 23:42 ]

[.oisyn]

Zucht. Die hele filesystem-aanpak is gewoon géén oplossing. Ookal zou een dergelijk filesystem met API bestaan. Een file is een stream van bytes, hoe die ook opgeslagen wordt op het onderliggende medium. Compressie gaat over de stream, niet over de opslag.

Daarnaast vraag ik me af waarom je überhaupt een topic opent als je toch al voor jezelf bepaald hebt in welke richting je moet denken en je elk genoemd advies hier in de draad in de wind slaat.

[ Voor 66% gewijzigd door .oisyn op 17-08-2010 23:51 ]

[Arcane Apex]

RobIII schreef op dinsdag 17 augustus 2010 @ 23:41:
[...]

Zijn we nou écht weer terug bij filesystems, bytes op offsets en die kraam? Was het je écht nog niet duidelijk uit dit topic dan?


[...]

WTF heeft dat met compressie te maken? Ik snap met de seconde minder van dit topic...


[...]

Laat.
Dat.
Filesystem.
Idee.
Nou.
GAAN.


[...]

PS: Laat die leraar aub even de opdracht plaatsen zoals 'ie bedoeld is. Hier is werkelijk koek noch hout van de klepelen.


[...]

PS2: Laat hem ook even reageren en posten wat 'ie vindt van de thread. Ik kan haast niet wachten te horen wat 'ie te zeggen heeft

Mbt dat filesysteem-idee. Als ik de opdracht wil oplossen zal ik toch wel grondig enkele opties na moeten gaan. Ok het is/was misschien wat vergezocht, maar het leek me een mogelijke oplossing.

Het is overigens niet zo dat ik enkel aan dat idee vastklampte en al het advies in de thread in de wind sloeg/sla. Ik kijk wel degelijk naar de voorstellen van anderen, maar dat gaat niet zo snel ivm trial & error testing, want ik moet er zelf wel een applicatie voor schrijven, dus ik moet met meerdere zaken rekening houden dan alleen een idee ansich.

[RobIII]

Arcane Apex schreef op woensdag 18 augustus 2010 @ 00:09:
Mbt dat filesysteem-idee. Als ik de opdracht wil oplossen zal ik toch wel grondig enkele opties na moeten gaan. Ok het is/was misschien wat vergezocht, maar het leek me een mogelijke oplossing.

Je zult toch ook beseffen dat, als je het al voor elkaar kreeg, het nog geen kont met compressie te maken heeft en dat de truuk die je uit probeert te halen toch ook "ruimte" kost om de "sprongen" ergens te bewaren die je wil maken? En dat je dan net zo goed amper tot geen of een negatieve "compressie" hebt ? Los van wat .oisyn al aangeeft: je moet (willen) opereren op stream niveau en nergens anders.

Arcane Apex schreef op woensdag 18 augustus 2010 @ 00:09:
Het is overigens niet zo dat ik enkel aan dat idee vastklampte en al het advies in de thread in de wind sloeg/sla.

Met alle respect, maar daar lijkt het wel erg op; lees je eigen topic nog eens na. En nu je leraar er klaarblijkelijk naar heeft gekeken weten wij nog steeds niet wat de (juiste, volledige, eigenlijke) opdracht zou zijn.

Arcane Apex schreef op woensdag 18 augustus 2010 @ 00:09:
Ik kijk wel degelijk naar de voorstellen van anderen, maar dat gaat niet zo snel ivm trial & error testing, want ik moet er zelf wel een applicatie voor schrijven, dus ik moet met meerdere zaken rekening houden dan alleen een idee ansich.

Je moet niet met trial & error aan de gang gaan; je moet de materie begrijpen en dan daar mee gaan stoeien. Het ontbeert je (op dit moment) gewoon duidelijk nog aan een duidelijke grip op de materie. Begin eens met een héél simpele compressie (los van je opdracht voor mijn part) waarin je bijvoorbeeld haaaaaallllllloooooo probeert op te slaan in minder bytes dan de daadwerkelijke tekst en ga van daar uit verder. Naarmate je kennis beter wordt zul je ook steeds meer de onzin van de opdracht inzien (als in: waarom zou de compressed versie nog "leesbaar" moeten zijn bijvoorbeeld?)

[ Voor 9% gewijzigd door RobIII op 18-08-2010 00:24 ]

[pedorus]

Arcane Apex schreef op dinsdag 17 augustus 2010 @ 23:26:
Ik begrijp het volgens hem wel correct alleen heb ik de voorwaarden van de opdracht door de thread heen verspreid. Niet alle voorwaarden staan dus in de 1ste post, maar die heb ik dan weer in latere replies neergezet waardoor het niet direct compleet duidelijk is voor de mensen die alleen de 1ste post lezen, dus wellicht is het handig dat ik de 1ste post aanpas of een nieuwe reply maak met alle voorwaarden netjes op een rijtje ipv verspreid over de thread.

Het lijkt me wel handig om de voorwaarden op een rijtje te zetten. Als ik het teruglees zie ik ongeveer:

• We hebben een willekeurig .txt-bestand, zeg input.txt, in 8-bits ascii (zeg ISO/IEC 8859-15) dat veel spaties (0x20) bevat. Voorbeeldinhoud in hex: 68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F (h__a_l___l____o)
• Dit moet gecodeerd worden tot een bestand, zeg output.txt, wat de oorspronkelijke inhoud van input.txt bevat maar zonder de spaties, en slechts 1/3 is van het origineel. (Voor voorbeeld: 6B BC 68 61 6C 6C 6F (hallo))
• output.txt moet weer gedecodeerd kunnen worden tot input.txt, voor alle mogelijke input.txt's

Ik kan je met zekerheid zeggen dat deze opdracht niet kan (het laatste punt dan), tenzij je bepaalde extra eisen stelt aan de input, eisen stelt aan de lezer die bepaald hoe output.txt eruit ziet, gebruik kan maken van een alternate data stream, of andere fratsen uithaalt. Dit komt omdat de aanwezige spaties een entropy hebben die groter is dan niets. (Als de entropy bekend is, dan kunnen we een lower bound berekenen met Shannon's source coding theorem, die hier geeft dat compressie tot 0 bytes onmogelijk is zonder dat vrijwel zeker informatie verloren gaat.)

Overigens lukt ook de 1/3 van het origineel niet als er te kort spaties zijn.

Desondanks hebben veel mensen in de thread toch de opdracht begrepen, ook al heb ik het wat onduidelijk uitgelegd.

Ik zie nog niemand die zegt het te begrijpen eigenlijk, dus dit lijkt me sterk..

[Arcane Apex]

pedorus schreef op woensdag 18 augustus 2010 @ 00:31:
[...]

Het lijkt me wel handig om de voorwaarden op een rijtje te zetten. Als ik het teruglees zie ik ongeveer:

• We hebben een willekeurig .txt-bestand, zeg input.txt, in 8-bits ascii (zeg ISO/IEC 8859-15) dat veel spaties (0x20) bevat. Voorbeeldinhoud in hex: 68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F (h__a_l___l____o)
• Dit moet gecodeerd worden tot een bestand, zeg output.txt, wat de oorspronkelijke inhoud van input.txt bevat maar zonder de spaties, en slechts 1/3 is van het origineel. (Voor voorbeeld: 6B BC 68 61 6C 6C 6F (hallo))
• output.txt moet weer gedecodeerd kunnen worden tot input.txt, voor alle mogelijke input.txt's

Ik kan je met zekerheid zeggen dat deze opdracht niet kan (het laatste punt dan), tenzij je bepaalde extra eisen stelt aan de input, eisen stelt aan de lezer die bepaald hoe output.txt eruit ziet, gebruik kan maken van een alternate data stream, of andere fratsen uithaalt. Dit komt omdat de aanwezige spaties een entropy hebben die groter is dan niets. (Als de entropy bekend is, dan kunnen we een lower bound berekenen met Shannon's source coding theorem, die hier geeft dat compressie tot 0 bytes onmogelijk is zonder dat vrijwel zeker informatie verloren gaat.)

Overigens lukt ook de 1/3 van het origineel niet als er te kort spaties zijn.

[...]

Ik zie nog niemand die zegt het te begrijpen eigenlijk, dus dit lijkt me sterk..

Volgens mij komt de oplossing die jij (eerder) hebt gepost al heel erg in de buurt van de oplossing van de opdracht met nog 1 laatste obstakel. Zoals je zegt is het zo dat: "de aanwezige spaties een entropy hebben die groter is dan niets."

En juist dat slaat op de enige hint die we hebben gekregen, want de header in jouw oplossing zou men nog ergens kwijt moeten kunnen. Nu zou voor het voorbeeld "hallo" de oplossing zijn om de header in de filenaam te plaatsen, maar zoals gezegd zou dat een regel overtreden. Het is wel een oplossing, maar een cheat-oplossing die niet zou werken voor tekstbestanden van bijvoorbeeld 100MB.

Volgens mij komt het dan neer op waar en hoe men de header verwerkt zonder dat het proces onomkeerbaar is, maar dat is makkelijker gezegd dan gedaan.

[RobIII]

Arcane Apex schreef op woensdag 18 augustus 2010 @ 00:56:
En juist dat slaat op de enige hint die we hebben gekregen, want de header in jouw oplossing zou men nog ergens kwijt moeten kunnen. Nu zou voor het voorbeeld "hallo" de oplossing zijn om de header in de filenaam te plaatsen, maar zoals gezegd zou dat een regel overtreden. Het is wel een oplossing, maar een cheat-oplossing die niet zou werken voor tekstbestanden van bijvoorbeeld 100MB.

En dus moet je die data elders kwijt en tenzij je ADS (zie eerdere post) gaat gebruiken (wat nét zo goed een cheat is en daarbij bij de eerste-de-beste "reguliere zipactie" of "download" of whatever verloren gaat en uiteindelijk helemaal géén oplossing is) moet de data dus in de file en dus klopt de opdracht (zoals jij 'm vertelt) niet. Punt.

Arcane Apex schreef op woensdag 18 augustus 2010 @ 00:56:
maar dat is makkelijker gezegd dan gedaan.

Het is zelfs onmogelijk. Tenzij je dus de opdracht niet (goed) weergeeft of andere informatie achterwege laat. Als je de file bijvoorbeeld zou openen in een viewer die na de eerste-de-beste 0-byte kapt kun je natuurlijk na hallo een 0-byte gooien en daarachter overige informatie. Of de overige data in een output.dat file naast een output.txt opslaan. Dat soort geintjes.

De laatste andere mogelijkheid die ik zie is dit + deze eerder genoemde persoon.

[ Voor 34% gewijzigd door RobIII op 18-08-2010 01:11 ]

[Jaap-Jan]

Als ik even kort de opdracht (is dat letterlijk wat de leraar gezegd heeft, of jouw interpretatie(?)) samenvat.

Zorg dat dit:

code:

68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F

gecomprimeerd wordt naar:

code:

68 61 6C 6C 6F

en dat je aan de hand van die data weer terug kunt naar het origineel.

Ik zou willen zeggen dat dat zo goed als onmogelijk is, tenzij je een compressie- algoritme weet te bedenken/ vinden die toevallig dat resultaat oplevert. Het lijkt me wel mogelijk om een compressie te vinden die de string terugbrengt naar 5 bytes, maar dat die vijf bytes 68 61 6C 6C 6F moeten zijn is gewoon niet te doen, behalve met een toevalstreffer.

[RobIII]

Jaap-Jan schreef op woensdag 18 augustus 2010 @ 02:19:
Ik zou willen zeggen dat dat zo goed als onmogelijk is, tenzij je een compressie- algoritme weet te bedenken/ vinden die toevallig dat resultaat oplevert.

De 'compressie' is peanuts: iets als str_replace("_", "", "H_a___l_l________o") voldoet. Het is de decompressie waar 't probleem in zit dan En die toevalstreffer (lees: een algoritme dat toevallig na compressie precies die output geeft) gaat dan ook alleen maar in dat ene specifieke geval werken en in alle andere gevallen de mist in. Linksom of rechtsom: het is un-f*ckin'-possible

Maar ik vertrouw er op dat TS (of de leerkracht), na de "deadline", ons zal verlossen en de oplossing zal posten. Liefst nog de 'ideale' oplossing zoals leerkracht het voor ogen had. Want nu zijn we allemaal wel héééél nieuwschierig.

[ Voor 43% gewijzigd door RobIII op 18-08-2010 02:25 ]

[ajakkes]

Ik heb zeer weinig kaas gegeten van compressie. Maar ergens aan het begin van het topic geeft TS aan dat het niet gaat om compressie maar om optimalisatie. Ik lees ergens dat het bestand na optimalisatie 33% van het origineel moet zijn maar dat is toch echt compressie. Ik ga er dus even van uit dat dit niet vast ligt. Mede omdat een 15 byte voorbeeld h _ _ a _ l _ _ _ l _ _ _ _ o extended ascii zonder spaties al h a l l o 5 bytes is. En je dus nul ruimte overhoud.

Dan lijkt mij de oplossing van soultaker voor optimalisatie heel erg in de goede richting. Als je het verhaal een beetje omdraait zou je het kunnen opslaan als:
hallo .2.1.3.4
6B BC 68 61 6C 6C 6F 20 02 01 03 04

Hierbij is ook het het geoptimaliseerde bestand "leesbaar", slechts na de tekst hou je een onleesbaar deel over. Dit deel kan je echter wel extra optimaliseren. In mijn voorbeeld hou je van de 15 bytes 12 bytes over. De 10 bytes aan spaties zijn wel opgelagen in 5 bytes.
Voor een normale tekst zou je de compressie om moeten draaien en het aantal tekens tussen de spaties moeten opslaan en er is volgens mij 50% compressie mogelijk.

[Verwijderd]

De enige "oplossing" die voldoet aan de gegeven "opdracht" is het weten van het spatie-patroon (lees: de spaties bevatten geen informatie).
Door nou alle spaties weg te gooien is de spatieloze tekst leesbaar met 33% van het origineel. De decompressie vult dan simpelweg de spaties weer in volgens het bekende patroon.

Dit heb ik eerder genoemd als:
- na 1e letter 2 spaties
- na 2e letter 1 spatie
- na 3e/4e/5e/6e letter 3/4/5/6 spaties
- na de laatste letter geen spaties

Dit patroon komt simpelweg voort uit een enkel genoemd voorbeeld en lijkt verder geen logica te bevatten. Echter door aan te nemen dat het spatie patroon volledig voorspelbaar is en dus geen informatie bevat, kunnen alle spaties verwijderd worden zonder enige informatie verloren te laten gaan.

[EddoH]

@Arcane Apex /TS:

Er zijn in dit topic heel veel goeie en slimme compressie methoden voorbij gekomen.
Ze lopen alleen allemaal stuk op het feit dat je opdracht beschrijft dat de uiteindelijke inhoud van de file
ALEEN het woordt "hallo" mag bevatten (5 bytes).
Dit is onmogelijk mits je het originele bestand met spaties terug wilt kunnen krijgen, of de oplossing van RoadRunner84 gebruikt, waarbij je de posities van de spaties al weet, maar dat is een beetje een non-oplossing.

Is het nou zo moeilijk om van de leraar deze eis bevestigd/ontkracht te krijgen?

[ajakkes]

Huh, alleen het woord hallo.

Als je de regels:

• 33% van 15bytes is 5bytes
• hallo in extended ascii is 5bytes
• resultaat moet alle extended ascii karakters bevatten behalve de spaties

toepast

Dan klopt het dat het document alleen hallo mag bevatten.
Echter ben ik nergens tegen gekomen dat het een harde eis is dat het resultaat alleen hallo mag bevatten.

Er zit dus een probleem in een van de bovenste regels. Of we zien wat over het hoofd of een van die regels klopt niet.

[EddoH]

Arcane Apex schreef op maandag 16 augustus 2010 @ 15:42:
[...]


Bedenk een (compressie en decompressie)algoritme voor een .txt bestand met de oorspronkelijke inhoud van 15x8-bits (zie onder). Zorg dat het resultaat in 5x8-bits opgeslagen kan worden en het woord "hallo" vormt in een nieuw tekstbestand. 1/3e van de inhoud van het oorspronkelijke bestand blijft dus over in het nieuwe bestand.
[...]
Dit is het oorspronkelijk bestand dat we moeten comprimeren. Het toont het woord "h a l l o" met een aantal spaties tussen de karakters.

code:

68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F

Dit moet het resultaat worden: "hallo"

code:

68 61 6C 6C 6F

[Arcane Apex]

Heb zojuist een mail gekregen van de leraar, voor de duidelijkheid plak ik het maar direct hier:

Na alles wat beter doorgelezen te hebben blijken er toch een aantal zaken verkeerd geïnterpreteerd te zijn, maar het is goed dat dat naar voren is gekomen, want dat geeft mij de kans om duidelijkheid te scheppen, ook voor andere studenten.

Bij deze ter referentie de opdracht en regels:

1. Maak een tekstbestand aan van het type .txt

2. Open het tekstbestand in een hex-editor en plaats daarin als inhoud de volgende (hexadecimale) byte-reeks: 68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F

3a. Schrijf een (lossless) algoritme welke de spaties tussen alle (non-spatie) karakters verwijderd. De output, dus het nieuwe tekstbestand dient de volgende byte-reeks te bevatten, waarbij de volgorde van de karakters gewaarborgd blijft: 68 61 6C 6C 6F

Maar dit betekent niet dat je niets voor of achter deze byte-reeks mag plaatsen, je mag dus
best de (spatie)data voor of achter je hallo-reeks kwijt. Zolang je dit maar doet op een manier
welke ervoor zorgt dat de output kleiner is dan de input en de 68616C6C6F-reeks intact blijft.
(Hiermee heb ik nu de hint prijsgegeven/verklapt, maar de opdracht/regels in deze e-mail
worden verstuurd naar alle studenten, zodat iedereen over dezelfde informatie beschikt.)

3b. De compressiefactor doet er niet toe, zolang er maar sprake is van compressie.
Een hoge mate van (lossless) compressie is uiteraard altijd wenselijk, maar niet
verplicht om de opdracht succesvol te voltooien.

3c. Het inputbestand dat jullie krijgen zal nooit situaties bevatten waarbij er meer dan 256 spaties voor een karakter staan.

3d. Situaties waarbij (non-spatie) karakters direct naast/achter elkaar geplaatst staan zonder spaties ertussen kunnen wel voorkomen.

4. Schrijf tevens een algoritme welke het proces om kan keren, waarbij de output dus weer
gelijk is aan de originele input, namelijk: 68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F
Dit komt zoals eerder aangegeven dus neer op een lossless algoritme.

5. Naast het woord 'hallo' met de spaties ertussen zal je algoritme/applicatie elke input moeten
kunnen accepteren uit de ASCII en Extended ASCII karaktersets.

6. Cheaten door niet-schaalbare hacks te gebruiken is niet toegestaan. Een voorbeeld van een hack welke niet schaalbaar is is het gebruik van de filename of file attributes om data in op te slaan. Dit zijn hacks die niet zullen werken wanneer je met grote bestanden gaat werken vanwege de beperkingen van filenames en file attributes. Je algoritme/applicatie zal dus niet mogen choken op een bestand van bijvoorbeeld 200MB.

7. Wanneer je algoritme/applicatie voldoet aan alle bovengenoemde regels heb je de opdracht voltooid. In aankomende lessen zul je je applicatie verder moeten gaan uitbreiden door de bekende pre-compressie- en compressie-algoritmen erin te verwerken.

Als er nog vragen zijn of dingen nog niet helemaal duidelijk zijn dan hoor ik het wel.

[EddoH]

Edit:
Nou...tadaaaa

Kies je oplossing en off you go. Genoeg varianten in dit topic

[ Voor 96% gewijzigd door EddoH op 18-08-2010 10:05 ]

[Verwijderd]

Juist, nou is de opdracht realiseerbaar. Het enige punt waar nu nog een echte uitdaging in zit is dat het aantal spaties in de reeks [0..256] valt en dus net niet in een byte past... maar dat is alleen maar een uitdaging, geen onoverkomelijk probleem.

hint: in het gecomprimeerde bestand zonder spaties zal gegarandeerd geen spatie voorkomen. Je kunt dus het spatie karakter gebruiken om de tekst en de spatie-data van elkaar te scheiden zonder ooit een conflict te veroorzaken.

[Arcane Apex]

Verwijderd schreef op woensdag 18 augustus 2010 @ 10:11:
Juist, nou is de opdracht realiseerbaar. Het enige punt waar nu nog een echte uitdaging in zit is dat het aantal spaties in de reeks [0..256] valt en dus net niet in een byte past... maar dat is alleen maar een uitdaging, geen onoverkomelijk probleem.

hint: in het gecomprimeerde bestand zonder spaties zal gegarandeerd geen spatie voorkomen. Je kunt dus het spatie karakter gebruiken om de tekst en de spatie-data van elkaar te scheiden zonder ooit een conflict te veroorzaken.

Ik denk dat het me nu wel moet gaan lukken. Dat van die 256 spaties viel me ook al op, het feit dat dat net buiten een enkele byte valt is vrij geniepig inderdaad.

[ajakkes]

Ik vindt het raar om de grens bij 256 te leggen ipv 255 en vermoedt dat dit een kleine denkfout is. Maar het is inderdaad niet onmogelijk.

De oplossing lag veel dichterbij dan gedacht.
De fout lag volgens mij in de aanname dat 33% compressie bereikt moest worden.

[RobIII]

Verwijderd schreef op woensdag 18 augustus 2010 @ 10:11:
Juist, nou is de opdracht realiseerbaar. Het enige punt waar nu nog een echte uitdaging in zit is dat het aantal spaties in de reeks [0..256] valt en dus net niet in een byte past... maar dat is alleen maar een uitdaging, geen onoverkomelijk probleem.

En ik vermoed dat de leraar 255 heeft bedoeld. Desondanks blijf ik de opdracht wat raar en knullig vinden*, ondanks dat 'ie nu mogelijk is. (En sinds wanneer hanteren leraren termen als "choken" )

edit: /laat

* Waarom zou je het .txt bestand in een hex-editor moeten openen als "h__a_l___l____o" typen in notepad volstaat (Waarbij een _ een spatie is uiteraard) Verder zul je niet in alle situaties een compressie kunnen garanderen, en dat eist de opdracht nog steeds (3b - "zolang er maar sprake is van compressie"). In een bestand met 0 spaties en alleen de tekst "abc" zul je, at best, 0 compressie halen.

Ik blijf reikhalzend nieuwschierig naar het algoritme (compressie en decompressie) van je leerkracht.

[ Voor 30% gewijzigd door RobIII op 18-08-2010 10:34 ]

[danslo]

Zolang je dit maar doet op een manier welke ervoor zorgt dat de output kleiner is dan de input en de 68616C6C6F-reeks intact blijft.

Oftewel: niks 33%

[Verwijderd]

RobIII schreef op woensdag 18 augustus 2010 @ 10:27:
[...]

En ik vermoed dat de leraar 255 heeft bedoeld. Desondanks blijf ik de opdracht wat raar en knullig vinden*, ondanks dat 'ie nu mogelijk is. (En sinds wanneer hanteren leraren termen als "choken" )

[...]Verder zul je niet in alle situaties een compressie kunnen garanderen, en dat eist de opdracht nog steeds (3b - "zolang er maar sprake is van compressie"). In een bestand met 0 spaties en alleen de tekst "abc" zul je, at best, 0 compressie halen.

Ik blijf reikhalzend nieuwschierig naar het algoritme (compressie en decompressie) van je leerkracht.

Ik vermoed dat hij niet meer of precies 256 spaties bedoeld, maar ach, zelfs met een range [0..256] is het te doen, alleen veel minder triviaal.

Compressie met een negatieve factor is ook compressie

Ik ben ook wel benieuwd, TS zal ons na de deadline vast op de hoogte stellen toch?

[.oisyn]

Ik noemde het eerder al maar het viel niemand op. 256 spaties is helemaal geen probleem. Er is namelijk geen enkele reden om 0 spaties te encoderen. Met 1 byte kun je dus 1 tot en met 256 spaties aangeven.
.oisyn in "\[C++/Hex] Offsets lezen en schrijven van..."

[ Voor 16% gewijzigd door .oisyn op 18-08-2010 11:05 ]

[RobIII]

Verwijderd schreef op woensdag 18 augustus 2010 @ 10:49:
Compressie met een negatieve factor is ook compressie

Compressie impliceert dat een bestand kleiner wordt, anders is het hele proces van compressie zinloos natuurlijk. Compressie met een negatieve compressiefactor ook compressie noemen is misschien leuk taalkundig gezien maar dan houdt het dan ook op.

.oisyn schreef op woensdag 18 augustus 2010 @ 11:04:
Ik noemde het eerder al maar het viel niemand op. 256 spaties is helemaal geen probleem. Er is namelijk geen enkele reden om 0 spaties te encoderen. Met 1 byte kun je dus 1 tot en met 256 spaties aangeven.
.oisyn in "\[C++/Hex] Offsets lezen en schrijven van..."

Goodmeuning!

[ Voor 33% gewijzigd door RobIII op 18-08-2010 11:05 ]

[ajakkes]

@ RobIII
Lossless compressie die ook in de minst ideale omstandigheid een kleiner bestand oplevert.

Dan zal je in ieder geval nutteloze info weg moeten gooien.

Nu zit er in (extended) ascii volgens mij wel een beetje nutteloze info maar ook dat lijkt me niet de bedoeling.

3b. De compressiefactor doet er niet toe, zolang er maar sprake is van compressie.
mist naar mijn mening: van het voorbeeld en/of in veel gevallen.

Edit:
@ .oisyn
hoe encode je __hal_256x_l__o_ dan?
Volgens mij moet je wel degelijk aangeven of ergens 0 of (1 of meer) spaties staan.

[ Voor 14% gewijzigd door ajakkes op 18-08-2010 11:12 . Reden: .oisyn later gelezen ]

[pedorus]

ajakkes schreef op woensdag 18 augustus 2010 @ 11:08:
3b. De compressiefactor doet er niet toe, zolang er maar sprake is van compressie.
mist naar mijn mening: van het voorbeeld en/of in veel gevallen.

Dat denk ik ook. Als je het woord hottentottententententoonstelling hebt, waar je een spatie op een willekeurige plek zet dan zul je niet in alle gevallen compressie kunnen laten zien. Sterker nog, ik denk dat het in geen enkel geval meer compressie dan 0 bytes (=geen compressie) zal opleveren..

Edit:
@ .oisyn
hoe encode je __hal_256x_l__o_ dan?
Volgens mij moet je wel degelijk aangeven of ergens 0 of (1 of meer) spaties staan.

Dat klopt, enkel 0 spaties werden geencode door een 1-bit, zie Verwijderd in "\[C++/Hex] Offsets lezen en schrijven van...". Die encoding voldoet niet, maar dat is aan te passen door bijvoorbeeld de 0/1-bits eerst neer te zetten (te padden met extra 1's), dan een byte per 0 bit voor het aantal spaties, en dan de originele reeks zonder de spaties.
Dan krijg je hier 01110101 01111111 01 FF 01 00 'h' 'a' 'l' 'l' 'o'
Met de voorwaarde van maximaal 256 spaties zal na iedere 0-bit zeker een 1-bit volgen, dus kun je die weglaten en volstaan met
01100011 01 FF 01 00 'h' 'a' 'l' 'l' 'o'

[Soultaker]

@hierboven: ik denk nog steeds dat RoadRunner's voorstel in de praktijk slecht werkt omdat je alleen runs van méér dan een spatie kunt comprimeren. Alle andere data wordt juist 12,5% groter. Normale tekst bevat wel veel spaties, maar zelden meerdere spaties achter elkaar (lees dit topic maar eens door ).

En aangezien de opdracht een specifieke codering van de niet-spaties vereist, blijft dan pedorus voorstel over. Daarmee codeer je spaties met 1 bit en alle andere karakters met 9 bits.

Arcane Apex schreef op woensdag 18 augustus 2010 @ 10:02:
(Hiermee heb ik nu de hint prijsgegeven/verklapt, maar de opdracht/regels in deze e-mail
worden verstuurd naar alle studenten, zodat iedereen over dezelfde informatie beschikt.)

Het lijkt me meer arbitraire bijkomende restrictie. Niet een "hint".

Wat ben ik trouwens blij dat ik niet zulke docenten/vakken heb zeg. Komt dit van een hogeschool? Welke precies?

edit:

3c. Het inputbestand dat jullie krijgen zal nooit situaties bevatten waarbij er meer dan 256 spaties voor een karakter staan.

Leuke valkuil: 257 spaties aan het eind van het bestand mag dus wel.

[ Voor 48% gewijzigd door Soultaker op 18-08-2010 20:38 ]

[TD-er]

Je kunt natuurlijk ook het aantal opeenvolgende spaties beschouwen als te comprimeren tekst, die je dan gaat analyseren.
Bijvoorbeeld je hebt de volgende verdeling:
1x 10 spaties
3x 5 spaties
4x 14 spaties
2x 1 spaties
Dan codeer je de meest voorkomende reeks met het kortste teken.
Kijk bijvoorbeeld eens naar de morse-code. De 'e' heeft de kortste codering en de minder gebruikte tekens zoals cijfers en een aantal letters heb je de langste code voor nodig.

Je kunt dan besluiten de gegenereerde codering mee op te slaan (kost ruimte), maar je kunt het jezelf ook heel makkelijk maken door die morse-code te gebruiken.

Bijvoorbeeld als resultaat je letters zonder spaties, gevolgd door 1 spatie en dan elke reeks van spaties opslaan als cijfers in morse opgeslagen.
Dus 123045067089 = 123 spaties, 45 spaties, 67 spaties. 89 spaties.
Dat is in dit voorbeeld 12 "tekens" in Morse die elk 5 bits innemen.
Oftewel 60 bits voor dit stukje.
Die codeer je dan met 6 tekens per 32-bit word, zodat je altijd mooi netjes uitkomt en dus ook in constante tijd kunt berekenen hoeveel spaties er tussen de n^e en (n+1)^e letter stond. Je kunt dus een hele simpele functie maken die 6x int accepteert en een string van 4 bytes oplevert.

Of nog leuker, je maakt een type met union waarin je de boel gewoon opslaat en uitleest. Dan heb je je compressie en decompressie in no-time klaar.

code:

union morseToString {
  struct {
     uint_8 digit1:5;
     uint_8 digit2:5;
     uint_8 digit3:5;
     uint_8 digit4:5;
     uint_8 digit5:5;
     uint_8 digit6:5;
  } digits;
  char c[4];
} mix;

Dit even uit het hoofd, maar het gaat om het idee.

[ajakkes]

Er wordt aangegeven dat de tekst alle extended ascii tekens kan bevatten. Hier is morse niet helemaal op gebouwd. Je kan er inderdaad voor kiezen om je algoritme te optimaliseren voor de tekens die ook in morse staan. @TD-er je oplossing voldoet overigens ook niet aan andere voorwaarden van de opdracht.

Maar aangezien het voorbeeld meerdere spaties tussen de letters heeft ben ik ervan uitgegaan dat het de bedoeling is om het algoritme te optimaliseren voor meerdere spaties tussen letters. Dit komt namelijk in normale tekst zelden voor.
Als je het algoritme wil optimaliseren voor normale tekst draai je de codering om. Sla je dus niet het aantal spaties tussen de tekens op, maar het aantal tekens tussen de spaties. Door ook dit weer aan het einde van het document te doen blijft de tekst min of meer leesbaar. De spatie komt nog vaker voor dan de "e". Dus voor een standaard stuk tekst kan het algoritme volgens mij wel 75% compressie halen. (grove schatting.) Zonder gegevens verlies en met volledig ascii ondersteuning.

[.oisyn]

Je kan natuurlijk ook een wat slimmere encoding bedenken mbv een huffman tree (het was natuurlijk al een huffman tree, maar ik bedoel een met meer dan 2 takken ), waarbij je zowel een aantal spaties of een aantal karakters met een variabel aantal bits kunt weergeven. En als je helemaal extra punten wilt verdienen dan maak je die tree dynamisch op basis van het input bestand

[Killemov]

.oisyn schreef op donderdag 19 augustus 2010 @ 10:20:
En als je helemaal extra punten wilt verdienen dan maak je die tree dynamisch op basis van het input bestand

Waarbij je de tree zelf ook weer moet opslaan voor of na de hallo-reeks.

Verder doelt de leraar heel specifiek op run-length encoding (Kudos voor RoadRunner.) en is de voorwaarde dat het gecomprimeerde resultaat ook leesbaar moet zijn op zijn minst ongebruikelijk te noemen. Feitelijk loop je dan twee streams af in plaats van een. Een tekst-stream en een spatie/skip stream.

[.oisyn]

Gisteravond een huffman encoder in elkaar gefrutseld die de lengtes van opeenvolgende spaties en tekens encodeerd in zo weinig mogelijk bits. Morgen-avond eens de decoder afronden. Zou ik 'm ook in mogen leveren denk je?

Killemov schreef op donderdag 19 augustus 2010 @ 17:00:
[...]

Waarbij je de tree zelf ook weer moet opslaan voor of na de hallo-reeks.

Sure. Voor héle kleine bestanden is het niet voordelig, maar zo heel veel ruimte kost het opslaan van zo'n tree ook weer niet (voor 8 symbols had ik maar 3 bytes nodig)

[ Voor 44% gewijzigd door .oisyn op 20-08-2010 12:09 ]

[Verwijderd]

.oisyn schreef op vrijdag 20 augustus 2010 @ 12:04:
Gisteravond een huffman encoder in elkaar gefrutseld die de lengtes van opeenvolgende spaties en tekens encodeerd in zo weinig mogelijk bits. Morgen-avond eens de decoder afronden. Zou ik 'm ook in mogen leveren denk je?


[...]

Sure. Voor héle kleine bestanden is het niet voordelig, maar zo heel veel ruimte kost het opslaan van zo'n tree ook weer niet (voor 8 symbols had ik maar 3 bytes nodig)

en heb je dan ook de waarde van de symbolen opgeslagen? want alleen symboolnummers is dus niet genoeg he!

[.oisyn]

Like, duh . Overigens is symbool + bitlengte wél genoeg, en als je ervoor kiest om alle mogelijke symbolen te specificeren dan hoef je alleen mog maar bitlengtes op te slaan. Waarden zijn sowieso niet nodig als je ervoor zorgt dat je tree in canonical form staat.

[ Voor 79% gewijzigd door .oisyn op 20-08-2010 16:47 ]

[Verwijderd]

.oisyn schreef op vrijdag 20 augustus 2010 @ 16:44:
Like, duh . Overigens is symbool + bitlengte wél genoeg, en als je ervoor kiest om alle mogelijke symbolen te specificeren dan hoef je alleen mog maar bitlengtes op te slaan. Waarden zijn sowieso niet nodig als je ervoor zorgt dat je tree in canonical form staat.

Je zegt tegelijk ja en nee. Ja: je hebt de bitlengtes (en daarmee berekenbaar hun code) opgeslagen, nee: je hebt hun symbolen niet opgeslagen. Dat een spatie straks als 1 bit gecodeerd wordt kan de decoder niet in staat stellen het resultaat terug te winnen zonder te weten dat het een spatie is.

[ Voor 3% gewijzigd door Verwijderd op 20-08-2010 16:57 ]

[.oisyn]

Volgens mij ben jij degene die zichzelf tegenspreekt. Eerst had je het over waarden, nu ineens over symbolen .

Een symbol in mijn geval is gewoon een lengte. Ik encodeer zowel de lengtes van opeenvolgende spaties als opeenvolgende tekens. In feite hoef je alleen maar te weten of er begonnen wordt met een spatie of een letter, daarna heb je in feite genoeg aan een reeks lengtes. Bijvoorbeeld:

begin_met_spatie 2 5 3 2 1 3 5 4 3 3 1 1 hallohierstaatiets

Resultaat:

"  hallo   hi ers     taat   iet s"

Die lengtes encodeer ik mbv een huffman tree.

.edit: heb het even snel uitgeschreven, in canonical form wordt de huffman codebook:
1: 00
2: 110
3: 01
4: 111
5: 10

De totale reeks wordt dus geëncodeerd als:
110 10 01 110 00 01 10 111 01 01 00 00

Voor de opslag van deze tree hoef je alleen maar te zeggen dat symbolen 1, 3 en 5 lengte 2 hebben, en 2 en 4 hebben lengte 3. Uit die informatie alleen kun je bovenstaande codebook weer destilleren.

nee: je hebt hun symbolen niet opgeslagen

Dat heb ik niet gezegd. Wat ik zei was dat als je de lengtes van alle mogelijke symbolen achter elkaar zet (met de ongebruikte symbolen dus lengte 0), dan hoef je de symbolen niet expliciet op te slaan. Zo kun je bijvoorbeeld stellen dat de maximale lengte bijv. 64 is (een reeks van bijv. 100 spaties zou je dan kunnen coderen met 64 spaties - 0 tekens - 36 spaties). En dan output je een table van 65 entries met bitlengtes voor elk symbool van 0 t/m 64.

[ Voor 111% gewijzigd door .oisyn op 20-08-2010 17:30 ]

[ajakkes]

Dus als ik het goed begrijp zou je het voorbeeld dus zo coderen?

00110000 00001001 11001110 hallo

30 09 CE 68 61 6C 6C 6F

8 bytes. Blijft het niet handiger om de spaties achter de tekst op te slaan? Als je dan met halve bytes overblijft kan je makkelijker opvullen of zie ik dat verkeerd?

Ik leer in ieder geval wel veel van dit topic.

[.oisyn]

ajakkes schreef op vrijdag 20 augustus 2010 @ 21:44:
Dus als ik het goed begrijp zou je het voorbeeld dus zo coderen?

00110000 00001001 11001110 hallo

Min of meer. Het codebook is afhankelijk van de frequenties. Het hallo voorbeeld geeft daardoor een ander codebook dan het voorbeeld hierboven. Daarnaast moet het codebook zelf ook nog worden opgeslagen (tenzij je natuurlijk voor een vast codebook gaat), en of je met een spatie begint, en (waarschijnlijk) ook of je met een spatie eindigt.

En halve bytes moet je altijd opvullen, of ze nou aan het begin of aan het eind staan

[pedorus]

.oisyn schreef op vrijdag 20 augustus 2010 @ 17:06:
Die lengtes encodeer ik mbv een huffman tree.

Zou het dan niet logisch zijn om 2 trees te hebben (1 voor spaties, 1 voor karakterlengtes)?

Verder ligt het er sterk aan hoe de input wordt gegenereerd of dit zinvol is. Het is helaas een beetje een kunstmatige opdracht waardoor je niet echt kan weten hoe deze eruit ziet. Ik kan prima een groot inputbestand verzinnen waarvoor de rle-variant het beste gaat werken bijvoorbeeld. (Groot inputbestand zodanig dat de uitkomst van een 0 of 1-bit in het uitvoerbestand steeds 50% is.)

[.oisyn]

pedorus schreef op zaterdag 21 augustus 2010 @ 13:40:
[...]

Zou het dan niet logisch zijn om 2 trees te hebben (1 voor spaties, 1 voor karakterlengtes)?

Heb ik stiekem ook . Alleen ben ik er nog niet over uit of het daadwerkelijk efficienter is, dat moet ik nog even testen. M'n intuitie zegt van wel, vandaar dat ik wel 2 trees gebruik.

[pedorus]

.oisyn schreef op zaterdag 21 augustus 2010 @ 13:57:
[...]

Heb ik stiekem ook . Alleen ben ik er nog niet over uit of het daadwerkelijk efficienter is, dat moet ik nog even testen. M'n intuitie zegt van wel, vandaar dat ik wel 2 trees gebruik.

Mm, ik kan zowel een groot inputbestand aan je geven waar dit efficiënter is, als een waar dat niet zo is. Gezien het kunstmatige karakter van de opdracht valt het lastig te zeggen wat het zal gaan zijn, dus ik denk dat "testen" lastig wordt..

[.oisyn]

Als ik er zo eens over nadenk is het hebben van twee trees nooit nadelig, met uitzondering van het feit dat je dan twee trees op moet slaan, wat juist weer marginaal is bij grote bestanden.

Daarnaast zou je ervoor kunnen kiezen om simpelweg meerdere algoritmen te implementeren (ook andere voorgestelde, zoals die van jou), en dan per bestand te bekijken welke het beste comprimeert

[ Voor 6% gewijzigd door .oisyn op 21-08-2010 19:20 ]

[codeneos]

Ik denk dat in dit geval een Bitmap compressie schema het beste werkt. Als ik het goed gelezen heb mag alleen de spatie weg gecomprimeerd worden en moet de volgorde van de letters niet veranderen. Nu maak je gewoon een bitmap (map/array van bits, geen plaatje met mspaint) die een als het ware een map van de byte array is die je verkleind. Als bit 5 geset is betekend dit dat er een spatie op die plaats is data zit als de bit niet geset is lees je een byte van de data string af.

De file ziet er ongeveer zo uit: eerst een byte array met de echte data waar geen spaties in zitten en dan een bitmap met waar de spaties zouden moeten zitten (geprefixt met een gecomprimeerde Int zodat je weet hoelang de originele data was).

Ik heb zelf even een compressie class gemaakt die dit schema toepast en de string van de TS er in gegooid, het resultaat:

code:

0x78 0x68 0x61 0x6c 0x6c 0x6f 0xd6 0x3d

Werkt met de hele ASCII-Extended characterset .Ik daag iedereen uit dit te verbeteren .

Bij interesse wil ik de source wel posten, is maar 120 regels .

[ Voor 29% gewijzigd door codeneos op 22-08-2010 23:57 ]

[TD-er]

Ik weet niet of je bij bit 0 of bit 1 begint te tellen, maar even zo uit het hoofd is bit 5, wanneer je telt van 0-7 het verschil tussen hoofd- en kleine letters. Dan kun je nog steeds niet ABCD comprimeren. (die hebben volgens mij bit5 op 0 staan.
Volgens mij is het enige character wat je kunt gebruiken om de positie te taggen, is... een spatie. (en de leesbare tekens leesbaar houden) (Volgens mij is extended-ASCII van 0-255, anders zou je bit 7 kunnen gebruiken voor je wel of niet spatie)
Als je wel een bitmap aan wilt houden, kun je bijvoorbeeld de '0' spatie gevallen wel coderen met 1 bit door bijvoorbeeld 8 bits te encoderen met een 1 voor wel een of meer spaties en een 0 voor geen spatie en zodoende een reeks te maken met hoeveel spaties waar geplaatst kunnen worden.
Echter dit is waarschijnlijk nog meer storage dan een simpele huffman codering omdat je bij vaak voorkomen van 0 spaties dit ook met weinig bits kunt coderen.

Kortom ik vermoed dat je codering niet helemaal conform specs is.

[pedorus]

codeneos schreef op zondag 22 augustus 2010 @ 21:33:
Ik daag iedereen uit dit te verbeteren .

Zie hier, het kan met een byte minder omdat je de lengte kan achterhalen...

.oisyn schreef op zaterdag 21 augustus 2010 @ 19:19:
Daarnaast zou je ervoor kunnen kiezen om simpelweg meerdere algoritmen te implementeren (ook andere voorgestelde, zoals die van jou), en dan per bestand te bekijken welke het beste comprimeert

En die keuze kan natuurlijk zelfs in de bestandsextentie zodat het geen bits kost..

[Killemov]

codeneos schreef op zondag 22 augustus 2010 @ 21:33:
Ik denk dat in dit geval een Bitmap compressie schema het beste werkt. Als ik het goed gelezen heb mag alleen de spatie weg gecomprimeerd worden en moet de volgorde van de letters niet veranderen. Nu maak je gewoon een bitmap (map/array van bits, geen plaatje met mspaint) die een als het ware een map van de byte array is die je verkleind. Als bit 5 geset is betekend dit dat er een spatie op die plaats is data zit als de bit niet geset is lees je een byte van de data string af.

De file ziet er ongeveer zo uit: eerst een byte array met de echte data waar geen spaties in zitten en dan een bitmap met waar de spaties zouden moeten zitten (geprefixt met een gecomprimeerde Int zodat je weet hoelang de originele data was).

Ik heb zelf even een compressie class gemaakt die dit schema toepast en de string van de TS er in gegooid, het resultaat:

code:

0x78 0x68 0x61 0x6c 0x6c 0x6f 0xd6 0x3d

Werkt met de hele ASCII-Extended characterset . Ik daag iedereen uit dit te verbeteren .

Bij interesse wil ik de source wel posten, is maar 120 regels .

Wat is hier principieel anders aan dan dit? http://gathering.tweakers...message/34529609#34529609 Dus hoezo uitdaging?

[codeneos]

pedorus schreef op zondag 22 augustus 2010 @ 23:15:
[...]

Zie hier, het kan met een byte minder omdat je de lengte kan achterhalen...
[...]

En die keuze kan natuurlijk zelfs in de bestandsextentie zodat het geen bits kost..

Ja inderdaad dan zou het 1 byte schelen omdat je de lengte van de originele string niet encode en het aantal 0 bits telt, daar had ik zelf nog niet aangedacht . Het decomprimeren gat wel sneller als je de originele lengte van de data nog weet .

Killemov schreef op zondag 22 augustus 2010 @ 23:17:
[...]
Wat is hier principieel anders aan dan dit? http://gathering.tweakers...message/34529609#34529609 Dus hoezo uitdaging?

Sorry het werd me uit jou post niet echt duidelijk dat dat was wat je bedoelde. Ik had het idee dat je bedoelde letterlijk 1 bit voor elke byte te zetten.

TD-er schreef op zondag 22 augustus 2010 @ 22:47:
Kortom ik vermoed dat je codering niet helemaal conform specs is.

Hmm, het was toch de bedoeling dat de originele string zonder spatie zichbaar moest zijn in bijvoorbeeld notepad? Verder is de eerste bit bij mij een gecomprimeerde int waarvan de eerste 3 bits een mask. De laatste 2 bytes zijn de daadwerkelijk bitmap.

Ik heb ook geprobeerd een simple bytepair algoritme toe te passen maar dan was de string niet meer te lezen .

[ Voor 18% gewijzigd door codeneos op 22-08-2010 23:58 ]

[Killemov]

codeneos schreef op zondag 22 augustus 2010 @ 23:49:
[...]
Sorry het werd me uit jou post niet echt duidelijk dat dat was wat je bedoelde. Ik had het idee dat je bedoelde letterlijk 1 bit voor elke byte te zetten.

Ja, dat klopt ook ... behalve als het een spatie betreft. Alleen wordt niet aan de eis voldaan dat de originele tekst leesbaar moet blijven in de gecomprimeerde vorm. Wat weer hoogst ongebruikelijk is bij compressie zoals ik al eerder heb geroepen. (Boeien dat je weinig interessants ziet als je met een hex-editor naar een zip-bestand kijkt.)
Bij woorden van 7 of meer karakters heb je dus helemaal geen winst meer.

[ Voor 5% gewijzigd door Killemov op 23-08-2010 00:16 ]

[.oisyn]

codeneos schreef op zondag 22 augustus 2010 @ 21:33:
Ik daag iedereen uit dit te verbeteren .

Ik daag jou uit de topic te lezen voor je reageert

Maar we kunnen natuurlijk niet echt een "competitie" houden zonder duidelijke voorbeeldbestanden. Dus misschien moeten we die zelf even gaan maken. Ik stel voor bestanden van verschillende grootten, met varianten waarbij zowel veel tekst en weinig spaties in staan als veel spaties en weinig tekst. En natuurlijk een lorem ipsum

[ Voor 43% gewijzigd door .oisyn op 23-08-2010 12:29 ]

[ajakkes]

Als je er dan toch een competitie van wil maken:

1. Het voorbeeld zo klein mogelijk.

2. Een nieuw voorbeeld dat een groot aantal ascii II tekens bevat en 256 spaties achter elkaar ergens in het bestand.

3. Een stukje standaard tekst. Bijvoorbeeld een willekeurig artikel op tweakers.

4. Een ascii art afbeelding.

5. De tekst "hallo", dus zonder spaties. Om te kijken of het ook in minst ideale situaties iets bereikt.

Je kan zorgen dat de encoder niet wordt geoptimaliseerd door bij voorbeeld 2, 3, 4 eerst een voorbeeld te zoeken. En deze op het moment dat de encoders af zijn te veranderen in een ander voorbeeld dat voldoet aan deze eisen.

Ik wens jullie veel succes

Overigens is het natuurlijk wel de bedoeling dat alle tekens behalve de spatie in het eindresultaat zichtbaar zijn. Het moet natuurlijk wel blijven voldoen aan de eisen die in de bron opdracht bedacht zijn.

[pedorus]

Voorbeeldbestand (31.2 mb gezipt tot 0.8 mb): http://www.mediafire.com/?8kysl26s207yiy9
Aantal niet-spaties: 236039

De entropy is minder dan 200 kb, de niet-spaties hebben geen entropy, en de bonusvraag is: welk dier?

[Soultaker]

Voor meer testdata kun je ook een random e-book pakken, b.v.:
http://www.gutenberg.org/files/16842/16842-8.txt

[.oisyn]

pedorus schreef op maandag 23 augustus 2010 @ 14:44:
Voorbeeldbestand (31.2 mb gezipt tot 0.8 mb): http://www.mediafire.com/?8kysl26s207yiy9
Aantal niet-spaties: 236039

De entropy is minder dan 200 kb, de niet-spaties hebben geen entropy, en de bonusvraag is: welk dier?

Mijn algo comprimeert deze naar 468kB (met niet-spaties eraf dus 232kB)

.edit: en voor de bonusvraag, volgens mij encodeert het aantal opeenvolgende spaties de bytes van een BMP file, maar dat klopt niet helemaal...

[ Voor 19% gewijzigd door .oisyn op 23-08-2010 16:42 ]

[pedorus]

.oisyn schreef op maandag 23 augustus 2010 @ 16:25:
[...]


Mijn algo comprimeert deze naar 468kB

Dat is beter dan de RLE-variant (ceiling((236038/8)+236039+(236038-4832))/1024= 485.1074kB), enkel ik weet zeker dat dit nog beter kan.

.edit: en voor de bonusvraag, volgens mij encodeert het aantal opeenvolgende spaties de bytes van een BMP file, maar dat klopt niet helemaal...

Ik heb geen probleem om het te decoderen?

C#:

            var bytes = File.ReadAllBytes(@"in.bmp");
            var result = new List<byte>(bytes.Length * 200);
            byte pos = 0;
            for (int i = 0; i < bytes.Length; i++)
            {
                unchecked { result.Add(pos++); }
                if (pos == (byte)0x20) pos++;
                result.AddRange(Enumerable.Repeat((byte) 0x20, bytes[i]));
            }
            unchecked { result.Add(pos++); }
            File.WriteAllBytes(@"input.txt",result.ToArray());

C#:

            var bytes = File.ReadAllBytes(@"input.txt");
            var result = new List<byte>(bytes.Length);
            byte cnt = 0;
            for (int i = 1; i < bytes.Length; i++)
            {
                if (bytes[i] == (byte)0x20)
                    cnt++;
                else
                {
                    result.Add(cnt);
                    cnt = 0;
                }
            }
            File.WriteAllBytes(@"in.bmp", result.ToArray());

[.oisyn]

Oh stom, ik pakte de lengte van opeenvolgende spaties, maar natuurlijk niet de "0 spaties" tussen twee tekens. Nou ja, m'n vermoeden was iig wel correct

spoiler:

haas

[ Voor 6% gewijzigd door .oisyn op 23-08-2010 17:56 ]

[.oisyn]

Hier is de code trouwens. Zonder comments, kan de TS het ook niet inleveren zonder te snappen wat het doet . 't Gebruikt trouwens wel wat C++0x features zoals lambda's en static type inference ('auto'), en de std::tr1 library (VS 2010 will do fine).

sourcecode
binary (win32)

.edit: oeps die BMP generator voor de bonusvraag van pedorus zat er nog in
.edit2: wat kleine bugjes eruit gehaald voor de gevallen waarbij er 256 of meer spaties of tekens na elkaar komen.

.edit3: die ebook van soultaker gaat van 334kB naar 304kB.

[ Voor 74% gewijzigd door .oisyn op 24-08-2010 00:37 ]

[Soultaker]

Nice. Ik denk dat ik je op tekst nog wel kan verbeteren maar die testcase van Pedorus is zo kunstmatig als wat. Dat is een stuk lastiger.

Overigens levert standaard compressie van de bitmap met bzip2 al aardig resultaat op in Pedorus' case:

	pedorus	potgieter
.oisyn	~237.568	~29.505
gzip	295.008	26.886
lzma	243.396	24.336
bzip2	177.740	26.228

Wel bijzonder dat bzip2 zo goed performt in pedorus' case.

[pedorus]

.oisyn schreef op maandag 23 augustus 2010 @ 21:47:
Hier is de code trouwens. Zonder comments, kan de TS het ook niet inleveren zonder te snappen wat het doet .

Ik zie stiekem toch nog wat comments, je hebt ze niet allemaal verwijderd

Is het trouwens [option] of gewoon option? Ik denk het laatste.

.edit2: wat kleine bugjes eruit gehaald voor de gevallen waarbij er 256 of meer spaties of tekens na elkaar komen.

Of zou dat een foutmelding/warning moeten opleveren? Verder nice.

Soultaker schreef op dinsdag 24 augustus 2010 @ 16:53:
Nice. Ik denk dat ik je op tekst nog wel kan verbeteren maar die testcase van Pedorus is zo kunstmatig als wat. Dat is een stuk lastiger.

Kunstmatige opdracht leidt tot kunstmatig voorbeeld.

Overigens levert standaard compressie van de bitmap met bzip2 al aardig resultaat op in Pedorus' case:

Mm, bzip2 werkt beter dan png hier.

[.oisyn]

pedorus schreef op dinsdag 24 augustus 2010 @ 22:53:
Ik zie stiekem toch nog wat comments, je hebt ze niet allemaal verwijderd

Ik heb helemaal niets verwijderd

Is het trouwens [option] of gewoon option? Ik denk het laatste.

Idd. Of eigenlijk <option>

Of zou dat een foutmelding/warning moeten opleveren? Verder nice.

De opdracht heeft het over maximaal 256 spaties na elkaar, maar niet over een maximum aantal tekens na elkaar. Aangezien ik voor tekens dus sowieso moet checken of ze niet over een maximum gaan (omdat ik het resulterende codebook anders niet goed kan opslaan), heb ik dat voor spaties ook maar meteen toegestaan (het was meer moeite om dat niet te doen dan wel).

Overigens is de fixed codebook om de dynamische huffman codebooks op te slaan ook niet erg efficient, de verschillen in bitlengtes schommelen nogal (meestal tussen de 1 en de -1), en hoewel een 0 of 1 als 2 bits kan worden opgeslagen kost een -1 ineens 11 bits. Hier valt dus nog wat op te winnen, maar ik had geen zin dat te implementeren en de winst is minimaal (de tree size was bij jouw voorbeeld ook maar 136 bytes, marginaal vergeleken met de daadwerkelijke data)

[Soultaker]

Ik heb m'n ideetje ook even uitgewerkt. Een tekortkoming van .oisyn's aanpak is dat hij alleen naar de bitmap data kijkt en de rest van de tekst negeert. Het klopt natuurlijk dat je die tekst niet mag comprimeren, maar dat betekent niet dat je er niets aan hebt. Ik begin ook met een bitmap zoals eerder beschreven, maar in plaats van die direct te comprimeren, gebruik ik de voorgaande karakter(s) als predictor (specifiek kijk ik naar het laatste karakter óf het aantal voorgaande spaties als het laatste karakter een spatie was).

Verder sla ik geen frequentietabel op in de output stream, maar gebruik ik een adaptive arithmetic coder. Een Huffman coder volstaat hier niet omdat ik individuele bits codeer (en die kun je niet verder comprimeren met een Huffman coder omdat die elk invoersymbool in een geheeltallig aantal bits codeert, al zou je in principe wel meerdere bits in een blok kunnen stoppen). Een arithmetic coder is ideaal als je probabilities per symbool verschillen.

Mijn verwachting was dat het vooral goed zou werken voor natuurlijke tekst (waarbij de voorgaande karakters veel voorspellende waarde hebben) maar ook in pedorus' synthetische case werkt het beter dan alle andere methoden op bzip2 na. Voor de volledigheid het hele overzicht:

	pedorus	potgieter
.oisyn	~237.568	~29.505
Soultaker	217.184	20.804
gzip	295.008	26.886
lzma	243.396	24.336
bzip2	177.740	26.228

Wie geïnteresseerd is in de achtergrond: mijn aanpak is geïnspireerd door Mark Nelson's Arithmetic Coding + Statistical Modeling = Data Compression. De broncode (in Python 3): encoder, decoder.

Ik denk dat er nog aanzienlijke winst te behalen is met betere statistical modeling van de invoer, bijvoorbeeld door middel van een (dynamisch) Markovmodel. Maar aangezien niemand wat beters bedacht heeft laat ik het hier voorlopig bij.

[alex3305]

Ik ben overigens nog wel benieuwd hoe het met de TS is afgelopen. Al een aantal dagen niets meer van gehoord.

[RobIII]

Klein kickje. Ik doe dit anders nooit, maar nu ben ik toch wel benieuwd naar hoe dit afgelopen is.