Re: sparse bitset compression
Oscar Forth <[email protected]> Tue, 14 Jan 2014 17:01:07 +0000
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <CACzpBswE2+g=de5nA+N=-wZTaah7X02o+U3vLotgQz=6==yQ-Q@mail.gmail.com> |
--===============7260063380399777665== Content-Type: multipart/alternative; boundary=001a1136491a727be004eff12372 --001a1136491a727be004eff12372 Content-Type: text/plain; charset=ISO-8859-1 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]>wrote: > >> 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)? >> >> 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=55 >> >> 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. >> >> Also apologies for the code formatting on my blog ... ill fix it one day >> ;) >> >> Oscar >> >> 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 >>> compression scheme that fits what I'm asking about. >>> >>> 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 >>> keep the save safe. I need to compress it. I'm compressing the entities 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. >>> >>> 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=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 > > > ------------------------------------------------------------------------------ > 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 > --001a1136491a727be004eff12372 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Pretty much. =A0<div><br></div><div>The space filling curv= e 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.</div></div><d= iv 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 class=3D"HOEnZb"><div class=3D"h5"><div clas= s=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]">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></div> --001a1136491a727be004eff12372-- --===============7260063380399777665== 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 --===============7260063380399777665== 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 --===============7260063380399777665==--