Re: sparse bitset compression
Richard Fabian <[email protected]> Fri, 31 Jan 2014 23:27:26 +0000
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <CACot5u2J97QKE8Va6E-tH6TMwX7Gok_MJ-sba78ZW-1gg29JxA@mail.gmail.com> |
--===============8197179470284728272== Content-Type: multipart/alternative; boundary=001a11c0dd9614cb7104f14c8691 --001a11c0dd9614cb7104f14c8691 Content-Type: text/plain; charset=ISO-8859-1 there was a lot of similarity, but with no processng at the destination, we decided that the Golomb-rice algorithm was good enough. Dropped our data by 70%. That was enough of a saving for this one area. On 31 January 2014 21:32, Jon Watte <[email protected]> wrote: > 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 >> > > > > ------------------------------------------------------------------------------ > 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 > _______________________________________________ > 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 > -- fabs(); "The fact that an opinion has been widely held is no evidence whatever that it is not utterly absurd." - Bertrand Russell --001a11c0dd9614cb7104f14c8691 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">there was a lot of similarity, but with no processng at th= e destination, we decided that the Golomb-rice algorithm was good enough. D= ropped our data by 70%. That was enough of a saving for this one area.</div= > <div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On 31 January= 2014 21:32, Jon Watte <span dir=3D"ltr"><<a href=3D"mailto:jwatte@gmail= .com" target=3D"_blank">[email protected]</a>></span> wrote:<br><blockquo= te class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc so= lid;padding-left:1ex"> <div dir=3D"ltr"><div class=3D"im"><blockquote class=3D"gmail_quote" style= =3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20= 4,204,204);border-left-style:solid;padding-left:1ex">Encode a single starti= ng value at full bandwidth then send a stream of differences:</blockquote> <div><br></div></div><div>Which is equivalent to a wavelet "lift"= transform :-)</div><div><br></div><div>Back to the original question: If y= ou have 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>"<span style>I find that the harder I work, the more luck I seem t= o have." -- Thomas Jefferson</span></font></div> </div> <br><br><div class=3D"gmail_quote"><div><div class=3D"h5">On Tue, Jan 21, 2= 014 at 12:08 AM, Robin Green <span dir=3D"ltr"><<a href=3D"mailto:robin.= [email protected]" target=3D"_blank">[email protected]</a>></span> wro= te:<br> </div></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo= rder-left:1px #ccc solid;padding-left:1ex"><div><div class=3D"h5"> <div dir=3D"ltr"><br><div class=3D"gmail_extra">Here'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 "adjacent" 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">=A0 =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'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">=A0 = =A0 <a href=3D"http://www.charlesneedham.com/pubs/153971/depthcode-final.pd= f" target=3D"_blank">http://www.charlesneedham.com/pubs/153971/depthcode-fi= nal.pdf</a><br> </div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Yes, = I know that wasn't the question you asked but at least it's an algo= rithm. :-)</div><span><font color=3D"#888888"><div class=3D"gmail_extra"> <br></div><div class=3D"gmail_extra"> - Robin Green</div></font></span><div><div class=3D"gmail_extra"><br></div>= <div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On Fri, Jan 1= 7, 2014 at 10:04 AM, Alex Walters <span dir=3D"ltr"><<a href=3D"mailto:a= [email protected]" target=3D"_blank">[email protected]</a>></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'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></div></div><div class=3D"im">-----------------------------------------= -------------------------------------<br> CenturyLink Cloud: The Leader in Enterprise Cloud Services.<br> Learn Why More Businesses Are Choosing CenturyLink Cloud For<br> Critical Workloads, Development Environments & 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&iu= =3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam= pad/clk?id=3D119420431&iu=3D/4140/ostg.clktrk</a><br>__________________= _____________________________<br> GDAlgorithms-list mailing list<br> <a href=3D"mailto:[email protected]" target=3D"_blank= ">[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></div></blockquote></div><br></div> <br>-----------------------------------------------------------------------= -------<br> WatchGuard Dimension instantly turns raw network data into actionable<br> security intelligence. It gives you real-time visual feedback on key<br> security issues and trends. =A0Skip the complicated setup - simply import<b= r> a virtual appliance and go from zero to informed in seconds.<br> <a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D123612991&iu= =3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam= pad/clk?id=3D123612991&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><br clear=3D"= all"> <div><br></div>-- <br><div dir=3D"ltr">fabs();<div><span style=3D"color:rgb= (0,0,0);font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;fon= t-size:14px;line-height:20px">"The fact that an opinion has been widel= y held is no evidence whatever that it is not utterly absurd." - Bertr= and Russell</span><br> </div></div> </div> --001a11c0dd9614cb7104f14c8691-- --===============8197179470284728272== 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 --===============8197179470284728272== 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 --===============8197179470284728272==--