Re: sparse bitset compression
Richard Fabian <[email protected]> Tue, 14 Jan 2014 19:40:34 +0000
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <CACot5u0YqMcUbkkLfo0o8RTKtUfA4ETZY7up-uDy1S-4DZWQjA@mail.gmail.com> |
--===============7974018517924318306== Content-Type: multipart/alternative; boundary=047d7b676f7c764f4d04eff35fc3 --047d7b676f7c764f4d04eff35fc3 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable I was going to plug in the morten coded version. Code from ryg's blog. http://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/ On 14 January 2014 19:11, Chris Birke <[email protected]> wrote: > You might also look into morton order encoding, as it is a simple and > efficient locality preserving way to do lossless n dimensional tree > structures - this is of course best for applications like map data. Your > mileage may vary. > > -Chria > > =E1=BC=80=CF=80=E1=BD=B8 =CE=BC=CE=B7=CF=87=CE=B1=CE=BD=E1=BF=86=CF=82 iP= hone 5 > > On Jan 14, 2014, at 9:01 AM, Oscar Forth <[email protected]= > > wrote: > > Pretty much. > > The space filling curve might not be necessary but you may be able to use > it to keep smaller gaps between the entries which are local to each other > spatially. > > > On 14 January 2014 16:52, Richard Fabian <[email protected]> wrote: > >> That sounds good. Something like the JPEG VLC for the actual distance >> between entries and just store deltas on a space filling curve should be >> good then. >> >> >> On 14 January 2014 13:11, Oscar Forth <[email protected]>w= rote: >> >>> Just a random though, so apologies if i'm talking about my arse, but ..= . >>> couldn't you just use something like the bit plane compression from Wav= elet >>> Difference Reduction (WDR)? >>> >>> A lot depends on your data, I appreciate, so this may not work out as >>> any significant saving ... >>> >>> I wrote about the compression method in my blog a few years back: >>> >>> http://trueharmoniccolours.co.uk/Blog/?p=3D55 >>> >>> Obviously thats in the context of a full wavelet image compressor so yo= u >>> will have to just grab the part I explain in the link above. >>> >>> Also apologies for the code formatting on my blog ... ill fix it one da= y >>> ;) >>> >>> Oscar >>> >>> On 14 January 2014 12:37, Richard Fabian <[email protected]> wrote: >>> >>>> The web is full of different solutions for compressing things, but som= e >>>> of you have probably already done this and found a really good ratio >>>> compression scheme that fits what I'm asking about. >>>> >>>> I've got a load of entites, (4-7k) that live on a grid (1024x1024), an= d >>>> I need to persist them to a savegame which gets sent across the networ= k to >>>> keep the save safe. I need to compress it. I'm compressing the entitie= s in >>>> the world already, ones that have been affected cost a few bytes, but = the >>>> but for the ones that don't have any changes, all I'm left with is the >>>> coords. There are only a few that need the fatter compression, but at = the >>>> numbers I'm looking at, those "unchanged entity" coords add up to a lo= t of >>>> data when storing as 20 bit structs. This is too much for sending over= the >>>> network regularly as part of a save. >>>> >>>> I've had some ideas on how to compress the data, but they might be >>>> crap. I don't know. >>>> >>>> I can't easily regenerate the set so thought someone who wanted to >>>> compress consumables might know the name of a good solution for sparse >>>> bitset compression. The bits are clumped around different areas of the >>>> grid, so I feel that something that leverages spatial coherence might = do >>>> well. >>>> >>>> Any leads would be highly appreciated. >>>> >>>> -- >>>> fabs(); >>>> "The fact that an opinion has been widely held is no evidence whatever >>>> that it is not utterly absurd." - Bertrand Russell >>>> >>>> >>>> ----------------------------------------------------------------------= -------- >>>> 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=3D119420431&iu=3D/4140/o= stg.clktrk >>>> _______________________________________________ >>>> GDAlgorithms-list mailing list >>>> [email protected] >>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>>> Archives: >>>> >>>> http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms= -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=3D119420431&iu=3D/4140/os= tg.clktrk >>> _______________________________________________ >>> GDAlgorithms-list mailing list >>> [email protected] >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-= list >>> >> >> >> >> -- >> fabs(); >> "The fact that an opinion has been widely held is no evidence whatever >> that it is not utterly absurd." - Bertrand Russell >> >> >> ------------------------------------------------------------------------= ------ >> 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=3D119420431&iu=3D/4140/ost= g.clktrk >> _______________________________________________ >> GDAlgorithms-list mailing list >> [email protected] >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-l= ist >> > > > -------------------------------------------------------------------------= ----- > 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=3D119420431&iu=3D/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=3Dgdalgorithms-li= st > > > > -------------------------------------------------------------------------= ----- > 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=3D119420431&iu=3D/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=3Dgdalgorithms-li= st > --=20 fabs(); "The fact that an opinion has been widely held is no evidence whatever that it is not utterly absurd." - Bertrand Russell --047d7b676f7c764f4d04eff35fc3 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">I was going to plug in the morten coded version. Code from= ryg's blog.<div><br><div><a href=3D"http://fgiesen.wordpress.com/2009/= 12/13/decoding-morton-codes/">http://fgiesen.wordpress.com/2009/12/13/decod= ing-morton-codes/</a><br> </div></div></div><div class=3D"gmail_extra"><br><br><div class=3D"gmail_qu= ote">On 14 January 2014 19:11, Chris Birke <span dir=3D"ltr"><<a href=3D= "mailto:[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"auto"><div>You might also look i= nto morton order encoding, as it is a simple and efficient locality preserv= ing way to do lossless n dimensional tree structures - this is of course be= st for applications like map data. Your mileage may vary.</div> <div><br></div><div>-Chria</div><div><br>=E1=BC=80=CF=80=E1=BD=B8 =CE=BC=CE= =B7=CF=87=CE=B1=CE=BD=E1=BF=86=CF=82=C2=A0<span>iPhone 5</span></div><div><= div class=3D"h5"><div><br>On Jan 14, 2014, at 9:01 AM, Oscar Forth <<a h= ref=3D"mailto:[email protected]" target=3D"_blank">oscar@true= harmoniccolours.co.uk</a>> wrote:<br> <br></div><blockquote type=3D"cite"><div><div dir=3D"ltr">Pretty much. =C2= =A0<div><br></div><div>The space filling curve might not be necessary but y= ou may be able to use it to keep smaller gaps between the entries which are= local to each other spatially.</div> </div><div class=3D"gmail_extra"> <br><br><div class=3D"gmail_quote">On 14 January 2014 16:52, Richard Fabian= <span dir=3D"ltr"><<a href=3D"mailto:[email protected]" target=3D"_blank= ">[email protected]</a>></span> wrote:<br><blockquote class=3D"gmail_quot= e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div dir=3D"ltr">That sounds good. Something like the JPEG VLC for the actu= al distance between entries and just store deltas on a space filling curve = should be good then.</div><div><div><div class=3D"gmail_extra"> <br><br><div class=3D"gmail_quote"> On 14 January 2014 13:11, Oscar Forth <span dir=3D"ltr"><<a href=3D"mail= to:[email protected]" target=3D"_blank">oscar@trueharmoniccol= ours.co.uk</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div dir=3D"ltr">Just a random though, so apologies if i'm talking abou= t my arse, but ... couldn't you just use something like the bit plane c= ompression from Wavelet Difference Reduction (WDR)?<div><br></div><div>A lo= t depends on your data, I appreciate, so this may not work out as any signi= ficant saving ...</div> <div><br></div><div>I wrote about the compression method in my blog a few y= ears back:</div><div><br></div><div><a href=3D"http://trueharmoniccolours.c= o.uk/Blog/?p=3D55" target=3D"_blank">http://trueharmoniccolours.co.uk/Blog/= ?p=3D55</a><br> </div> <div class=3D"gmail_extra"><br>Obviously thats in the context of a full wav= elet image compressor so you will have to just grab the part I explain in t= he link above.</div><div class=3D"gmail_extra"><br></div><div class=3D"gmai= l_extra"> Also apologies for the code formatting on my blog ... ill fix it one day ;)= </div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Oscar= </div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote"><div><div> On 14 January 2014 12:37, Richard Fabian <span dir=3D"ltr"><<a href=3D"m= ailto:[email protected]" target=3D"_blank">[email protected]</a>></span> w= rote:<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">The w= eb is full of different solutions for compressing things, but some of you h= ave probably already done this and found a really good ratio compression sc= heme that fits what I'm asking about.<div> <br></div> <div>I've got a load of entites, (4-7k) that live on a grid (1024x1024)= , and I need to persist them to a savegame which gets sent across the netwo= rk to keep the save safe. I need to compress it. I'm compressing the en= tities in the world already, ones that have been affected cost a few bytes,= but the but for the ones that don't have any changes, all I'm left= with is the coords. There are only a few that need the fatter compression,= but at the numbers I'm looking at, those "unchanged entity" = coords add up to a lot of data when storing as 20 bit structs. This is too = much for sending over the network regularly as part of a save.</div> <div><br></div><div>I've had some ideas on how to compress the data, bu= t they might be crap. I don't know.</div> <div><br></div><div>I can't easily regenerate the set so thought someon= e who wanted to compress consumables might know the name of a good solution= for sparse bitset compression. The bits are clumped around different areas= of the grid, so I feel that something that leverages spatial coherence mig= ht do well.</div> <div><br></div><div>Any leads would be highly appreciated.<span><font color= =3D"#888888"><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr">fabs(= );<div> <span style=3D"line-height:20px;font-size:14px;font-family:'Helvetica N= eue',Helvetica,Arial,sans-serif">"The fact that an opinion has bee= n widely held is no evidence whatever that it is not utterly absurd." = - Bertrand Russell</span><br> </div></div> </font></span></div></div> <br></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></blockquote></div><br></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 & 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></blockquote></div><br><br clear=3D"= all"> <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></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]" 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></div> </div></blockquote><blockquote type=3D"cite"><div><span>-------------------= -----------------------------------------------------------</span><br><span= >CenturyLink Cloud: The Leader in Enterprise Cloud Services.</span><br><spa= n>Learn Why More Businesses Are Choosing CenturyLink Cloud For</span><br> <span>Critical Workloads, Development Environments & Everything In Betw= een.</span><br><span>Get a Quote or Start a Free Trial Today. </span><br><s= pan><a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D119420431&am= p;iu=3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net= /gampad/clk?id=3D119420431&iu=3D/4140/ostg.clktrk</a></span></div> </blockquote><blockquote type=3D"cite"><div><span>_________________________= ______________________</span><br><span>GDAlgorithms-list mailing list</span= ><br><span><a href=3D"mailto:[email protected]" targe= t=3D"_blank">[email protected]</a></span><br> <span><a href=3D"https://lists.sourceforge.net/lists/listinfo/gdalgorithms-= list" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgo= rithms-list</a></span><br><span>Archives:</span><br><span><a href=3D"http:/= /sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-list" targ= et=3D"_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgda= lgorithms-list</a></span></div> </blockquote></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 & 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> --047d7b676f7c764f4d04eff35fc3-- --===============7974018517924318306== 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 --===============7974018517924318306== 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 --===============7974018517924318306==--