Re: sparse bitset compression

--===============8099662879560999714==
Content-Type: multipart/alternative; boundary=001a11368e7699b93a04f14ae7c0

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

>
> Encode a single starting value at full bandwidth then send a stream of
> differences:


Which is equivalent to a wavelet "lift" transform :-)

Back to the original question: If you have a previous save game, is there
lots of similarity in the next save? If so, can you save a delta instead?
If not, what solution did you end up choosing?

Sincerely,

jw






Sincerely,

Jon Watte


--
"I find that the harder I work, the more luck I seem to have." -- Thomas
Jefferson


On Tue, Jan 21, 2014 at 12:08 AM, Robin Green <[email protected]> wrote:

>
> 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
>>
>>
>>
>
> ------------------------------------------------------------------------------
> 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
> _______________________________________________
> 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
>

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

<div dir=3D"ltr"><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-l=
eft-style:solid;padding-left:1ex">Encode a single starting value at full ba=
ndwidth then send a stream of differences:</blockquote>
<div><br></div><div>Which is equivalent to a wavelet &quot;lift&quot; trans=
form :-)</div><div><br></div><div>Back to the original question: If you hav=
e a previous save game, is there lots of similarity in the next save? If so=
, can you save a delta instead?</div>
<div>If not, what solution did you end up choosing?</div><div><br></div><di=
v>Sincerely,</div><div><br></div><div>jw</div><div><br></div><div><br></div=
></div><div class=3D"gmail_extra"><br clear=3D"all"><div><div dir=3D"ltr"><=
font face=3D"courier new, monospace"><br>
<br><br><font>Sincerely,</font><br><br><font>Jon Watte</font><br><br><br>--=
<br>&quot;<span style=3D"color:rgb(0,0,0)">I find that the harder I work, t=
he more luck I seem to have.&quot; -- Thomas Jefferson</span></font></div>
</div>
<br><br><div class=3D"gmail_quote">On Tue, Jan 21, 2014 at 12:08 AM, Robin =
Green <span dir=3D"ltr">&lt;<a href=3D"mailto:[email protected]" target=
=3D"_blank">[email protected]</a>&gt;</span> wrote:<br><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex">
<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"=
 target=3D"_blank">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" target=3D"_blank">http://www.charlesneedham.com/pubs/153971/depthcod=
e-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><span class=3D"HOEnZb"><font color=3D"#888888"><div class=
=3D"gmail_extra">
<br></div><div class=3D"gmail_extra">
- Robin Green</div></font></span><div class=3D"im"><div class=3D"gmail_extr=
a"><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 hre=
f=3D"mailto:[email protected]" 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></div>
<br>-----------------------------------------------------------------------=
-------<br>
CenturyLink Cloud: The Leader in Enterprise Cloud Services.<br>
Learn Why More Businesses Are Choosing CenturyLink Cloud For<br>
Critical Workloads, Development Environments &amp; Everything In Between.<b=
r>
Get a Quote or Start a Free Trial Today.<br>
<a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D119420431&amp;iu=
=3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam=
pad/clk?id=3D119420431&amp;iu=3D/4140/ostg.clktrk</a><br>__________________=
_____________________________<br>

GDAlgorithms-list mailing list<br>
<a href=3D"mailto:[email protected]">GDAlgorithms-lis=
[email protected]</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" =
target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms=
-list</a><br>
Archives:<br>
<a href=3D"http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgo=
rithms-list" target=3D"_blank">http://sourceforge.net/mailarchive/forum.php=
?forum_name=3Dgdalgorithms-list</a><br></blockquote></div><br></div>

--001a11368e7699b93a04f14ae7c0--


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

------------------------------------------------------------------------------
WatchGuard Dimension instantly turns raw network data into actionable 
security intelligence. It gives you real-time visual feedback on key
security issues and trends.  Skip the complicated setup - simply import
a virtual appliance and go from zero to informed in seconds.
http://pubads.g.doubleclick.net/gampad/clk?id=123612991&iu=/4140/ostg.clktrk
--===============8099662879560999714==
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
--===============8099662879560999714==--