Cijfers encoden in minder bytes?

[PanMan]

Hoi!
Ik vroeg me af of er een eenvoudig algoritme bestaat om cijfers in minder bits te encoderen dan 'gewoon' in bytes.
Een byte bestaat uit 8 bits, waarmee er 256 mogelijkheden zijn. Als je een getal encode, gebruik je er daar maar 10 van. Volgens mij zou je dus met 4 bytes 16 mogelijkheden hebben, meer dan genoeg, en dus 2x zoveel cijfers kunnen encoden per byte als je een aantal cijferreeksen wilt oversturen, of bijvoorbeeld 2 cijfers (getal tot 100) in 7 bytes.
Bestaan hier eenvoudige algoritmes voor? Het gaat om een javaprogramma'tje dat van een telefoon cijferreeksen moet doorsturen naar een webserver. Aangezien je hier per byte betaalt, is elke byte besparing er een, en zou je hiermee vrij veel kunnen besparen.
Ik begrijp dat ik zelf wat zou kunnen maken, maar ik vroeg me af of er al wat bestaat, of dat er bepaalde keywords zijn waar ik goed op kan zoeken. Ik heb sofar nog niets gevonden, en standaard zipfuncties lijken niet echt iets nuttigs te doen op ditsoort strings.

[RobIII]

PanMan schreef op dinsdag 07 november 2006 @ 01:25:
Hoi!
Een byte bestaat uit 8 bits, waarmee er 256 mogelijkheden zijn. Als je een getal encode, gebruik je er daar maar 10 van. Volgens mij zou je dus met 4 bytes bits 16 mogelijkheden hebben, meer dan genoeg, en dus 2x zoveel cijfers kunnen encoden per byte als je een aantal cijferreeksen wilt oversturen, of bijvoorbeeld 2 cijfers (getal tot 100) in 7 bytes.

Euh, hoe sla jij 25 op dan? Dat zou bij jou in 2 bytes moeten, namelijk een "2" en een "5". Bij mij past 25 (en 255 ook nog ) in 1 byte

Je haalt bits/bytes door elkaar denk ik. Een byte = 8 bits (bruggetje: "By eight" ~ "Byte")
En anders haal je de "ASCII-representatie" door elkaar met de binaire representatie/waarde.

Even een tabelletje voor je:

code:

1   00000001
2   00000010
3   00000011
4   00000100
5   00000101
...
10  00001010
11  00001011
12  00001100
13  00001101
14  00001110
...
25  00011001
...
253 11111101
254 11111110
255 11111111

En mocht ik je toch onverhoopt verkeerd begrijpen, kijk dan eens naar BCD

Wat je uiteindelijk dus gewoon wil is je cijfer in "binary mode" doorgeven aan de webserver en dus niet als ASCII.

Hoe stuur je die cijferreeksen overigens naar de server? In de URL met een GET?

[ Voor 109% gewijzigd door RobIII op 07-11-2006 01:40 ]

[BèR]

Ja, inderdaad, binair doorgeven is te doen, mits de ontvangende partij dat weer naar losse decimale cijfers kan omzetten als dat nodig is. Met 4 bits words of een VBR schema (sommige cijfers 3, andere 4 bits) valt het redelijk optimaal te doen.

[Thralas]

Je kunt natuurlijk wel gaan shiften e.d., zodat je bijvoorbeeld 2 4-bits waarden in een byte kwijt kan.

[.oisyn]

Binary coded decimals (4 bits per decimaal) worden wel vaker gebruikt hoor, de x86 CPU heeft zelfs speciale instructies om ermee te rekenen. En "of daar algoritmes voor bestaan", tja, het is vrij basic, ik denk niet dat iemand ooit moeite heeft gedaan dat soort dingen te bespreken in een paper oid

[MadMarky]

Die 4-bits waarden worden ook wel een nibble genoemd, via google zijn vast wel wat voorbeelden te vinden over het gebruik van nibbles icm Java.

[PanMan]

