Re: sparse bitset compression
Richard Fabian <[email protected]> Sat, 18 Jan 2014 00:10:02 +0000
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <CACot5u0QOMxSN5Msjt0RpJLG3RzkOny1Qv4qfT9THB3Q9a4HNA@mail.gmail.com> |
--===============4079160985694891007== Content-Type: multipart/alternative; boundary=001a11c2bfb4ae131304f0337c34 --001a11c2bfb4ae131304f0337c34 Content-Type: text/plain; charset=ISO-8859-1 hah, that was funny. I looked at the link, then realised that it was the same as what I'm doing except I pack with ones instead of zeros. 0 -> 0 100 -> 1 101 -> 2 11000 -> 3 etc. I'm pretty sure i read about this in a jpeg compression book more than 10 years ago. On 17 January 2014 18:04, 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 > > > On Fri, Jan 17, 2014 at 10:14 AM, Richard Fabian <[email protected]> wrote: > >> I would question this assumption: >>> >>> This is too much for sending over the network regularly as part of a >>>> save. >>> >>> >>> >> >> Well, we've got our play-through logs showing how much data was being >> sent per day per user, and this part of the save was the bit being updated >> the most. Over a day of play it was adding up to about 5mb I think (can't >> remember precisely now) and this made it into the top three we needed to >> compress better to reduce the client bandwidth cost (mobile carrier data >> limits and all that). >> >> >> >>> If I had to compress the data you talk about, I might want to look into >>> some implicit representation, like a quad tree with filled/not nodes. >>> Something like: >>> "Does the current sub-area have entities? If not, store 0, and >>> terminate. Else store 1. If the size of the sub-area is greater than one, >>> subdivide, and recurse for each sub-quadrant." >>> Depending on how clustered the entities are, this may compress well or >>> poorly (but with a max 7% fill rate, it ought to at least compress >>> somewhat.) >>> >> >> I had thought about a quad tree, but I think I chose to not go that way >> because my previous experience with them was that they're not quite as >> efficient in practice as the should be. I can't remember why I think this, >> but I remember working through some code and thinking something along the >> lines of "Oh, yeah. Of course" but that might have been because the data >> involved wasn't quite as clumpy. >> >> >>> Apply gzip on top of any encoding you come up with for possible bonus >>> gains. >>> >>> that's part of the network layer, so no point in doing it explicitly. >> >> >>> Sincerely, >>> >>> jw >>> >>> >>> Thanks, I might try the quad tree idea again. >> >> >> ------------------------------------------------------------------------------ >> 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 >> > > > > ------------------------------------------------------------------------------ > 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 > -- fabs(); "The fact that an opinion has been widely held is no evidence whatever that it is not utterly absurd." - Bertrand Russell --001a11c2bfb4ae131304f0337c34 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">hah, that was funny. I looked at the link, then realised t= hat it was the same as what I'm doing except I pack with ones instead o= f zeros.<div>0 -> 0</div><div>100 -> 1</div><div>101 -> 2</div><di= v> 11000 -> 3</div><div>etc.</div><div>I'm pretty sure i read about thi= s in a jpeg compression book more than 10 years ago.</div></div><div class= =3D"gmail_extra"><br><br><div class=3D"gmail_quote">On 17 January 2014 18:0= 4, Alex Walters <span dir=3D"ltr"><<a href=3D"mailto:[email protected]= om" 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">Its on the fringe of being = useful, but one thing you could look at to reduce your data size is Exponen= tial Golomb coding (<a href=3D"http://en.wikipedia.org/wiki/Exponential-Gol= omb_coding" target=3D"_blank">http://en.wikipedia.org/wiki/Exponential-Golo= mb_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 class=3D"gmail_quote"><div><div class= =3D"h5">On Fri, Jan 17, 2014 at 10:14 AM, Richard Fabian <span dir=3D"ltr">= <<a href=3D"mailto:[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 class=3D"h5"><div dir= =3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div><blockq= uote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-wi= dth:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-= left:1ex"> <div dir=3D"ltr">I would question this assumption:<div><div><br></div><bloc= kquote 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;paddin= g-left:1ex"> <span style=3D"font-family:arial,sans-serif;font-size:12.800000190734863px"= >This is too much for sending over the network regularly as part of a save.= </span></blockquote><div><span style=3D"color:rgb(34,34,34)">=A0</span></di= v> </div></div></blockquote><div><br></div></div><div><div class=3D"gmail_quot= e">Well, we've got our play-through logs showing how much data was bein= g sent per day per user, and this part of the save was the bit being update= d the most. Over a day of play it was adding up to about 5mb I think (can&#= 39;t remember precisely now) and this made it into the top three we needed = to compress better to reduce the client bandwidth cost (mobile carrier data= limits and all that).</div> </div><div><div><br></div><div>=A0</div><blockquote class=3D"gmail_quote" s= tyle=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rg= b(204,204,204);border-left-style:solid;padding-left:1ex"><div dir=3D"ltr"> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px">If I had to compress the data you talk about, I might want to look in= to some implicit representation, like a quad tree with filled/not nodes. So= mething like:</span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px">"Does the current sub-area have entities? If not, store 0, and t= erminate. Else store 1. If the size of the sub-area is greater than one, su= bdivide, and recurse for each sub-quadrant."</span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px">Depending on how clustered the entities are, this may compress well o= r poorly (but with a max 7% fill rate, it ought to at least compress somewh= at.)</span></div> </div></blockquote><div><br></div></div><div>I had thought about a quad tre= e, but I think I chose to not go that way because my previous experience wi= th them was that they're not quite as efficient in practice as the shou= ld be. I can't remember why I think this, but I remember working throug= h some code and thinking something along the lines of "Oh, yeah. Of co= urse" but that might have been because the data involved wasn't qu= ite as clumpy.=A0</div> <div> <div>=A0</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);border-left= -style:solid;padding-left:1ex"><div dir=3D"ltr"><div><span style=3D"font-fa= mily:arial,sans-serif;font-size:12.800000190734863px"></span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px">Apply gzip on top of any encoding you come up with for possible bonus= gains.</span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px"><br></span></div></div></blockquote></div><div>that's part of the= network layer, so no point in doing it explicitly.</div><div>=A0</div><blo= ckquote 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;paddi= ng-left:1ex"> <div dir=3D"ltr"><div><span style=3D"font-family:arial,sans-serif;font-size= :12.800000190734863px"></span></div><div><span style=3D"font-family:arial,s= ans-serif;font-size:12.800000190734863px">Sincerely,</span></div><div><span= style=3D"font-family:arial,sans-serif;font-size:12.800000190734863px"><br> </span></div><div><span style=3D"font-family:arial,sans-serif;font-size:12.= 800000190734863px">jw</span></div><div><span style=3D"font-family:arial,san= s-serif;font-size:12.800000190734863px"><br></span></div><div><br></div></d= iv> </blockquote><div>Thanks, I might try the quad tree idea again.=A0</div></d= iv> </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> 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]">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> --001a11c2bfb4ae131304f0337c34-- --===============4079160985694891007== 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 --===============4079160985694891007== 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 --===============4079160985694891007==--