Re: sparse bitset compression

--===============8308050794356208945==
Content-Type: multipart/alternative; boundary=001a1139569e52e83904f07682d2

--001a1139569e52e83904f07682d2
Content-Type: text/plain; charset=UTF-8

Here's a modern Run Length version of Golomb-Rice encoding designed for
compressing general data with a Generalized Gaussian distribution. Works
best if you can prove there are, in most cases, small differences between
adjacent data (but handily you get to define what "adjacent" means to your
stream). Encode a single starting value at full bandwidth then send a
stream of differences:

    https://research.microsoft.com/pubs/102069/malvar_dcc06.pdf

As a bonus, if you're encoding depth images, you can remap the values to
leave zero as an out-of-band value:

    http://www.charlesneedham.com/pubs/153971/depthcode-final.pdf

Yes, I know that wasn't the question you asked but at least it's an
algorithm. :-)

- Robin Green



On Fri, Jan 17, 2014 at 10:04 AM, Alex Walters <[email protected]>wrote:

> Its on the fringe of being useful, but one thing you could look at to
> reduce your data size is Exponential Golomb coding (
> http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in
> H.264 entropy encoding among other things.
>
> Instead of writing a full n-bit values for every number you store, it
> produces a bit stream of codes, using far less bits for small numbers -
> take a look at the wiki page, its pretty simple to see whats going on when
> you look at the example. It can reduce the amount of data you have to move,
> and from what I remember from when I worked with video, it produces much
> more predictable (and compressible) stream of bits for the next compression
> scheme along (variable length encoding, or arithmetic encoding in the case
> of H.264) - I've not looked into the details but could probably improve the
> compression of the stream you get through gzip.
>
> Regards,
>
> Alex
>
>
>

--001a1139569e52e83904f07682d2
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><div class=3D"gmail_extra">Here&#39;s a modern Run Len=
gth version of Golomb-Rice encoding designed for compressing general data w=
ith a Generalized Gaussian distribution. Works best if you can prove there =
are, in most cases, small differences between adjacent data (but handily yo=
u get to define what &quot;adjacent&quot; means to your stream). Encode a s=
ingle starting value at full bandwidth then send a stream of differences:</=
div>
<div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">=C2=A0 =C2=
=A0 <a href=3D"https://research.microsoft.com/pubs/102069/malvar_dcc06.pdf"=
>https://research.microsoft.com/pubs/102069/malvar_dcc06.pdf</a><br></div><=
div class=3D"gmail_extra">
<br></div><div class=3D"gmail_extra">As a bonus, if you&#39;re encoding dep=
th images, you can remap the values to leave zero as an out-of-band value:<=
/div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">=C2=A0=
 =C2=A0 <a href=3D"http://www.charlesneedham.com/pubs/153971/depthcode-fina=
l.pdf">http://www.charlesneedham.com/pubs/153971/depthcode-final.pdf</a><br=
>
</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Yes, =
I know that wasn&#39;t the question you asked but at least it&#39;s an algo=
rithm. :-)</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_ex=
tra">
- Robin Green</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail=
_extra"><br><br><div class=3D"gmail_quote">On Fri, Jan 17, 2014 at 10:04 AM=
, Alex Walters <span dir=3D"ltr">&lt;<a href=3D"mailto:[email protected]=
m" target=3D"_blank">[email protected]</a>&gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div dir=3D"ltr">Its on the fringe of being useful, but on=
e thing you could look at to reduce your data size is Exponential Golomb co=
ding (<a href=3D"http://en.wikipedia.org/wiki/Exponential-Golomb_coding" ta=
rget=3D"_blank">http://en.wikipedia.org/wiki/Exponential-Golomb_coding</a>)=
, its used in H.264 entropy encoding among other things.<div>

<br></div><div>Instead of writing a full n-bit values for every number you =
store, it produces a bit stream of codes, using far less bits for small num=
bers - take a look at the wiki page, its pretty simple to see whats going o=
n when you look at the example. It can reduce the amount of data you have t=
o move, and from what I remember from when I worked with video, it produces=
 much more predictable (and compressible) stream of bits for the next compr=
ession scheme along (variable length encoding, or arithmetic encoding in th=
e case of H.264) - I&#39;ve not looked into the details but could probably =
improve the compression of the stream you get through gzip.<div>

<br></div><div>Regards,</div><div><br></div><div>Alex</div></div></div><div=
 class=3D"gmail_extra"><br><br></div></blockquote></div></div></div>

--001a1139569e52e83904f07682d2--


--===============8308050794356208945==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

------------------------------------------------------------------------------
CenturyLink Cloud: The Leader in Enterprise Cloud Services.
Learn Why More Businesses Are Choosing CenturyLink Cloud For
Critical Workloads, Development Environments & Everything In Between.
Get a Quote or Start a Free Trial Today. 
http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
--===============8308050794356208945==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
--===============8308050794356208945==--