RobIII schreef op dinsdag 07 november 2006 @ 01:29:
Euh, hoe sla jij 25 op dan? Dat zou bij jou in 2 bytes moeten, namelijk een "2" en een "5". Bij mij past 25 (en 255 ook nog ) in 1 byte
Je haalt bits/bytes door elkaar denk ik. Een byte = 8 bits (bruggetje: "By eight" ~ "Byte")

Volgens mij weet ik wel hoe bits en bytes werken, maar wellicht leg ik het niet goed uit. Wat ik bedoel: Als ik hier een cijfer intype (de 2 uit jou 25, bv), dan kost dat, in de transfer en de GoT database, 1 byte, omdat het een van de 256 mogelijke inputs is. Normaal, als tekst, wordt jou 25 dus in 2 bytes opgeslagen. Als ik echter vantevoren weet dat de input alleen uit cijfers (en een scheidingsteken) zal bestaan, is het zonde om die zo te coderen dat er nog 245 mogelijkheden zijn, terwijl ik weet dat die niet gebruikt gaan worden. Ik vroeg me dus af of dat efficienter kan.
BCD ga ik naar kijken, het lijkt dat dat inderdaad iets heeft van wat ik zoek.

[RobIII]

PanMan schreef op dinsdag 07 november 2006 @ 01:43:
BCD ga ik naar kijken, het lijkt dat dat inderdaad iets heeft van wat ik zoek.

Trust me (us ), dat is wat je zoekt

edit:

Hier stond onzin; het is al laat

Ook in BCD heb je nog wat "slack" in je beschikbare ruimte; je gebruikt de bits niet optimaal. wil je ze optimaal gebruiken dan kun je uiteindelijk nog het beste gewoon de "binary" value sturen; dat dat raar uit ziet in ASCII is jammer dan.

Zo past het getal 34423445452 (11 digits) in 5 bytes:

code:

00001000 00000011 11001100 00010111 11001100

De ASCII representatie is dan iets "onleesbaars", maar exact dezelfde waarde (duh; het draait om een representatie van bits)

Om wat voor "cijferreeksen" gaat het?

[ Voor 36% gewijzigd door RobIII op 07-11-2006 01:54 ]

[burne]

RobIII schreef op dinsdag 07 november 2006 @ 01:48:
Trust me (us ), dat is wat je zoekt

Als je 11 mogelijkheden (10 cijfers en een separator) in 4 bits encode verspil je 0.6875 bit. Da's zonde en meestal niet nodig.

[RobIII]

burne schreef op dinsdag 07 november 2006 @ 01:51:
[...]

Als je 11 mogelijkheden (10 cijfers en een separator) in 4 bits encode verspil je 0.6875 bit. Da's zonde en meestal niet nodig.

Dat zeg ik...

[ Voor 13% gewijzigd door RobIII op 07-11-2006 01:55 ]

[Verwijderd]

.oisyn schreef op dinsdag 07 november 2006 @ 01:41:
Binary coded decimals (4 bits per decimaal) worden wel vaker gebruikt hoor, de x86 CPU heeft zelfs speciale instructies om ermee te rekenen. En "of daar algoritmes voor bestaan", tja, het is vrij basic, ik denk niet dat iemand ooit moeite heeft gedaan dat soort dingen te bespreken in een paper oid

Dat heet hexidecimaal

[Ricvdp]

HEX != BCD.

[Verwijderd]

Mocht de cijferreeks die je gaat verzenden van een vaste lengte zijn (bijvoorbeeld iedere keer 10 getallen) dan is er een eenvoudige mapping te maken naar de "unsigned" waarde van een getal. Daar valt verder niet veel aan te minimaliseren.

Mocht de lengte van de cijferreeks erg variëren dan is het ook mogelijk om een variabele lengte integer te gebruiken om de data te representeren. Hierbij wordt er bijvoorbeeld 1 bit per byte gebruikt als vlag om aan te geven of de volgende byte ook nog deel uit maakt van het getal.

Ofwel er zijn vele verschillende manier om een cijferreeks te mappen op een aantal bytes.

