[Jprogramming] variable integer coding (challenge)

Tue Dec 30 18:18:39 UTC 2014

I also provided some adverbs

toVint =: 1 : '[: (({."1 ,. 1:) #&, m ,. {:"1) (0, m) #: ]' 
fromVint=: 1 : 'm&~: +/;.2 ]'

these let you set the breakup point to what you wish

  15 toVint 33 12 17 
15 15 3 12 15 2 
  511 toVint 1233 
511 511 211 

  511 fromVint 511 toVint 1233 444 
1233 444
It can provide simple compression.  If you have a list of many strings where almost all of them will fit into a 6bit alphabet, you can still encode a full 7 bit or 8bit alphabet.  On average, you'd save space using 6bit alphabet, depending on your context.

The variable string functions I showed, still let you do a substring search on the packed data.  Part of it is disk and memory compression (don't expand until you need to, and a string takes much less memory than a list of numbers < 256), but part of it is not being forced in design to determine what the impossible cutoff number is.

A big advantage related to J is having binary data records.  If you encode the length of the binary data, you no longer have to box them if a trailing 0 or space would be difficult to know whether it is a fill or intentional.

Beyond binary data, there is dumb stuff such as storing addresses.  Most people have just 1,  Most fit within 255 bytes.  Usually no one cares about address info except when they do or already have the client record.  Do you really want a separate table with 1 to many join with a possible 10000 character fixed size per address just because you're unsure if it will ever be possible for you to store an address to an African village as a set of driving instructions and then a description of the house relative to 3 other houses and landmarks just in case one of the other houses gets painted.

Another neat feature about the coding method is that if you have a lot of inefficient codes, ie. storing 1020 as 255 255 255 255 0, it at least compresses well.

A minor thing is that the encoding still lets you do search by < or >.  If you are storing the number of orders per customer.  The first byte tells you whether it is > 254 or less than any other number below 255 (probably enough info to select customers of interest).  Another minor thing is that you don't have to use the encoding codes until there is an overflow.  It may be easier to just switch functions to decode variable data, then to reshape terrabytes of data.
________________________________
From: Joe Bogner <joebogner at gmail.com>
To: programming at jsoftware.com 
Sent: Tuesday, December 30, 2014 10:45 AM
Subject: Re: [Jprogramming] variable integer coding (challenge)

Pascal,

Thanks for sharing. Can you also share a potential use case?

I had to remind myself about the size of integers (4 bytes) on 32-bit.

Will this only save space on numbers less than 1019?

NB. 4 bytes
toVint2 1019
255 255 255 254

NB. 5 bytes
toVint2 1020
255 255 255 255 0

Are you looking for the savings in terms of disk space (saving it to a
file) or working memory?

On Mon, Dec 29, 2014 at 12:12 PM, 'Pascal Jasmin' via Programming
<programming at jsoftware.com> wrote:
> A common design decision is how large to make a field.  For many numbers, we think that a byte will be large enough to hold practical values, but one day we will find out that it is not.  This is essentially the Y2k problem, or year 2032 issue.
>
> A simple variable integer coding (tied to byte ranges)
>
> toVint =: [: ; (255&| ,~ 255 #~ <.@%&255) each
>
>   toVint 566 44
> 255 255 56 44
>
> It now takes 3 bytes to store 566, and one byte to store 44.
>
> the challenge is to write fromVint such that
>
>
> 566 44 -: fromVint 255 255 56 44
>
> as an extra challenge, is there a way to write toVint or fromVint such that it is faster than using intermediate boxing?
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm