Alternerende data comprimeren

[Juup]

Voor een hobbyproject probeer ik een stuk data kleiner te maken voordat het (soms ge-gzipt) naar de client wordt gestuurd.
De data ziet er ongeveer zo uit:

code:

Sl. nr. VINfrom VINto
AR83    ET42914 ET42915
AW43    ET42916 ET42920
AR83    ET42921 ET42921
AW43    ET42922 ET42925
AR83    ET42926 ET42927
AW43    ET42928 ET42928
AR83    ET42929 ET42930
AW43    ET42931 ET42931
AR83    ET42932 ET42937
AW43    ET42938 ET42938
AR83    ET42939 ET42948
AW43    ET42949 ET42952
AR83    ET42953 ET42956
AW43    ET42957 ET42960
AR83    ET42961 ET42963
...
BL93    JR10000 JR24999
AX71    JR25000 JR34999
BL41    JR35000 JR36988
BL42    JR45000 JR48399
... nog 60.000 rows

Gegeven een VIN nummer (bv VIN "ET42950") moet het sleutelnummer opgezocht worden (Sleutel "AW43").

De tabel zou zo omgeschreven kunnen worden dat op 1 row alle VIN ranges van 1 sleutelnummer staan maar dat levert maar weinig winst op.

Is er iets slims te bedenken om die alternerende rows compact op te slaan?

[Caballeros]

Alles wat dubbel is vervangen of weglaten.

bijvoorbeeld

code:

AR83    ET42914 42915

is alvast 120000 bytes minder in je file

kan je nog verder gaan door de rest wat overeenkomt weg te laten

code:

AR83    ET42914 5

[RobIII]

code:

AR83:ET42914,2,ET42921,1,ET42926,2,ET42929,2,ET42932,6,ET42939,10,ET42953,4,ET42961,3
AW43:ET42916,5,ET42922,4,ET42928,1,ET42931,1,ET42938,1,ET42949,4,ET42957,4

etc... Dus:
Code:From,Lengte,From,Lengte,From,Lengte,From,Lengte,...

En dat zou je nog kunnen comprimeren naar offsets/lengtes:

code:

AR83:ET42914,0,2,7,1,12,2,15,2,18,6,25,10,39,4,47,3
AW43:ET42916,0,5,6,4,22,1,15,1,22,1,33,4,41,4

Dus:
Code:Start,Offset,Lengte,Offset,Lengte,Offset,Lengte,Offset,Lengte,...
Waarbij je de eerste offset nog weg zou kunnen laten en stellen: 1e Offset = start.

[ Voor 83% gewijzigd door RobIII op 22-06-2016 15:46 ]

[Juup]

RobIII schreef op woensdag 22 juni 2016 @ 15:38:

code:

AR83:ET42914,2,ET42921,1,ET42926,2,ET42929,2,ET42932,6,ET42939,10,ET42953,4,ET42961,3
AW43:ET42916,5,ET42922,4,ET42928,1,ET42931,1,ET42938,1,ET42949,4,ET42957,4

etc...

Ja. En dat kan nog verder worden gereduceerd tot

code:

AR83:ET42914,2,3,1,4,2,1,2,5,6,5,10,6,4,1,3

etc
dat helpt alweer.

[RobIII]

Juup schreef op woensdag 22 juni 2016 @ 15:43:
[...]

Ja. En dat kan nog verder worden gereduceerd tot

code:

AR83:ET42914,2,3,1,4,2,1,2,5,6,5,10,6,4,1,3

etc
dat helpt alweer.

Of zoiets ja. Alles kan. Hangt er natuurlijk ook een beetje af hoe 'vrij' je bent in het opstellen van 't bestandsformaat. Maar: hou er rekening mee dat compressie als GZ etc. vaak het beste/beter werkt bij veel repeterende data; hoe meer je zélf al gaat reduceren ("compressen"), hoe minder GZ ermee kan doen. Ik zou dan ook vooral even voor- en na meten wat de verschillen zijn (en je eerst afvragen of 't überhaupt een probleem is dat je aan 't oplossen bent; bedenk wel dat je extra complexiteit introduceert en dus extra werk, extra code, extra kans op bugs etc.). Als tijd / complexiteit geen / amper een issue is dan is het meten == weten en gewoon kijken tot waar 't zich nog loont om door te gaan voor net die extra paar bits besparing (if at all).

[ Voor 47% gewijzigd door RobIII op 22-06-2016 15:50 ]

[Viper®]

Als je de data daarna alsnog gaat comprimeren (zip) kan het zijn dat het eindresultaat minimaal is.