[Creepy]

Verwijderd schreef op dinsdag 07 november 2006 @ 04:50:
[...]


Dat heet hexidecimaal

Dat is niet waar.

BCD is een andere representatie van de getallen, maar is geen ander tallenstelsel. BCD kent geen A tot en met F.

Voorbeeld: 127 in bits in BCD notatie: 0001 0010 0111
0001 = 1
0010 = 2
0111 = 7
Letterlijk dus elk decimaal getal in bits gerepresenteerd.

127 in HEX = 7F. 7F gerepresenteerd in bits: 1111111. Toch wel een klein verschil dus

[Voutloos]

PanMan schreef op dinsdag 07 november 2006 @ 01:43:
Normaal, als tekst, wordt jou 25 dus in 2 bytes opgeslagen.

Beetje offtopic, maar wat je hier zegt is ook niet altijd waar, ivm character encoding. 1 teken != 1 byte.

[Icelus]

Voor wie interesse heeft in het rekenen in BCD in hogere programmeertalen:
Jones on BCD Arithmetic

[.oisyn]

Verwijderd schreef op dinsdag 07 november 2006 @ 04:50:
[...]


Dat heet hexidecimaal

Nee, maar de BCD string in hexadecimale notatie geeft wel precies dezelfde tekstuele representatie als dat getal in decimale notatie.

Getal in decimaal: 123
Dat wordt geencodeerd als 0001 0010 0011
In hex is dat: 123

.edit: en het wordt tijd dat ik eens topics ga lezen voor ik reageer
Gisteren had ik overigens nog een mooi verhaaltje over huffman coding getikt, maar mijn provider besloot dat het wel handig was om op dat moment onderhoud te gaan plegen, dus mijn verhaaltje is naar /dev/null. Maar goed, hier kun je daar meer over lezen

[ Voor 34% gewijzigd door .oisyn op 07-11-2006 11:23 ]

[PanMan]

RobIII schreef op dinsdag 07 november 2006 @ 01:29:
[...]
Hoe stuur je die cijferreeksen overigens naar de server? In de URL met een GET?

Dat was wel mijn bedoeling, ja. Maar deze vraag heeft me wel aan het denken gezet: Een GET kan natuurlijk niet alle karakters aan. En om het te gaan urlencoden, levert ws in totaal alleen maar een verlies op... Toch nog maar's kijken of ik in de praktijk hier echt iets mee opschiet.. Binnenkort maar's wat voorbeeldjes coden...

[Paul C]

PanMan schreef op dinsdag 07 november 2006 @ 15:01:
[...]


Dat was wel mijn bedoeling, ja. Maar deze vraag heeft me wel aan het denken gezet: Een GET kan natuurlijk niet alle karakters aan. En om het te gaan urlencoden, levert ws in totaal alleen maar een verlies op... Toch nog maar's kijken of ik in de praktijk hier echt iets mee opschiet.. Binnenkort maar's wat voorbeeldjes coden...

URLencoden schiet je niets mee op, want dan ga je een byte vervangen door drie bytes. Het is misschien wel interessant om je eigen codering toe te passen:

"...Only alphanumerics [0-9a-zA-Z], the special characters "$-_.+!*'()," [not including the quotes - ed], and reserved characters used for their reserved purposes may be used unencoded within a URL."

Dat levert dus 10+26+26+11=73 bruikbare bytewaardes. Maak hiervoor je eigen encoder en decoder (is niet zo moeilijk) en je kunt ²log(73ⁿ) bit binaire gegevens kwijt in n-bytes URL.

Als je hier zoveel moeite voor gaat doen, dan is het natuurlijk ook interessant om de rest van je URL zo kort mogelijk te houden, dus ik weet niet wat je serverside voor mogelijkheden hebt, maar een korte domeinnaam, geen 'www.' en een goede mod_rewrite (oid) kunnen je ook al veel besparen!

edit: Base64 is natuurlijk ook geen slecht idee:
http://en.wikipedia.org/wiki/Base64#URL_Applications

