Re: sparse bitset compression
Colt McAnlis <[email protected]> Sat, 8 Mar 2014 07:13:15 -0800
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <CAE=eMOt3BAymk3iRhXM-2rc0y-chGqY0v7eVAyu-5bmvrS2JtQ@mail.gmail.com> |
--===============3823992793810722942== Content-Type: multipart/alternative; boundary=089e0115f36849a9b904f419cfef --089e0115f36849a9b904f419cfef Content-Type: text/plain; charset=ISO-8859-1 Why not just use industry standard Arithmetic Compression? If you calculate the estimated entropy for that data set ( http://planetcalc.com/2476/) you end up with about H=0.06 for 7k set bits in a 1024*1024 stream, and H=0.01 for 1k set bits. That being entropy (or minimum bits per symbol) should yield 70kb and 10k after compression, respectively. Or, with AC, and those sparse values, you can get around 94% compression and 99% compression. (if my early morning math is right) AC is a known algorithm, easy examples to find on the web. And as far a serialization is concerned, it's pretty straight forward to just encode your bits, then decode; no extra special data structures needed. ~Main On Fri, Jan 31, 2014 at 3:27 PM, Richard Fabian <[email protected]> wrote: > 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 > > > ------------------------------------------------------------------------------ > 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 > -- == Colt "MainRoach" McAnlis Graphics Programmer --089e0115f36849a9b904f419cfef Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Why not just use industry standard Arithmetic Compression?= <div><br><div>If you calculate the estimated entropy for that data set (<a = href=3D"http://planetcalc.com/2476/">http://planetcalc.com/2476/</a>) you e= nd up with about H=3D0.06 for 7k set bits in a 1024*1024 stream, and H=3D0.= 01 for 1k set bits.</div> <div>That being entropy (or minimum bits per symbol) should yield 70kb and = 10k after compression, respectively. Or, with AC, and those sparse values, = you can get around 94% compression and 99% compression. (if my early mornin= g math is right)</div> <div><br></div><div>AC is a known algorithm, easy examples to find on the w= eb. And as far a serialization is concerned, it's pretty straight forwa= rd to just encode your bits, then decode; no extra special data structures = needed.</div> <div><br></div><div>~Main</div></div></div><div class=3D"gmail_extra"><br><= br><div class=3D"gmail_quote">On Fri, Jan 31, 2014 at 3:27 PM, Richard Fabi= an <span dir=3D"ltr"><<a href=3D"mailto:[email protected]" target=3D"_bla= nk">[email protected]</a>></span> wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"><div dir=3D"ltr">there was a lot of similari= ty, but with no processng at the destination, we decided that the Golomb-ri= ce algorithm was good enough. Dropped 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"><div><div cla= ss=3D"h5">On 31 January 2014 21:32, Jon Watte <span dir=3D"ltr"><<a href= =3D"mailto:[email protected]" target=3D"_blank">[email protected]</a>></sp= an> wrote:<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"><div><blockquote class=3D"gmail_quote" style=3D"margin:0px= 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);bor= der-left-style:solid;padding-left:1ex">Encode a single starting value at fu= ll 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>I find that the harder I work, the more luck I seem to have= ." -- Thomas Jefferson</span></font></div> </div> <br><br><div class=3D"gmail_quote"><div><div>On Tue, Jan 21, 2014 at 12:08 = AM, Robin Green <span dir=3D"ltr"><<a href=3D"mailto:[email protected]= om" target=3D"_blank">[email protected]</a>></span> wrote:<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> <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>------------------------------------------------------= ------------------------<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></div></div>-----------------------------------------------------------= -------------------<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><div class=3D""><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><br cle= ar=3D"all"> <div class=3D""> <div><br></div>-- <br><div dir=3D"ltr">fabs();<div><span style=3D"line-heig= ht:20px;font-size:14px;font-family:'Helvetica Neue',Helvetica,Arial= ,sans-serif">"The fact that an opinion has been widely held is no evid= ence whatever that it is not utterly absurd." - Bertrand Russell</span= ><br> </div></div> </div></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>=3D=3D<br>Colt "MainRoach" McAnlis<br>Graph= ics Programmer </div> --089e0115f36849a9b904f419cfef-- --===============3823992793810722942== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline ------------------------------------------------------------------------------ Subversion Kills Productivity. Get off Subversion & Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951&iu=/4140/ostg.clktrk --===============3823992793810722942== 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 --===============3823992793810722942==--