| --- Log opened Tue Feb 22 00:00:36 2022 |
| 00:07 | <&Reiver> | hmph |
| 00:08 | <&Reiver> | And here I was wondering if you could create a complete compression algorathm with linear time decoding (even if you do this via rigging a few presets that's fine) that would work out in the entirety to be smaller than the text strings you in fact wrote |
| 00:08 | <&Reiver> | like, in total. No library cheating. :p |
| 00:10 | | * macdjord recalls he independently reinvented run-length encoding of images back in high school, not to save space but for /speed/. |
| 00:11 | <@macdjord> | I needed to draw a specific image - the Mandelbrot set - as quickly as possible, and I found that, due to the limitations of the language I was working in (Turing, IIRC), writing colour values from an array pixel-by-pixel was relatively slow. |
| 00:12 | <&Reiver> | ha, yeah |
| 00:12 | <@macdjord> | However, I had this handy 'draw line' function, and a lot of the image involved large horizontal segments of pixels that were all the same colour... |
| 00:27 | | catalyst [catalyst@Nightstar-3j04n3.dab.02.net] has joined #code |
| 00:29 | | catalys8 [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 00:29 | | catalyst_ [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Connection closed] |
| 00:32 | | catalyst [catalyst@Nightstar-3j04n3.dab.02.net] has quit [Connection reset by peer] |
| 01:00 | <&McMartin> | OK, so |
| 01:01 | <&McMartin> | When you're being super pedantic, you charge for the decoder when working out compression ratios |
| 01:01 | <&McMartin> | And second, linear decode with no real tricks: you want to start your search with Huffman decoding |
| 01:01 | <&McMartin> | I have yet to truly grasp the secrets of doing Huffman encoding properly, but huffman decode is a basic tech and a very sneaky application of graph theory |
| 01:02 | <&McMartin> | It's a variable-bit encoding mechanism and "letters" can be arbitrary length so it is super-RLE |
| 01:02 | <&McMartin> | And decode is "walk a tree with each bit, then when you hit a leaf copy the string out and start over" which is as linear as you get |
| 01:03 | <&McMartin> | (after all, there is ultimately the cost of *writing the uncompressed data somewhere* so you will always at least be linear in *that*) |
| 01:05 | | gizmore|2 [kvirc@Nightstar-5kds8n.dip0.t-ipconnect.de] has joined #code |
| 01:08 | | gizmore [kvirc@Nightstar-30r12s.dip0.t-ipconnect.de] has quit [Ping timeout: 121 seconds] |
| 01:29 | | ErikMesoy1 [Bruker@Nightstar-dkl205.bb.online.no] has joined #code |
| 01:30 | | ErikMesoy [Bruker@Nightstar-5dnqhq.bb.online.no] has quit [Ping timeout: 121 seconds] |
| 01:35 | <&Reiver> | Huffman does scale very effectively, but it involves creating a library as you go and I was honestly wondering if it would have been beaten out by a more for-purpose encode. |
| 01:36 | <&Reiver> | I dunno. It was a dumb puzzle, but I appreciate not one that holds much interest when so much of this is a Solved Problem nowadays~ |
| 01:37 | <&McMartin> | Yeah, I'd say it's really more "this is an important enough problem that it's not really about seeing what The Old Ways Were Like as it is Having To Catch Up With Like 40 Years Of Development |
| 01:37 | <&McMartin> | Also the creating the library is for the *encode*, AIUI |
| 01:37 | <&McMartin> | For decode you are kinda handed the dictionary in advance and then you just navigate it |
| 01:51 | <&Reiver> | ... ah, beans, you're right |
| 01:51 | <&Reiver> | bah, fiiiine |
| 01:51 | <&Reiver> | I will skip doingi nteresting math on primitive encoding methods~ |
| 01:55 | <&McMartin> | If you get a handle on how to get decent dictionaries for *encoding*, let me know~ |
| 01:56 | <~Vornicus> | huffman coding is not that complicated |
| 01:57 | <~Vornicus> | even for the encode step |
| 01:57 | <&McMartin> | Yeah, it's just one of those places I've never had to dig |
| 01:57 | <&McMartin> | (similarly: actually good maze generators) |
| 01:58 | <~Vornicus> | you just pair the least common two things, repeatedly, to make the tree |
| 01:58 | <&McMartin> | The part I'm less clear on is how you decide what things are things |
| 01:59 | <~Vornicus> | oh. well, in this case you'd probably do 4-bit objects |
| 01:59 | <&Reiver> | IIRC: They always start with a 1, and every string that starts with a 1 is unique |
| 01:59 | <&McMartin> | Yeah, I suppose I should be clearer here, and say the thing I wouldn't mind learning is how you decide to build a table when you are, like |
| 01:59 | <&McMartin> | zip.exe |
| 01:59 | <&Reiver> | There is a 101 and a 1101 but there is no 1011 |
| 01:59 | <&McMartin> | and compressing text |
| 02:00 | <&Reiver> | Or whatever |
| 02:00 | <&McMartin> | So your dictionary in that case has target "words" that are variable length... |
| 02:00 | <&Reiver> | Correct |
| 02:00 | <&McMartin> | The easy part that Vorn describes is what I had to do in school, basically |
| 02:00 | <&Reiver> | I remember coding this shit by hand once to get my head around it so |
| 02:00 | <&McMartin> | Where the target "words" are fixed length and the *source* words are variable. |
| 02:01 | <&McMartin> | I recall some theorem about how the Huffman encoding is The Best You Can Do by some metric given a particular dictionary |
| 02:01 | <&Reiver> | Yeah no this is the words scale rapidly in length, you don't use the whole, uh, bitspace of each word |
| 02:01 | <&Reiver> | It fits neatly into the ... is it a log curve on that one I forget, but yeah, it's the Best General Purpose Because It Fits The Curve With No Waste |
| 02:01 | | catalys8 [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Connection closed] |
| 02:02 | <&Reiver> | However this is distinct from being The Best That Is Possible In All Circumstances So Keep Paying Attention Kids |
| 02:02 | <&McMartin> | I've been taught, in the gutter, a few transforms you can do in advance that make RLE work insanely well, so there are modes where you do that, then RLE, then Huffman-encode *that* and such |
| 02:02 | <&McMartin> | If you chain these in the right order you start getting names out like "deflate" and "bzip2" |
| 02:02 | <&Reiver> | right |
| 02:03 | <&McMartin> | Also there's a Lempel and a Ziv in there somewhere, and some patents that finally expired around when FFXIV launched |
| 02:03 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 02:03 | <&Reiver> | However it is optimal for... yeah, that's it |
| 02:04 | | catalyst is now known as jessika |
| 02:04 | <&Reiver> | It's optimal when you can build your table before you write it, and you're strictly doing symbol-by-symbol |
| 02:05 | <&Reiver> | So running runtime on something then huffman'ing it having Kept Notes As You Went means you can then compress the compression, so to speak, to, effectively, bitpack shit that would've otherwise been wasteful |
| 02:05 | <&Reiver> | I remember Adaptive hurting my head because on small examples it looks *terrible* and of course doing a larger example by hand to watch it work is time consuming |
| 02:06 | <&Reiver> | Er, Adaptive Huffman encodes |
| 02:07 | <&Reiver> | Which work around the probability issues by working them out as you go, and just accepting that the first n characters you saw may have been wrong but Keep Going and is thus kind of a glorious mess when other systems work better in that example anyway |
| 02:12 | <&McMartin> | Yeah, IIRC the specific one I want to learn is the... sliding window? Huffman encode that was made ubiquitous by PKZIP |
| 02:14 | | jessika [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Ping timeout: 121 seconds] |
| 02:19 | <&Reiver> | oh, yeah |
| 03:11 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 03:25 | | Degi_ [Degi@Nightstar-506vng.pool.telefonica.de] has joined #code |
| 03:28 | | Degi [Degi@Nightstar-7cpqg6.pool.telefonica.de] has quit [Ping timeout: 121 seconds] |
| 03:28 | | Degi_ is now known as Degi |
| 04:57 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 05:18 | | himi [sjjf@Nightstar-1drtbs.anu.edu.au] has quit [Ping timeout: 121 seconds] |
| 05:24 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has joined #code |
| 05:24 | | mode/#code [+ao ToxicFrog ToxicFrog] by ChanServ |
| 06:35 | | Kindamoody is now known as Kindamoody|afk |
| 07:25 | | * McMartin ponders his blog stats |
| 07:25 | <&McMartin> | Apparently another wave of people suddenly very interested in loading programs into the ZX81 |
| 07:25 | <&McMartin> | I have no idea how this became my third-most-popular article |
| 07:34 | | McMartin [mcmartin@Nightstar-i80eaa.ca.comcast.net] has quit [[NS] Quit: reboot] |
| 07:41 | | McMartin [mcmartin@Nightstar-i80eaa.ca.comcast.net] has joined #code |
| 07:41 | | mode/#code [+ao McMartin McMartin] by ChanServ |
| 07:42 | <&McMartin> | OK, I've written up the graphics creation pipeline. https://bumbershootsoft.wordpress.com/2022/02/22/lights-out-nes-content-creation/ |
| 07:43 | <&McMartin> | Also featured: the Official Bumbershoot BAD-IDEAS-O-METER (tm) |
| 07:44 | | himi [sjjf@Nightstar-v37cpe.internode.on.net] has joined #code |
| 07:44 | | mode/#code [+o himi] by ChanServ |
| 08:19 | | gizmore|2 [kvirc@Nightstar-5kds8n.dip0.t-ipconnect.de] has quit [Connection closed] |
| 08:20 | | gizmore [kvirc@Nightstar-5kds8n.dip0.t-ipconnect.de] has joined #code |
| 08:32 | | macdjord is now known as macdjord|slep |
| 09:00 | | abudhabi__ [abudhabi@Nightstar-2ifl2t.adsl.tpnet.pl] has joined #code |
| 09:01 | | abudhabi_ [abudhabi@Nightstar-2q9glf.adsl.tpnet.pl] has quit [Ping timeout: 121 seconds] |
| 14:43 | | macdjord|slep is now known as macdjord |
| 14:55 | | catalyst_ [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 14:55 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Connection closed] |
| 16:05 | | Vorntastic [uid293981@Nightstar-phvupn.irccloud.com] has joined #code |
| 16:05 | | mode/#code [+qo Vorntastic Vorntastic] by ChanServ |
| 17:02 | | Emmy [Emmy@Nightstar-l49opt.fixed.kpn.net] has joined #code |
| 18:21 | | Netsplit Krikkit.Nightstar.Net <-> Deepthought.Nightstar.Net quits: @celticminstrel, @macdjord, Degi, @Syloq, gizmore, ErikMesoy1, @Kindamoody|afk, @JustBob |
| 18:22 | | Netsplit over, joins: @celticminstrel, Degi, ErikMesoy1, @macdjord, gizmore, @Syloq, @JustBob, @Kindamoody|afk |
| 18:24 | | Vorntastic [uid293981@Nightstar-phvupn.irccloud.com] has quit [[NS] Quit: Connection closed for inactivity] |
| 19:51 | | Kindamoody|afk is now known as Kindamoody |
| 20:00 | < abudhabi__> | WTF. Youtube has a DOWNLOAD button now? |
| 20:02 | <&McMartin> | Where are you seeing this? |
| 20:02 | <&[R]> | If you click it it'll say that you need to be signed up for Premium |
| 20:02 | <&[R]> | It's effectively an ad for Premium |
| 20:06 | <&McMartin> | Huh, don't even see the pretend option here |
| 20:07 | <&[R]> | It's probably in A/B testing |
| 20:20 | <&McMartin> | Looking at their page, it isn't even that; it sounds like they self-destruct after awhile |
| 20:21 | <&[R]> | That's how it used to work when that option was free, yeah |
| 20:34 | <&Reiver> | ... how do you self destruct a video |
| 20:34 | <&Reiver> | Or is this "We dump it in your video cache for 'watch later' |
| 20:35 | <&[R]> | This was only an option available through the app |
| 20:35 | <&[R]> | Thus the app has full control over the file |
| 20:37 | < Mahal> | Yeah, it's a cache-to-device download not a 'real' download |
| 20:37 | < Mahal> | same as netflix, disney+, et al |
| 20:38 | <&Reiver> | right |
| 20:38 | <&Reiver> | Not an unwelcome technology tbh |
| 20:38 | <&Reiver> | Could load up on Drachnifels for my commutes if/when I ever did them again |
| 20:39 | <&McMartin> | Yeah, that's clearly the use case |
| 20:39 | <&Reiver> | (He does hour-long Q&A sessions once a week, and a like 6-hour Q&A once a month. He has a very consistent vocal style and excellent sound quality, so hearing him over traffic is no object and each question is a few minutes long so you can stop at a Useful Spot when you arrive at your destination; It makes for pleasant commuting chatter.) |
| 20:40 | <&Reiver> | (I have found audiobooks and Full Length Podcasts work less great there because I'm inevitably having to halt the thing In The Middle Of Something Interesting and have to pick up the thread later, /or/ the thing was Five Minutes Too Short and I had to drive in agonising silence for the last portion of the trip~) |
| 20:47 | | himi [sjjf@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 21:27 | | Pink [Pink@Nightstar-oetkb4.ph.cox.net] has joined #code |
| 22:48 | | Kindamoody is now known as Kindamoody[zZz] |
| 23:07 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Connection closed] |
| 23:21 | | himi [sjjf@Nightstar-1drtbs.anu.edu.au] has joined #code |
| 23:21 | | mode/#code [+o himi] by ChanServ |
| 23:26 | | catalyst_ is now known as jessika |
| --- Log closed Wed Feb 23 00:00:38 2022 |