[ Voor 3% gewijzigd door Paul C op 07-11-2006 15:45 ]

[Verwijderd]

Hexadecimaal is van 1 tot en met 16. Je zou dit in 4 bits kunnen opslaan ({4²}4x4=16). Zoiets heet compressie en daar hebben we het ook over. Dat bedoelde ik dus

Dit topic lijkt erg op het LZ77 principe (Lempel-Ziv) welke op NTFS gebruikt wordt als compressie. Hier gaat het om strings van vaak vvoorkomende reeksen en hier kan de ASCII tabel voor gebruikt worden om maar 1-8 bit en niet altijd 8-bit te gebruiken voor een teken. De E en de N komen het meeste voor en krijgen de minste aantal bits toegewezen.
Van BCD heb ik niet zo heel veel kaas gegeten. Ik weet wel dat LZ77 een van de snelste vormen van compressie is zonder overhead en niet extreem rekenintensief.

een gecomprimeerde NTFS partitie kan in veel gevallen zelfs sneller zijn dan zonder compressie. De disk levert de data te traag aan om de CPU op 100% te zetten.

Heel rekenintensieve compressie met grote bibliotheken zoals PPMd of LZMA zijn traag met encoden en decoden en daardoor minder geschikt voor dagelijks gebruik. Ook kost het veel geheugen om terug te coderen wat bij LZ77 niet het geval is (64 KB bij LZ77).

PS: Mijn schijven zijn altijd gecomprimeerd geweest en ik merk geen verschil met andere identieke systemen zonder compressie. UT2004 is er zeker vlugger door geworden en ook 3,4 GB kleiner.

[ Voor 7% gewijzigd door Verwijderd op 07-11-2006 18:35 ]

[Woy]

PanMan schreef op dinsdag 07 november 2006 @ 15:01:
[...]


Dat was wel mijn bedoeling, ja. Maar deze vraag heeft me wel aan het denken gezet: Een GET kan natuurlijk niet alle karakters aan. En om het te gaan urlencoden, levert ws in totaal alleen maar een verlies op... Toch nog maar's kijken of ik in de praktijk hier echt iets mee opschiet.. Binnenkort maar's wat voorbeeldjes coden...

Als elke bit zo belangrijk is kan je dan niet beter gewoon een simpel protocolletje schrijven. Dan kan je nog veel meer besparen.
Als dat niet mogenlijk is kan je denk beter gewoon Post variabelen versturen en dan gewoon in binaire vorm.

[H!GHGuY]

tjah, het lijkt me dat adaptive huffman encoding voor dit geval wel het meest geschikt is.

Misschien dat Runlength Encoding bovenop BCD ook wel iets heeft.

[Janoz]

Verwijderd schreef op dinsdag 07 november 2006 @ 18:33:
Hexadecimaal is van 1 tot en met 16. Je zou dit in 4 bits kunnen opslaan ({4²}4x4=16). Zoiets heet compressie en daar hebben we het ook over. Dat bedoelde ik dus

Dat heet absoluut geen compressie en heeft daar ook weinig mee te maken. Waar het alles mee te maken heeft is grondtallen.

Dit topic lijkt erg op het LZ77 principe (Lempel-Ziv) welke op NTFS gebruikt wordt als compressie. Hier gaat het om strings van vaak vvoorkomende reeksen en hier kan de ASCII tabel voor gebruikt worden om maar 1-8 bit en niet altijd 8-bit te gebruiken voor een teken. De E en de N komen het meeste voor en krijgen de minste aantal bits toegewezen.
Van BCD heb ik niet zo heel veel kaas gegeten. Ik weet wel dat LZ77 een van de snelste vormen van compressie is zonder overhead en niet extreem rekenintensief.

