Re: sparse bitset compression
Richard Fabian <[email protected]> Tue, 14 Jan 2014 16:52:06 +0000
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <CACot5u1b-UrdMFpGA7h4hhszO0rVk==pdaGq8b=j4m95zgxPxw@mail.gmail.com> |
--===============0046133262048313275== Content-Type: multipart/alternative; boundary=047d7b5d94f5fc3ff104eff104ee --047d7b5d94f5fc3ff104eff104ee Content-Type: text/plain; charset=ISO-8859-1 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 --047d7b5d94f5fc3ff104eff104ee Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <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"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 c= lass=3D"h5"> 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 class=3D"h5"><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 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]">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> --047d7b5d94f5fc3ff104eff104ee-- --===============0046133262048313275== 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 --===============0046133262048313275== 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 --===============0046133262048313275==--