De tekst data zoals je die nu namelijk hebt is goed te comprimeren.
Ga je het zelf al enigszins verbouwen dan zal het comprimeren minder efficient zijn. Uiteindelijk is het eindbestand misschien net zo groot.

[Standeman]

Viper® schreef op woensdag 22 juni 2016 @ 15:50:
Als je de data daarna alsnog gaat comprimeren (zip) kan het zijn dat het eindresultaat minimaal is.

De tekst data zoals je die nu namelijk hebt is goed te comprimeren.
Ga je het zelf al enigszins verbouwen dan zal het comprimeren minder efficient zijn. Uiteindelijk is het eindbestand misschien net zo groot.

Of groter door de metadata

[Ventieldopje]

Gzip is wel een van de beste algoritmes (tijd vs. compressie) om text mee te comprimeren, vandaar dat het ook vaak gebruikt wordt. We kunnen speculeren maar het zal in ieder geval helpen om een compacter bron formaat te gebruiken. Daarna kun je eventueel nog testen met gzip compressie om te kijken wat het uit haalt.

[jeroen3]

Moet het een textfile blijven?

code:

AR83:ET42914,2,3,1,4,2,1,2,5,6,5,10,6,4,1,3
AR83;ETA7A22314212565A6413\n

[RobIII]

Ventieldopje schreef op woensdag 22 juni 2016 @ 16:00:
Gzip is wel een van de beste algoritmes (tijd vs. compressie) om text mee te comprimeren