ZUlke rocketsience is LZ77 ook weer niet hoor (komt zelfs al uit '77), daarnaast is een andere toepassing wel iets bekender. Iedereen kent immers wel de LZW gebruikende GIF bestanden

[Soultaker]

H!GHGuY schreef op dinsdag 07 november 2006 @ 18:59:
tjah, het lijkt me dat adaptive huffman encoding voor dit geval wel het meest geschikt is.

Da's is nog enigzins te doen. Misschien is adaptief coderen helemaal niet nodig (maakt het een stuk makkelijker om een efficiënt algoritme te maken).

Misschien dat Runlength Encoding bovenop BCD ook wel iets heeft.

Ik denk dat dat voor geen meter opschiet. Je hebt dan minstens vier dezelfde cijfers in een telefoonnummer nodig om twee dezelfde bytes te krijgen (én die cijfers moeten goed gealignd zijn), en dat is vrij zeldzaam.

Ik denk dat concreet BCD gewoon het praktisch is, of de TS moet handig een zip-library kunnen gebruiken. Zelf een compressor implementeren lijkt me eerlijk gezegd gewoon veel te veel werk, en ook een beetje zinloos.

edit:

Verwijderd schreef op dinsdag 07 november 2006 @ 18:33:
Dit topic lijkt erg op het LZ77 principe (Lempel-Ziv) welke op NTFS gebruikt wordt als compressie. Hier gaat het om strings van vaak vvoorkomende reeksen en hier kan de ASCII tabel voor gebruikt worden om maar 1-8 bit en niet altijd 8-bit te gebruiken voor een teken. De E en de N komen het meeste voor en krijgen de minste aantal bits toegewezen.

Dit laatste is nu juist wat LZ'77 niet doet. Het coderen van symbolen zo dat vaak-voorkomende kortere codes krijgen is entropie-codering (.oisyn noemde al Huffman codering), maar LZ'77 is een dictionary-coder. Het principe daarbij is als een substring meerdere keren voorkomt, je 'm maar één keer hoeft te versturen en je er daarna referenties naar kunt coderen, waarmee je ruimte kunt besparen als de substring langer is dan een referentie ernaar.

Entropie-codering lijkt mij hier veel zinniger; LZ'77 is vooral nuttig als de invoer zelf vaak-voorkomende substrings bevat (in de praktijk zijn compressors zoals zip en LZMA een combinatie van een dictionary-encoder en een entropie-encoder).

[ Voor 40% gewijzigd door Soultaker op 07-11-2006 20:38 ]

[Confusion]

PanMan schreef op dinsdag 07 november 2006 @ 01:25:
Het gaat om een javaprogramma'tje dat van een telefoon cijferreeksen moet doorsturen naar een webserver. Aangezien je hier per byte betaalt, is elke byte besparing er een, en zou je hiermee vrij veel kunnen besparen.

Hoeveel bytes denk je te gaan besparen en hoeveel kost de tijd die jij hier inmiddels al aan hebt besteed en nog al aan zal moeten besteden?

[RobIII]

Confusion schreef op dinsdag 07 november 2006 @ 20:58:
[...]

Hoeveel bytes denk je te gaan besparen en hoeveel kost de tijd die jij hier inmiddels al aan hebt besteed en nog al aan zal moeten besteden?

Dat vraag ik me inmiddels ook af, los van het feit dat ik me niet kan voorstellen dat 1 byte zo duur is. Ik neem aan dat je per KB (of zelfs per MB ) betaalt?

[PanMan]

Tuurlijk vallen de kosten wel een beetje mee. Maar als je hiermee je traffic zou kunnen halveren, zou het toch leuk zijn, toch? Zeker als je, per MB, tot 15E betaald, bij GPRS verkeer. Het gaat om een app die continu zou draaien, en bijvoorbeeld elke min een update zou doen.
Bovendien vind ik het gewoon wel leuk om er over na te denken, het hoeft niet altijd even efficient te zijn, het moet ook een beetje leuk blijven.
Maar ik zit wel te twijfelen of het in de praktijk efficient is om hier naar te kijken: Een HTTP request is al snel 50 bytes, en daar kan je al niet op besparen (wel met een korte hostname, enzo, maar je houdt een bepaald minimum).