Re: sparse bitset compression
Richard Fabian <[email protected]> Sun, 9 Mar 2014 16:40:20 +0000
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <CACot5u0qqEsQXaniYpXDRqpr3pEE_JAHC8W45db_RsNVkr-swA@mail.gmail.com> |
--===============2805827124094171682== Content-Type: multipart/alternative; boundary=001a11c29e9057ec3704f42f26cc --001a11c29e9057ec3704f42f26cc Content-Type: text/plain; charset=ISO-8859-1 AC (and now Finite State Entropy https://github.com/Cyan4973/FiniteStateEntropy) are really good, but carry the weight of spending more time than we had to do the task. Goulomb coding the distance between high bits was a great, simple to implement solution for us. Another issue was the compression time. It needed to be quick, and AC is not known to be fast. In future, I hope to use FSE for almost all my lossless coders. On 8 March 2014 15:13, Colt McAnlis <[email protected]> wrote: > 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 > > > ------------------------------------------------------------------------------ > 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 > _______________________________________________ > 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 --001a11c29e9057ec3704f42f26cc Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">AC (and now Finite State Entropy=A0<a href=3D"https://gith= ub.com/Cyan4973/FiniteStateEntropy">https://github.com/Cyan4973/FiniteState= Entropy</a>) are really good, but carry the weight of spending more time th= an we had to do the task. Goulomb coding the distance between high bits was= a great, simple to implement solution for us. Another issue was the compre= ssion time. It needed to be quick, and AC is not known to be fast.<div> <br></div><div>In future, I hope to use FSE for almost all my lossless code= rs.<br><div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On 8 M= arch 2014 15:13, Colt McAnlis <span dir=3D"ltr"><<a href=3D"mailto:mainr= [email protected]" target=3D"_blank">[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">Why not just use industry s= tandard Arithmetic Compression?<div><br><div>If you calculate the estimated= entropy for that data set (<a href=3D"http://planetcalc.com/2476/" target= =3D"_blank">http://planetcalc.com/2476/</a>) you end 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"><div>= <div class=3D"h5"><br><br><div class=3D"gmail_quote">On Fri, Jan 31, 2014 a= t 3:27 PM, Richard Fabian <span dir=3D"ltr"><<a href=3D"mailto:raspo1@gm= ail.com" target=3D"_blank">[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>On = 31 January 2014 21:32, Jon Watte <span dir=3D"ltr"><<a href=3D"mailto:jw= [email protected]" 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"><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><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> <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]" 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></blockquote></div><br><br clear=3D"= all"> <div><br></div>-- <br></div></div>=3D=3D<br>Colt "MainRoach" McAn= lis<br>Graphics Programmer </div> <br>-----------------------------------------------------------------------= -------<br> Subversion Kills Productivity. Get off Subversion & Make the Move to Pe= rforce.<br> With Perforce, you get hassle-free workflows. Merge that actually works.<br= > Faster operations. Version large binaries. =A0Built-in WAN optimization and= the<br> freedom to use Git, Perforce or both. Make the move to Perforce.<br> <a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D122218951&iu= =3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam= pad/clk?id=3D122218951&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></div></div> --001a11c29e9057ec3704f42f26cc-- --===============2805827124094171682== 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 --===============2805827124094171682== 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 --===============2805827124094171682==--