Re: sparse bitset compression
Chris Birke <[email protected]> Tue, 14 Jan 2014 11:11:31 -0800
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <[email protected]> |
--===============1946736517027598347== Content-Type: multipart/alternative; boundary=Apple-Mail-338FB1AC-91EE-4785-B315-D5BAFF3F03C9 Content-Transfer-Encoding: 7bit --Apple-Mail-338FB1AC-91EE-4785-B315-D5BAFF3F03C9 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable You might also look into morton order encoding, as it is a simple and effici= ent locality preserving way to do lossless n dimensional tree structures - t= his 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 iPhon= e 5 > On Jan 14, 2014, at 9:01 AM, Oscar Forth <[email protected]>= wrote: >=20 > Pretty much. =20 >=20 > The space filling curve might not be necessary but you may be able to use i= t to keep smaller gaps between the entries which are local to each other spa= tially. >=20 >=20 >> On 14 January 2014 16:52, Richard Fabian <[email protected]> wrote: >> That sounds good. Something like the JPEG VLC for the actual distance bet= ween entries and just store deltas on a space filling curve should be good t= hen. >>=20 >>=20 >>> 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 Wavelet= Difference Reduction (WDR)? >>>=20 >>> A lot depends on your data, I appreciate, so this may not work out as an= y significant saving ... >>>=20 >>> I wrote about the compression method in my blog a few years back: >>>=20 >>> http://trueharmoniccolours.co.uk/Blog/?p=3D55 >>>=20 >>> Obviously thats in the context of a full wavelet image compressor so you= will have to just grab the part I explain in the link above. >>>=20 >>> Also apologies for the code formatting on my blog ... ill fix it one day= ;) >>>=20 >>> Oscar >>>=20 >>>> On 14 January 2014 12:37, Richard Fabian <[email protected]> wrote: >>>> The web is full of different solutions for compressing things, but some= of you have probably already done this and found a really good ratio compre= ssion scheme that fits what I'm asking about. >>>>=20 >>>> 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 network to k= eep the save safe. I need to compress it. I'm compressing the entities in th= e world already, ones that have been affected cost a few bytes, but the but f= or the ones that don't have any changes, all I'm left with is the coords. Th= ere are only a few that need the fatter compression, but at the numbers I'm l= ooking at, those "unchanged entity" coords add up to a lot of data when stor= ing as 20 bit structs. This is too much for sending over the network regular= ly as part of a save. >>>>=20 >>>> I've had some ideas on how to compress the data, but they might be crap= . I don't know. >>>>=20 >>>> I can't easily regenerate the set so thought someone who wanted to comp= ress consumables might know the name of a good solution for sparse bitset co= mpression. The bits are clumped around different areas of the grid, so I fee= l that something that leverages spatial coherence might do well. >>>>=20 >>>> Any leads would be highly appreciated. >>>>=20 >>>> --=20 >>>> fabs(); >>>> "The fact that an opinion has been widely held is no evidence whatever t= hat it is not utterly absurd." - Bertrand Russell >>>>=20 >>>> -----------------------------------------------------------------------= ------- >>>> 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 >>>=20 >>>=20 >>> ------------------------------------------------------------------------= ------ >>> 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 >>=20 >>=20 >>=20 >> --=20 >> fabs(); >> "The fact that an opinion has been widely held is no evidence whatever th= at it is not utterly absurd." - Bertrand Russell >>=20 >> -------------------------------------------------------------------------= ----- >> 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 > --------------------------------------------------------------------------= ---- > 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.=20 > 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-lis= t --Apple-Mail-338FB1AC-91EE-4785-B315-D5BAFF3F03C9 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable <html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=3D= utf-8"></head><body dir=3D"auto"><div>You might also look into morton order e= ncoding, as it is a simple and efficient locality preserving way to do lossl= ess n dimensional tree structures - this is of course best for applications l= ike map data. Your mileage may vary.</div><div><br></div><div>-Chria</div><d= iv><br>=E1=BC=80=CF=80=E1=BD=B8 =CE=BC=CE=B7=CF=87=CE=B1=CE=BD=E1=BF=86=CF=82= <span class=3D"Apple-style-span" style=3D"-webkit-tap-highlight-color:= rgba(26, 26, 26, 0.296875); -webkit-composition-fill-color: rgba(175, 192, 2= 27, 0.230469); -webkit-composition-frame-color: rgba(77, 128, 180, 0.230469)= ; ">iPhone 5</span></div><div><br>On Jan 14, 2014, at 9:01 AM, Oscar Forth &= lt;<a href=3D"mailto:[email protected]">oscar@trueharmoniccolo= urs.co.uk</a>> wrote:<br><br></div><blockquote type=3D"cite"><div><div di= r=3D"ltr">Pretty much. <div><br></div><div>The space filling curve mig= ht not be necessary but you may be able to use it to keep smaller gaps betwe= en the entries which are local to each other spatially.</div></div><div clas= s=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">r= [email protected]</a>></span> wrote:<br><blockquote class=3D"gmail_quote" s= tyle=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 actua= l distance between entries and just store deltas on a space filling curve sh= ould be good then.</div><div class=3D"HOEnZb"><div class=3D"h5"><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"mailt= o:[email protected]" target=3D"_blank">oscar@trueharmoniccolou= rs.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 about my a= rse, but ... couldn't you just use something like the bit plane compression f= rom Wavelet Difference Reduction (WDR)?<div><br></div><div>A lot depends on y= our data, I appreciate, so this may not work out as any significant saving .= ..</div> <div><br></div><div>I wrote about the compression method in my blog a few ye= ars back:</div><div><br></div><div><a href=3D"http://trueharmoniccolours.co.= uk/Blog/?p=3D55" target=3D"_blank">http://trueharmoniccolours.co.uk/Blog/?p=3D= 55</a><br> </div> <div class=3D"gmail_extra"><br>Obviously thats in the context of a full wave= let image compressor so you will have to just grab the part I explain in the= link above.</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_e= xtra"> 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"ma= ilto:[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;bor= der-left:1px #ccc solid;padding-left:1ex"><div><div><div dir=3D"ltr">The web= is full of different solutions for compressing things, but some of you have= probably already done this and found a really good ratio compression scheme= 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 network to k= eep the save safe. I need to compress it. I'm compressing the entities in th= e world already, ones that have been affected cost a few bytes, but the but f= or the ones that don't have any changes, all I'm left with is the coords. Th= ere are only a few that need the fatter compression, but at the numbers I'm l= ooking at, those "unchanged entity" coords add up to a lot of data when stor= ing as 20 bit structs. This is too much for sending over the network regular= ly as part of a save.</div> <div><br></div><div>I've had some ideas on how to compress the data, but the= y might be crap. I don't know.</div> <div><br></div><div>I can't easily regenerate the set so thought someone who= wanted to compress consumables might know the name of a good solution for s= parse bitset compression. The bits are clumped around different areas of the= grid, so I feel that something that leverages spatial coherence might do we= ll.</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();<d= iv> <span style=3D"line-height:20px;font-size:14px;font-family:'Helvetica Neue',= Helvetica,Arial,sans-serif">"The fact that an opinion has been widely held i= s no evidence whatever that it is not utterly absurd." - Bertrand Russell</s= pan><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.<br= > 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/gampad/= 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" t= arget=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-l= ist</a><br> Archives:<br> <a href=3D"http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgor= ithms-list" target=3D"_blank">http://sourceforge.net/mailarchive/forum.php?f= orum_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.<br= > 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/gampad/= 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" t= arget=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-l= ist</a><br> Archives:<br> <a href=3D"http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgor= ithms-list" target=3D"_blank">http://sourceforge.net/mailarchive/forum.php?f= orum_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-heigh= t:20px;font-size:14px;font-family:'Helvetica Neue',Helvetica,Arial,sans-seri= f">"The fact that an opinion has been widely held is no evidence whatever th= at 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.<br= > 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/gampad/= clk?id=3D119420431&iu=3D/4140/ostg.clktrk</a><br>_______________________= ________________________<br> GDAlgorithms-list mailing list<br> <a href=3D"mailto:[email protected]">GDAlgorithms-list= @lists.sourceforge.net</a><br> <a href=3D"https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" t= arget=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-l= ist</a><br> Archives:<br> <a href=3D"http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgor= ithms-list" target=3D"_blank">http://sourceforge.net/mailarchive/forum.php?f= orum_name=3Dgdalgorithms-list</a><br></blockquote></div><br></div> </div></blockquote><blockquote type=3D"cite"><div><span>--------------------= ----------------------------------------------------------</span><br><span>C= enturyLink Cloud: The Leader in Enterprise Cloud Services.</span><br><span>L= earn Why More Businesses Are Choosing CenturyLink Cloud For</span><br><span>= Critical Workloads, Development Environments & Everything In Between.</s= pan><br><span>Get a Quote or Start a Free Trial Today. </span><br><span><a h= ref=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D119420431&iu=3D/4= 140/ostg.clktrk">http://pubads.g.doubleclick.net/gampad/clk?id=3D119420431&a= mp;iu=3D/4140/ostg.clktrk</a></span></div></blockquote><blockquote type=3D"c= ite"><div><span>_______________________________________________</span><br><s= pan>GDAlgorithms-list mailing list</span><br><span><a href=3D"mailto:GDAlgor= [email protected]">[email protected]</a= ></span><br><span><a href=3D"https://lists.sourceforge.net/lists/listinfo/gd= algorithms-list">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-l= ist</a></span><br><span>Archives:</span><br><span><a href=3D"http://sourcefo= rge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-list">http://sourcef= orge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-list</a></span></di= v></blockquote></body></html>= --Apple-Mail-338FB1AC-91EE-4785-B315-D5BAFF3F03C9-- --===============1946736517027598347== 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 --===============1946736517027598347== 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 --===============1946736517027598347==--