http://nlp.stanford.edu/IR-book/html/htmledition/gamma-codes-1.html
gamma codes are a way of representing an arbitrary sequence of
positive integers. For an n bit value, the corresponding gamma code
will occupy 2n-1 bits.
So, for example, they could be used to represent 1+rank and 1+shape in
a network protocol, and the result would always be more space
efficient than encoding them as 32 bit or 64 bit values.
Like most implementations of space efficiency, they tend to not be
very time efficient, though hypothetically speaking "that's just a
hardware issue".
Here's an implementation:
gamma=: ([: ; <@(#&1@#, 0:, ])@}.@#:"0) :. gamma
ungamma=:3 :0 :. ungamma
r=. i. 0
while. #y do.
len=. y i. 0
r=. r, #. 1, len {. (1+len) }. y
y=. (1+2*len) }. y
end.
r
)
And here's an example of encoding rank and shape of an array A, using
gamma codes:
gamma 1 + (#@$, $) A
In this example, we only need 10 bits:
gamma 1 + (#@$, $) i. 8
1 0 0 1 1 1 0 0 0 1
That said, since gamma codes can only represent positive integers,
they probably are not the right way to encode the data of A, so this
is an incomplete scheme.
(Space efficient network representation of the data of A should
probably take into account the results of aggregate operations on A
(min, max, ...) and of course the type of the data.)
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