Nou; het is vooral een 'overal beschikbaar' algoritme. Voor elke taal en elk platform bestaat er wel een library. Er zijn echter genoeg betere algoritmes (uit m'n hoofd o.a. zopfli/brotli, 7zip, bzip, lzma, ...)
Edit: voila. (Overigens is gzip eigenlijk deflate)

Ventieldopje schreef op woensdag 22 juni 2016 @ 16:00:
het zal in ieder geval helpen om een compacter bron formaat te gebruiken

Dat hoeft dus niet zo te zijn. Alle bekende algoritmes moeten 't doen zonder 'domein specifieke' kennis en zullen dus een generieke compressie loslaten op een (voor "hun") ontransparante blob data. Omdat je echter precies weet wat-wat is kun je waarschijnlijk zélf al een behoorlijk efficiënt bestandsformaatje bedenken; daarna compressen met eender welk algoritme kan grotere bestanden opleveren. Beetje hetzelfde als dat een MP3 of JPG of whatever (wat al een behoorlijk gecomprimeerd formaat is) zippen/rarren/whatever weinig tot geen nut heeft. De vraag is: kosten/baten. Hoeveel tijd/geld heb je om erin te steken en kun je je tijd niet beter besteden aan belangrijker zaken en 't formaat inefficiënt(er) laten voor wat 't is en die handel gewoon gzippen. En naast dat alles heb je ook nog de afweging (de)compressiesnelheid, geheugengebruik etc.

[ Voor 9% gewijzigd door RobIII op 22-06-2016 16:12 ]

[Juup]

jeroen3 schreef op woensdag 22 juni 2016 @ 16:04:
Moet het een textfile blijven?

code:

AR83:ET42914,2,3,1,4,2,1,2,5,6,5,10,6,4,1,3
AR83;ETA7A22314212565A6413\n

Hoeft idd geen text te zijn.

[RobIII]

Juup schreef op woensdag 22 juni 2016 @ 16:13:
[...]

Hoeft idd geen text te zijn.

Dan kun je ook nog wel besparen door een binair bestandsformaat te verzinnen; zo kost elk getal als start/offset in ASCII zoals 0..9 je nu 1 byte en 10..99 2 bytes en 100..999 3 bytes; en dan heb je nog de separators. Daar kun je natuurlijk heel mooi een 16bit int van maken (kun je elk getal van 0..65535 in 2 bytes kwijt), hoef je geen separators meer te gebruiken etc. Afhankelijk van hoe de "bulk" van de data eruit ziet zou je ook voor enkele bytes of juist 32bit values kunnen gaan (maar afgaand op wat ik nu zie bevat je bestand dan minimaal 50% "lucht" a.k.a. nullen). Ik zou alleen de codes wel 'gewoon' een string laten; ondanks dat er 'getallen' in staan zijn 't natuurlijk niet echt getallen.

[ Voor 19% gewijzigd door RobIII op 22-06-2016 16:19 ]

[Ventieldopje]

RobIII schreef op woensdag 22 juni 2016 @ 16:06:
[...]

Nou; het is vooral een 'overal beschikbaar' algoritme. Voor elke taal en elk platform bestaat er wel een library. Er zijn echter genoeg betere algoritmes (uit m'n hoofd o.a. zopfli/brotli, 7zip, bzip, lzma, ...)
Edit: voila. (Overigens is gzip eigenlijk deflate)


[...]

Dat hoeft dus niet zo te zijn. Alle bekende algoritmes moeten 't doen zonder 'domein specifieke' kennis en zullen dus een generieke compressie loslaten op een (voor "hun") ontransparante blob data. Omdat je echter precies weet wat-wat is kun je waarschijnlijk zélf al een behoorlijk efficiënt bestandsformaatje bedenken; daarna compressen met eender welk algoritme kan grotere bestanden opleveren. Beetje hetzelfde als dat een MP3 of JPG of whatever (wat al een behoorlijk gecomprimeerd formaat is) zippen/rarren/whatever weinig tot geen nut heeft. De vraag is: kosten/baten. Hoeveel tijd/geld heb je om erin te steken en kun je je tijd niet beter besteden aan belangrijker zaken en 't formaat inefficiënt(er) laten voor wat 't is en die handel gewoon gzippen. En naast dat alles heb je ook nog de afweging (de)compressiesnelheid, geheugengebruik etc.

Het ligt er ook aan wat snel moet zijn maar bzip2 en lzma zijn behoorlijk traag met comprimeren. Met uitpakken is lzma wel wat sneller maar dan kun je imho beter lz4 pakken.

[klinz]

Doet de volgorde van de records er toe?

[ajakkes]

Als ik het zo zie hoeft je characterset maar 38 tekens te bevatten. 26 letters, 10 cijfers en twee seperaters. (row en column) Veel minder dan de 256 waar een minimale encoding uit bestaat.

Door het te beperken tot deze 38 in de header en 1 column seperater kan je de compressie verbeteren.

Misschien dat er ook nog winst te halen is door de characters aan het begin van de encoding te kiezen.

Maar eigenlijk haal je hiermee de compressie regels uit je compressie bestand. Wat wel veel kan opleveren met veel bestanden. Maar weinig met een enkel bestand. Een goede compressor doet dat zelf in het bestand.

Als het altijd 2 letters 4 cijfers patronen in kolom 1 zijn kan je ook nog denken aan het vertalen van 2 cijfers naar 1 letter of 1 letter naar 2 cijfers. Als de regels altijd even lang zijn hoeft een column separater niet.

Maar of je echt wint van een algoritme weet ik niet.

[farlane]

Als je het toch gaat zippen waarom zou je dan nog zelf iets gaan bedenken?

[Juup]

klinz schreef op woensdag 22 juni 2016 @ 20:01:
Doet de volgorde van de records er toe?

Nee die is irrelevant.
Gegeven een VIN moet er een sleutelnummer opgezocht worden.

[Juup]

code:

Sl. nr. VINfrom VINto
AR83    ET42914 ET42915
AW43    ET42916 ET42920
AR83    ET42921 ET42921
AW43    ET42922 ET42925
AR83    ET42926 ET42927
AW43    ET42928 ET42928
AR83    ET42929 ET42930
AW43    ET42931 ET42931
AR83    ET42932 ET42937
AW43    ET42938 ET42938
AR83    ET42939 ET42948
AW43    ET42949 ET42952
AR83    ET42953 ET42956
AW43    ET42957 ET42960
AR83    ET42961 ET42963

Ik zou ook een bitmap van deze alternerende reeks kunnen maken:
AR83 == 1
AW43 == 0
parseInt("11000001000011011011111101111111111000011110000111",2).toString(36) == "8cyse9j69z"

code:

AR83,AW43,ET42914,8cyse9j69z

[Vinnienerd]

Leuk dat jullie hier offsets willen gebruiken, gelukkig gebruikt LZW dit ook *hint*

[RobIII]

Vinnienerd schreef op donderdag 23 juni 2016 @ 20:44:
Leuk dat jullie hier offsets willen gebruiken, gelukkig gebruikt LZW dit ook *hint*

Een offset is een heel generieke term en die waar jij nu op doelt zal (zeker op basis van ASCII tekst) andere resultaten leveren dan de offsets die hier gesuggereerd worden

[jeroen3]

Veruit de eenvoudigste methode is gebruik maken van de 7-zip library. (of executable zelfs)
http://www.7-zip.org/sdk.html
Maar daar zit natuurlijk geen uitdaging in!

[ Voor 11% gewijzigd door jeroen3 op 23-06-2016 20:53 ]