[HN Gopher] Game Boy Wordle clone: How to compress 12972 five-le...
___________________________________________________________________
Game Boy Wordle clone: How to compress 12972 five-letter words to
17871 bytes
Author : cubefox
Score : 297 points
Date : 2022-02-20 01:41 UTC (21 hours ago)
(HTM) web link (alexanderpruss.blogspot.com)
(TXT) w3m dump (alexanderpruss.blogspot.com)
| hinkley wrote:
| There's a technique whose name I can't remember, where you take a
| bunch of words and you produce a much shorter string that has all
| of the input words in it but overlapping, where the beginning of
| one word is the end of the previous. Functionally it's like a 1
| dimensional word search, and you store pointers into it for all
| of the individual words.
|
| Anybody know what I'm thinking of?
| ProjectBarks wrote:
| I think you are thinking of a trie
| hinkley wrote:
| No, not a trie.
|
| After throwing more words at the Google Wall, it finally
| allowed that what I'm thinking of is the Shortest Superstring
| Problem.
| rasz wrote:
| https://en.wikipedia.org/wiki/De_Bruijn_sequence
| hinkley wrote:
| Interesting. Here we don't care about duplicates though,
| except that they may indicate we had yet to arrive at the
| optimal solution.
|
| But it's possible that you could accidentally make duplicates
| of one word by pairing others. For a single copy you can omit
| that word. But if it appears multiple times that represents a
| compression opportunity that a shuffle to avoid it might
| destroy.
| alisonkisk wrote:
| hombre_fatal wrote:
| You can see a trie in action used to build a better regex
| expression: https://www.npmjs.com/package/trie-regex
| [deleted]
| danieldk wrote:
| You can probably get better compression by storing the words in
| a minimized acyclic finite state automaton, since then e.g.
| shared prefixes and suffixes between words are compressed.
| Finite state automata can be stored as compact contiguous
| tables and you can use some of the same tricks as in the
| article to compress characters on transitions.
|
| The linked post reaches 3.6 bits per byte. E.g. [1] uses finite
| state automata to reach 1.1 bits per byte for a Scrabble word
| list and 1.5 bits per byte for an English word list. Both word
| lists are probably more difficult, since they contain words of
| varying lengths and long words have less sharing in their
| pre/suffixes.
|
| [1]
| https://www.cs.put.poznan.pl/dweiss/site/publications/downlo...
| quicktwo wrote:
| I think you might have miscalculated bits per bytes here?
|
| 8 * 17,763/64,860 = 2.19
|
| Also, I attempted to implement this as described in this
| paper (variable length encoding the letters and the offsets,
| utilized L, and dropped F entirely because all words are the
| same length, N didn't make a big difference).
|
| I achieved a naive size of 20,560 bytes, which I didn't have
| confidence implementing more advanced techniques outlined in
| the paper would get the size down sufficiently to compete
| with using a trie+Huffman representation (15,599 bytes,
| https://github.com/adamcw/wordle-trie-packing#all-words).
|
| 8 * 15,599/64,860 = 1.92 bits per byte.
| hinkley wrote:
| 5.5 bits per word is pretty good. 18 bits per word leaves
| room to be undercut by a lucky break with a Bloom Filter.
| danieldk wrote:
| But not for Wordle, since a Bloom filter cannot enumerate
| items? (So, you can't tell which letters were correct.)
| hinkley wrote:
| What you'd need is a Bloom filter with no false positives
| in the 26^5 keyspace, and then you'd have to guess random
| words on startup until you got a hit, which on average
| would take you 917 guesses.
|
| Which is terrible but still probably faster than the
| algorithm that the linked article is using, since finding
| the offset of the kth worth takes O(k) time, and there
| are 12948 (I still haven't found the mythical 12972 word
| list).
| ars wrote:
| Are there general purpose compression tools that preserve the
| data, but not the ordering?
|
| [One of] the reasons gzip does worse is it also preserves the
| order of input.
| manx wrote:
| That's what I was thinking, too. Are compression algorithms for
| Sets a thing? Might be useful for compressing JSON, because the
| key-value pairs are a Set.
| haunter wrote:
| Good job!
|
| Works perfectly on the 3DS (mine is a New 3DS XL) with the NSUI!
| https://i.imgur.com/TjGYsKC.jpeg
| zackboe wrote:
| My flashcart's GB emulator doesn't have a color palette that
| matched perfectly, but works well enough!
| https://i.imgur.com/ePtY5Jf.jpg
|
| Found a GBC implementation as well: https://github.com/bbbbbr/gb-
| wordle
| bbbbbr wrote:
| The linked GBC version is my fork with some improvements (and
| more in the works).
|
| The current published release uses a similar compression
| approach by zeta_two, but in current builds I've switched to
| the compression by arpruss since total data + decompression
| code size is now a couple hundred bytes smaller.
|
| I did some profiling and code size measurements before
| switching over. https://github.com/bbbbbr/gb-
| wordle/blob/compress_arpruss/wo...
|
| Speed (and code size somewhat) have improved more since then.
| a-dub wrote:
| i wonder if the letter frequencies across the corpora could
| justify variable length character encoding.
| coumbaya wrote:
| Does anybody know how much words the Lingo/Motus GB game had ?
| Can't find the info online. Might be interesting toncompare to
| the original 1994 version (if it can be decompiled ?!).
| ant6n wrote:
| In '94, it was possible to have multi-MB cartridges. They used
| bank switching to access all the data.
| dietrichepp wrote:
| I got nerd sniped and compressed it to under 28K, which was good
| enough for the goal of fitting it in a 32K NROM cartridge for the
| NES. On the NES, you don't need to do better than that, because
| you get a separate 8K for graphics, and 4K is plenty of space to
| fit the code for your Wordle clone.
|
| https://www.moria.us/blog/2022/01/dictionary-compression
|
| The annoying part is that the NES only gives you four background
| palettes, and you are constrained to use all four of those to
| color your words.
| operator-name wrote:
| Both of these ideas remind me of tries and radix trees.
| mzs wrote:
| Nice! Do you have a repo somewhere?
| tragomaskhalos wrote:
| There was a pretty decent Scrabble available for the ZX Spectrum
| - around 41k for vocab + code. I always imagined that must have
| used a fairly ingenious compression mechanism for its dictionary,
| especially given the types of fairly open searching it would need
| to do.
| nathell wrote:
| There's a similar algorithm for indexing words in text
| collections (I know it from the 'Managing Gigabytes' book).
|
| Say you want to store the information that the word 'algorithm'
| occurs in documents 42, 2718 and 3141. That's a sorted list, so
| as the author notes, you can just store the differences (42,
| 2676, 423). Those differences can still be arbitrarily large, but
| if there are many documents, you can expect most differences to
| be small.
|
| The trick is to store the numbers not as fixed-bit-size integers,
| but using a variable-length encoding. The algorithm stipulates
| using a Golomb code with the parameter b = ceil(N / n * ln(2)),
| where N is the number of documents in total, n is the number of
| documents containing our word, and ln is the natural logarithm.
|
| For our example, assuming 5000 documents in total, this gives N =
| 5000, n = 3, b = 1156, and our index entry is
| 10000101010001010110110010110100111, for a total of 35 bits.
| justinlloyd wrote:
| I love little compression hacks like the one given in the
| article.
|
| I created a word search game way back in late 1978/early 1979 4KB
| of RAM. I had about 2KB for storing the word database. And I
| recall I had about 2,500 words. Which I had to type in by hand.
|
| I used the 26 tables of words trick too, to drop the first
| letter. I also treated each word being made up of 32 symbols. I
| called them letters, but they didn't represent individual letters
| necessarily.
|
| Edit 36 minutes after writing my original comment: Having just
| checked my notes from December 24th 1978, I need to correct
| myself and say it was 38 symbols. Though I seem to recall I
| actually got it down to 32 symbols. I need to keep looking
| through my notes to refresh my brain on the solution.
|
| A word might end in "ING" so that was considered a single
| letter/symbol. Words were between four and seven letters long.
|
| Most words took up two bytes, some only took up a single byte,
| only a few took up three bytes, maybe a few dozen took up four
| bytes. And I judiciously pruned the database to minimize the
| words that took up three or four bytes so that I didn't have too
| many of them. I also packed the bits, so that there was no gaps
| between words.
|
| And it was all written in 6502 assembly, originally for the CBM
| PET, and later for the Acorn Atom.
|
| I was 11 years old and so proud of myself for such cleverness. I
| still have my notes and scribblings, including the digitised
| versions from all those years back.
|
| Later, when I wrote a much more complex Bookworm type of game I
| had to take a word list that was about 8MB long, uncompressed,
| which would just barely fit on the hard drive, and turned it into
| a trie, which brought it down to just a few dozen kilobytes,
| which handily fit on a SS/SD 100KB 5+1/4" floppy.
| para_parolu wrote:
| I don't know what amazes me more: your engineering solution or
| the fact you was able to find notes dated December 24th 1978
| iforgotpassword wrote:
| Man, at 11 my programs mainly consisted of INPUT, PRINT and
| GOTO, which I wrote on my uncle's brand new IBM XT.
| rootsudo wrote:
| My programs at 11 were just Visual Basic 6 for an IE
| scrapper/clicker and making HTML websites in Dreamweaver 6.
|
| Not sure why the 6 was so popular for many programs then. It
| was for sure Photoshop 7 era.
| [deleted]
| slim109ya wrote:
| Yeah, me too. Mainly D&D character generators.
| justinlloyd wrote:
| D&D character generators were fun to write. And remember
| those name generators? And you could make planet name &
| planet environment generators, and then solar system
| generators for Traveller. I threw together a really bad
| dungeon map designer thing when I bought once of the
| earliest mice you could get, with the roller ball inside
| the mouse that you had to take out and clean.
| justinlloyd wrote:
| It doesn't matter how we all started, or how fast we got
| here, we're here now, in the same place, the adventure only
| stops, when you don't want to learn new things.
| totetsu wrote:
| Looks like you can try it out on this webassembly Gameboy
| emulator https://wasmboy.app/
| Animats wrote:
| I once came across a calculator-like device that had some version
| of a Bible stored in it. But not very well. It clearly had a
| dictionary with the text stored by word number, because some of
| the longer words were off by one word in the dictionary. This
| produced some strange texts.
| nicoco wrote:
| I think that in this case, the original text is rather strange
| to start with.
| nitrogen wrote:
| When I was a kid my parents had some bible (plus other books)
| software for their PC XT that came on dozens of 360K floppies
| and filled most of the 20MB hdd. What impressed me most was the
| search feature, and I've never seen anything like it since. You
| could search for a word within N words or N verses of another
| word, for example. I always wondered what indexing structures
| allowed that on an 8MHz 8088.
| cosmiccatnap wrote:
| charcircuit wrote:
| Can we compresses further by optimizing for only testing set
| membership?
| hinkley wrote:
| There is probably a bloom filter that covers all 26*5
| possibilities with no false positives but that's somewhere over
| 10 bits per element or 16215 bytes not counting the encoder.
|
| Might be a perfect hash waiting in there somewhere.
| kqr wrote:
| Related but not the same: does anyone have information on how the
| old T9 pre-smartphone system stored its compressed and fast
| dictionaries? I remember reading about it a long time ago but
| can't find it now.
|
| That system used some sort of lossy compression that created
| artifacts like fake words that don't exist but look enough like
| real words from the dictionary's point of view that they can be
| generated.
|
| I find it fascinating.
| hinkley wrote:
| I haven't done any noodling with compression in some time and I'm
| tempted to sit down and try this. But I think he must be using a
| different list than I can find because the numbers don't quite
| add up.
|
| Any time you are tasks with crushing the living daylights out of
| an unordered list, always, always look at suffix sorting as an
| option. It might not work out as useful, but it's frequently
| worth the cost of checking.
|
| I will say that given that a delta encoding was settled on,
| bitpacking the words first is probably a mistake, and
| multiplication should have been used instead. For instance using
| multiplication you can store the words in 24 bits without
| chopping off the first character and using pointers to them. That
| may seem a small difference but it makes the deltas he's looking
| at narrower. So instead of choosing 8 words in 8 bytes versus 10
| words in 8 bytes, it could be 8 vs 11, possibly 12.
| hinkley wrote:
| It looks like the reliance on 5 bits per character versus using
| 26*5 is that a lot more of his deltas get an extra character.
|
| He is encoding 7 bits per byte, so there are about 172 words
| that spill over into the next byte due to this.
|
| With 5 bits per letter, if the second to last character shifts
| by more than 4, then it automatically spills over. With 26, it
| also depends on how much the last letter also varies.
| grogers wrote:
| Once you have the delta encoding scheme, do you actually gain
| anything by splitting into 26 lists by first letter? It seems
| like the wrapping delta from a->b, b->c, etc would take similar
| space as the 2 byte pointer in the table, but simplify the code.
| owisd wrote:
| Saves you the CPU cycles of having to step through the entire
| list when the word is zebra.
| tyingq wrote:
| There was as similar discussion about Barclay's bank, and a list
| of 74,000 numbers:
|
| https://shkspr.mobi/blog/2021/05/the-74000-numbers-of-barcla...
|
| I tried a similar scheme of sorting the list and storing the
| delta of the previous number:
|
| https://news.ycombinator.com/item?id=28348965
| willis936 wrote:
| >The Answers could be stored as a bitmap of length 12972, which
| would be 1622 bytes. But this would make the code for generating
| a random word more complicated and slower.
|
| You could run RLE on that as well for a decent storage savings.
|
| Another thought: you could order the list of words such that the
| first 1622 words are answers. That way you don't need to store
| the answer list and checking is as fast as comparing the value of
| a memory address. This would probably hurt the differential
| coding performance though.
| quicktwo wrote:
| I was thinking that it's probably not quite sparse enough to
| benefit from RLE as-is, since the number of bits you'd need for
| your lengths would outstrip the length of your run. If any run
| can be more than 128 words, then you'd need at least 8 bits for
| the run, making it only beneficial for runs of longer than
| that.
|
| An alternative would be to make 0 mean five zeros (or some
| other N) and then if you hit a 1, it means the next 5 bits are
| to be interpreted as-is. This reduces all 5 length 0s to 1 bit,
| while only adding 1 bit whenever there is a bit. At worst this
| introduces 1 extra bit per answer. The answer to non-answer
| ratio is about 5 to 1, so this should definitely save space
| while also having a trivial decoding algorithm.
| justinlloyd wrote:
| Probably not suitable for direct RLE as you say, but if you
| looked over the data I suspect you might find that a stepped
| RLE, where you interleave two or more RLEs could provide a
| savings. You do of course need a cache to decompress parts of
| the intervleaved RLE'd data into.
| quicktwo wrote:
| You can get down to 15,559 bytes by combining a trie with Huffman
| coding: https://github.com/adamcw/wordle-trie-packing
|
| However, this doesn't beat general Brotli encoding of a ASCII
| trie representation, which gets down to 14,180 bytes (but needs
| an experience decoder), but goes to show general purpose
| compression is still really really good these days.
| steventhedev wrote:
| brotli on the raw word list gives 17194 bytes. gzip gives
| 32352.
|
| A lot can be done in 3014 bytes, but what's the difference in
| code size for the ascii trie vs. a flat list/gzip/brotli?
| quicktwo wrote:
| A trie representation physically removes letters from the
| dataset. Leaving it in ASCII means that it still leaves
| enough information behind that can be compressed well (a trie
| only exploits shared prefixes, not suffixes).
| lifthrasiir wrote:
| Roadroller [1] is probably a borderline general purpose
| compression algorithm, and with some automatic parameter tuning
| it results in 12,170 bytes estimated, at the expense of a lot
| of memory. "Estimated" because the algorithm was originally
| meant to be recompresssed in a ZIP file, so it doesn't bother
| to generate the smallest JS file in terms of uncompressed size
| (yet). But that estimation does include the decoder size so it
| is a good estimate for the Kolmogorov complexity of the
| generated code though.
|
| [1] https://lifthrasiir.github.io/roadroller/ (the exact
| parameters: golf.horse dataset; input mode text; action write
| to document; # contexts 12 with
| 12,15,49,50,70,79,96,97,131,154,292,353; pollute the global
| scope; max memory usage 150 MB; precision 16; learning rate
| 1333; model max count 11; model base divisor 14; dynamic model
| flags -1; # abbreviations 64)
| notpushkin wrote:
| Huffman coding was the first thing that jumped into my mind,
| too. Reminds me of the time we implemented a subset of bzip2 on
| a CS class in highschool.
| Syzygies wrote:
| Arithmetic coding is a drop-in replacement for Huffman coding
| that saves binary roundoff. It's less known because it was
| patented, and the (short) code to implement requires optimizing
| a tricky 1.0000 versus 0.9999 issue (in binary).
|
| The usual application involves letter frequencies without
| context. Rather than a trie for deterministic context, one
| could in far less space compute a hidden Markov chain of small
| but effective dimension, to generate the probabilities for
| arithmetic coding.
| quicktwo wrote:
| Thanks, I'll look into it. This case is interesting though,
| because the Gameboy doesn't even have native mul/div
| operators, so I suspect that Huffman coding is as fancy as
| you're going to get while still having a small and efficient
| decoder that isn't taking up more space than its saving.
| [deleted]
| u2077 wrote:
| For anyone playing, the dark green letters are correct and the
| lighter green letters are in the wrong spot. Took me 4 tries
| before I figured that out.
| ecf wrote:
| Does anyone know of a HN client that supports keyboard blocking?
| I really don't understand HN's obsession with this game.
| indigodaddy wrote:
| Bug? See screenshot. My 5th guess shouldn't have gone down like
| that for a conventional Wordle clone.
|
| https://ibb.co/93CdVWv
| throwanem wrote:
| Looks like maybe a bug in highlighting multiple occurrences of
| a letter in the same word, yeah.
| castratikron wrote:
| Black is right letter right spot. Green is right letter wrong
| spot.
| indigodaddy wrote:
| Oh my fault.. assumed the color scheme was the same:
| PickledHotdog wrote:
| Ahh thanks for this. Found it super confusing!
| [deleted]
| corruptio wrote:
| oo oo, idea... trying to implement it now:
|
| With 5 bits per letter, you have 6 symbols left over. We can use
| those to represent alternate pairs like "A or E", so you can
| encode BANDS and BENDS at the same time. Looks like if you pick
| the 6 highest frequency replacements for each starting letter,
| you can reduce the full word list size by ~2k words.
|
| A naive lookup table for the replacements is 26 * 2 * 6 = 312
| bytes.
|
| edit: oops double counted the reduction
| justinlloyd wrote:
| Hmmm... sounds familiar https://justinlloyd.li/blog/word-
| search-game-part-two/
|
| Many times you don't even need to store the individual letters,
| just the pairings, and if you are permitted to prune out
| troublesome words from your dictionary, all the better.
| hinkley wrote:
| Since delta encoding is applied after this step, it's probably
| better to just use 26^5 instead of trying to pack extra things
| into those bits.
| corruptio wrote:
| oook did some experiments... just counting the size of the
| delta streams: 17346B for 26^4 and 16852B for 32^4 (as
| described above)
|
| interestingly, the sweet spot is a mix at 30^4 at 16797B
| lucb1e wrote:
| I've noticed in the past (trying to optimize traffic for a game
| with delta compression, variable-length integers, ...) that it's
| really hard to beat good compression with manual tricks.
|
| Original word list: https://raw.githubusercontent.com/arpruss/gb-
| fiver/main/comp... $ <full.txt wc # "word
| count" #lines, words, bytes 12973 12972
| 77833 $ calc 77833-12973 # bytes minus newlines
| 64860 # matches the article, to confirm I got the right input
| data $ <full.txt xz -9 | wc -c 15412
|
| 2000 bytes smaller without any optimizations (this even includes
| the newlines), though now I guess the question is what the size
| of the xz decompressor is since a few KB actually matter (not
| like on a regular computer).
|
| For some reason bzip2 gets it only to 36K, even worse than gzip
| (32K) and zstd (29K).
|
| Update: Counter-intuitively, stripping the newlines (... | tr -d
| \\\n | ...) results in a _higher_ compressed size with xz. It 's
| surprisingly hard to find a minimal xz decompressor, it doesn't
| seem as though anyone bothers with this stuff. The Hutter Prize
| includes the decompressor so that was my first stop, but none of
| the contestants submitted that (I assume they predate xz).
|
| Update#2: Found at least one measurement of xz decompressor at
| 36K, but it seems to me like this is the general-purpose utility
| and includes the compressor, help output, etc.
| http://mattmahoney.net/dc/text.html
| Someone wrote:
| My first thought would be "DAWG". That's a smart way to represent
| a trie, with identical 'tail' ends of the trie merged into one.
|
| https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l...
| compresses a 780k word list into 175k. That's about 22% of the
| size. This accomplishes 27%.
|
| This list is a lot shorter, so there will be fewer opportunities
| for savings. On the other hand, all words are five letters, so
| the 'is a word' bit can be taken out.
| quicktwo wrote:
| I tried this method today, but a huge shortcoming here is that
| a DAWG needs these large pointers between nodes.
|
| I based my approach on http://www.wutka.com/dawg.html and
| http://stevehanov.ca/blog/?id=115.
|
| I generated a DAWG with 12,822 nodes, which means you need 14
| bits for each pointer. A trie representation can be packed much
| smaller because you don't need to randomly jump around the
| graph, you can just read it out sequentially.
|
| With huffman coded labels and offsets, I got the size down to
| approximately:
|
| - 94,761 bits for offsets. - 56,900 bits for labels. - 12,822
| bits for indicating when you're at the end of a next chain.
|
| = 164,483 bits + Size of Huffman Table = ~20,560 bytes
|
| I assumed I didn't need any bits for indicating end of word,
| because all Wordle words are length 5.
|
| Meanwhile, bitpacked trie can get down to 15,599 bytes.
|
| https://github.com/adamcw/wordle-trie-packing#all-words
|
| It's not clear to me a path that will compress the DAWG so much
| that it could cut another 5000 bytes and whatever the Huffman
| table size is.
| quicktwo wrote:
| I ended up doing some math on a theoretical DAWG, based on: h
| ttps://www.cs.put.poznan.pl/dweiss/site/publications/downlo..
| .
|
| With 12,822 nodes, you need 57,387 bits for the labels and
| the Huffman table (I'm sure you could make the Huffman table
| more efficient, but it's only 50 bytes, so that's not helping
| much).
|
| Then, to mimic their edge reordering technique but without
| having to actually implement all the logic, I ordered the
| edges by frequency and used variable length integer encoding
| of size 3 (this performed the best on the data set) which
| required 95,988 bits.
|
| Variable length integer encoding breaks the number into 3 bit
| chunks, each prefixed by 1 bit to indicate if there is
| another 4 bit chunk to read for that number. Since the
| distribution of offsets is heavily skewed, optimizing the
| most frequent offsets into a small package is better even if
| rarer ones suffer from multiple prefix bits.
|
| This is 19,171 bytes total, or substantially worse than both
| the original article and Huffman tries do. This isn't even
| counting the flag bits needed for actually traversing the
| graph. So even cheating, it's not clear I can get a DAWG to
| be within striking distance of either other approach.
|
| I hypothesize that the reason tries and other methods perform
| so well here is the relatively shallow depth. All words are
| only length 5, so the trie doesn't ever get really deep. This
| also means that suffixes generally don't actually take up
| that much space given common ones will also pack small with
| Huffman coding. The size of offsets appears to be just too
| great relative to how much you can save by removing shared
| suffixes from 5 letter words.
|
| Would love to know if there is some trick to DAWG that I'm
| missing that would let me get it even smaller.
| Someone wrote:
| I feared that ("This list is a lot shorter, so there will be
| fewer opportunities for savings")
|
| However, I think you can layout the tree so that no pointers
| point backwards. If so, can you make those offsets smaller by
| making them relative to the current point in the tree?
|
| Also, since the list only has five-letter words, for the last
| letter, you don't even need the letters themselves, just 26
| bits for what letters can complete a word. That might be a
| saving.
|
| Also, the crab source code is available (DEC:
| http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt, Mac: h
| ttp://www.gtoal.com/wordgames/jacobson+appel/mac/Crab_sourc..
| .. Both via http://www.gtoal.com/wordgames/scrabble.html)
|
| Both are nice examples of C the way it is intended to be
| written, or rather, was intended to be written decades ago.
|
| I don't remember how that stores the data, but it might do a
| trick you didn't think of.
|
| And finally, I just realize that, for fairness, you need to
| look at (data size + decompressor size). Did you do that?
| quicktwo wrote:
| Ah, I replied to myself with more information while you
| were also replying.
|
| I also surmise that the short length of the words makes a
| DAWG just very heavy.
|
| It's not clear to me that relative offsets would be notably
| smaller to the extent that would be needed. Even a
| hypothetical and cheated DAWG I came up with is ~33% bigger
| than alternatives. I've generally explored enough (see the
| paper in my other comment) that I don't feel that further
| investigations into a DAWG are likely to outperform other
| methods.
|
| I can't see anything immediately that jumps out that the
| Crab game is doing that's special to save space, I think it
| just achieves better compression because you can compress
| larger files easier, and the words are longer with more
| overlapping sections.
|
| I agree that you need to compare including the decompressor
| size, so I'm not sure which approach is better the Huffman
| trie or the one in the original article. I'm not familiar
| enough with GB programming to be able to suggest how much
| program memory would be needed to decode the Huffman Trie,
| it looks like it would be somewhat similar in complexity.
| jhgb wrote:
| > That's a smart way to represent a trie, with identical 'tail'
| ends of the trie merged into one.
|
| That sounds like a DAG-shaped FSM to me...? At least I can't
| spot the difference.
| NieDzejkob wrote:
| Yeah, tries are special cases of FSMs, and so are DAWGs.
| jhgb wrote:
| Ah, apparently I didn't manage to connect the sentence I
| quoted with the preceding sentence. Now I get it.
| Someone wrote:
| That's correct.
| https://en.wikipedia.org/wiki/Directed_acyclic_word_graph
| links it to Deterministic acyclic finite state automaton (htt
| ps://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...)
|
| I guess a strategy for compressing a word set could be to
| compile a regular expression recognizing it using a good
| regex engine and to then construct a compact representation
| of the resulting automaton.
| cleancoder0 wrote:
| Zero suppressed binary decision diagrams are the best
| anon_123g987 wrote:
| > _I don't have a good feel for how fast the Game Boy runs, so I
| did a bit of speed optimization._
|
| This sounds like a very wrong approach to optimization. I mean,
| if you don't know exactly what and how to optimize, or if there's
| a need for optimization at all, then what are you doing?
| glandium wrote:
| I read it as "I don't know how fast a Game Boy runs, so I
| optimized for speed rather than minimal size"
| Closi wrote:
| The idea of 'don't optimize if you don't have to' probably
| doesn't apply as much when developing a game for a 8-bit
| processor that runs at 4mhz with 8kb of working RAM, and when
| you are building a program which is inherently aiming to push
| the capabilities of the hardware with clever coding tricks (I
| mean the whole project is basically an exercise in
| optimization).
|
| I think OP was saying they weren't sure if the original
| algorithm would be too slow to run under these conditions, and
| didn't have the ability to test it at the time, so they wrote
| it in a way which increased the chances of it running quickly
| considering the system limitations.
| dwrensha wrote:
| Over on http://golf.horse/ there are leaderboards for finding the
| smallest Javascript programs that output various word lists,
| including the Wordle list. I've found it to be a fun and
| educational challenge. I would be excited to see more
| submissions!
| dwrensha wrote:
| Hasegawa Sayuri wrote up some notes about their submissions at
| http://sayuri.tx0.org/golfhorse/, including an extremely
| elegant and compact encoding of huffman trees.
| hinkley wrote:
| Interesting that page suggests that the wordle dictionary is
| 'at most 11.11 bits per word', which works out to 18015 bytes,
| slightly higher than was achieved here.
|
| Golf.horse is measuring the payload plus the compressor, which
| I don't believe the author is doing, and is important when
| trying to be objective about the relative strength of
| solutions. Otherwise you can store the entire file out of band
| in the compressor, emit 1 bit in the output file, and then the
| compressor just returns the expected value on 1 and throws an
| error on 0 saying the file was corrupt.
| phire wrote:
| The other major difference is that golf.horse requires the
| payload to be valid uft8 javascript, which means your binary
| blobs are essentially limited to base64 encoded strings. You
| might manage slightly better, but I suspect the limit is
| somewhere around 6.5bits per byte.
|
| On the gameboy, you have the advantage of being able to use
| the full 8 bits per byte.
| lifthrasiir wrote:
| The possible number of x-byte-long valid UTF-8 strings is
| defined with the following recurrence relation:
| f(-x) = 0 f(0) = 1 f(x) = 0x80 * f(x-1) +
| 0x780 * f(x-2) + 0xf400 * f(x-3) + 0x100000 * f(x-4)
|
| (Replace 0x80 with 0x7c to account for ES6 template
| literals.) The characteristic polynomial for this
| recurrence has a positive root of 144.61 (or 141.12 for
| literals). This means that you can actually put quite more
| than 7 bits per byte in a valid JS code, provided that your
| decoder is negligibly small enough. Indeed, there exists an
| encoding that allows exactly 7 bits per byte by using two-
| byte-long UTF-8 sequence as an escape code [1].
|
| [1] http://blog.kevinalbs.com/base122
| phire wrote:
| Huh. Javascript is significantly more accepting of non-
| printing characters in it's strings than I was expecting.
| I guess I should have known better.
| hobs wrote:
| There's definitely apocryphal stories of someone winning a
| compression contest with this very approach :)
| alisonkisk wrote:
| shimonabi wrote:
| The colors are misleading in my opinion.
|
| Green usually signifies something is correct. You should have
| used yellow for misplaced letters instead.
|
| I had CRAN? in the second row, but I lost the game, because it
| was RANCH.
| quasarj wrote:
| lol yes, I played it and was so confused, the colors are
| literally backwards!
| viraptor wrote:
| I wonder why the first letter is used on its own. Getting the
| first letter in 5 bits + 3 bits out of the second should make the
| first array much more densely populated. Maybe making the further
| lists more sparse offsets the gains?
| jagged-chisel wrote:
| And far better than gzip compression. Nice work. My takeaway is
| that context matters - this is not General Purpose Compression,
| but compression made specifically for this case. Good Stuff.
| [deleted]
| noduerme wrote:
| Even though it's domain specific, it's a pretty clever idea
| that could carry over to other things. I wonder if you couldn't
| cleverly reorder any text document in chunks and get the
| maximum word differences per chunk, keep a map of word order
| and compress it this way. With a 2 bit minimum per word, maybe
| you could take all replica words in two bits.
| vanderZwan wrote:
| If you have enough space to store the fully decompressed
| list, then you could in transpose the list of words - so
| instead of 5 by 12972 make them 12972 by 5, and get
| enormously long repeated runs of first, letters, second
| letters, etc. Any lz77 based compression will compress pretty
| well after that
| lifthrasiir wrote:
| That would be only effective for initial letters though.
| Implicit delta coding, where you strip a common prefix from
| the lexicographically previous word and mark word boundary
| somehow (e.g. capitalization), would be better suited if
| there are many short runs of words sharing a longer prefix;
| it seems to be the case for the Wordle list as well (about
| 10% smaller for zlib -9).
| vanderZwan wrote:
| It would be, but it would also be _really_ effective on
| those initial letters: a near-perfect use case for RLE
| compression on the first two characters should already
| result in something close to a 40% size reduction _before
| Huffman encoding_. But I suppose implicit delta coding
| also basically achieves that.
|
| Anyway, thinking about the transposing idea some more:
| this would effectively split the word in to 262 = 625
| "buckets" of three-letter suffixes. What we could do to
| make those still compress decently after transposing is
| look for shared suffixes in multiple buckets, and ensure
| they get grouped together in the same order before
| transposing. This would result in short runs in those
| suffixes, squeezing some more compression out of it.
|
| ... which should also work really well for implicit delta
| coding.
|
| Hmm... you know, the basic concept here shouldn't be too
| difficult to implement and try out out, thanks for the
| ideas! :)
| quicktwo wrote:
| A trie will already run-length encode all the first
| letters into 26*5=130 bits pre-Huffman coding. I doubt
| RLE will beat that. A trie will in essence RLE every
| level but without needing to track the length of the run,
| so I suspect it'll outperform RLE at every level.
|
| If you have a means of doing RLE that performs otherwise,
| I'd love to understand how it works.
|
| FYI, turning it into 12972 by 5 and Brotli compressing
| achieves 15,093 bytes, which is less than if you first
| turn the data into an ASCII trie then Brotli compress
| that (14,180 bytes) (Source:
| https://github.com/adamcw/wordle-trie-packing#all-words).
| davidjohnstone wrote:
| To improve compression of a sorted list of words you can
| replace the (initial) letters repeated from the word above with
| spaces before compression and add them back as an extra step
| after decompression. For example, if the previous word was
| "apple", the next entry will be " y" ("apply", edit: HN removes
| extra spaces, so this should be four spaces + "y") ("apple"
| will probably already be entered as " le" (three spaces +
| "le")). In theory a compression algorithm could handle this
| automatically, but in practice this gives better compression.
|
| This is conceptually similar to what OP does by storing the
| (numerical) difference between the words. Also, if you have a
| list of numbers that aren't random, they generally compress
| better if you turn it into a list of the differences between
| the numbers.
|
| A simple compression algorithm (miniLZO is apparently 6KB
| compiled) might be small enough and save enough bytes with
| compression to make it worth it for OP.
| creatonez wrote:
| Testing this with zstd -19
|
| 29.44% - Original sorted list just compressed with zstd
|
| 22.45% - Matching prefix characters from previous word
| replaced with space
|
| 19.38% - Matching prefix characters from previous word
| removed
| HALtheWise wrote:
| Because all the words are five letters here, you should be
| fine to elide leading spaces in this case.
| [deleted]
| abainbridge wrote:
| How would that work? If I want to store "apple", "apply",
| "apron" the bytes in memory would be "appleyron". How would
| I know where the second word ends?
| ant6n wrote:
| One newline is probably better than 1-4 spaces.
| pronoiac wrote:
| You might want to look at locatedb and frcode - https://manpa
| ges.ubuntu.com/manpages/bionic/man5/locatedb.5....
|
| If you want to skim, check out the EXAMPLE section toward the
| bottom.
| nerfhammer wrote:
| It's similar to the compression techniques you might use in
| column store
| anyfactor wrote:
| Is task specific compression a thing in real life practical
| software engineering? As far as reducing data loads go I only
| came across the keyword "SQL optimization".
| hamandcheese wrote:
| One example that comes to mind is some work nvidia has done
| compressing "video" streams. They do so by capturing your
| facial movements and reconstructing them on the other side,
| resulting and massively less bandwidth.
|
| https://developer.nvidia.com/ai-video-compression
| detaro wrote:
| Depends how specific you want "specific" to be I guess? I.e.
| we have loads of compression algorithms for different kinds
| of data. Whereas here we are looking at almost dataset-
| specific compression (i.e. the only benchmark is how it works
| for one specific set of data to compress), and there's a
| sliding scale between the two ends.
|
| Similarly, having to contain the decompression code in the
| measured result size and it being a relevant contribution is
| something that only applies in some use cases of compression.
| willis936 wrote:
| Scarcity breeds innovation. Why hand tune a compression
| scheme for a specific dataset when it is less storage
| efficient than LZ? You opt to not use LZ when all the memory
| and compute you have can barely run prefix codes.
|
| That's why people still write for the Z80: it's a fun toy.
| dahart wrote:
| Yes! Not only is it a real thing, but with Moore's Law
| slowing down, data/compute appetites going up, and the gap
| between processing speed and memory speed still large and
| growing, the need for task specific compression is currently
| going up.
|
| Working on GPUs, I see many, and work on some task specific
| compression ideas as part of my job. The compiler has it's
| own ways of compressing code & debug info. The hardware has
| it's own ways of compressing textures. A recent feature we
| built on my team is a compressed encoding for adaptively
| subdividing curves. All of these things have the primary goal
| of reducing memory bandwidth, which in turn increases the
| speed of computation because memory is so frequently the main
| bottleneck.
| londons_explore wrote:
| Anytime you're trying to squeeze more performance out of
| old/underpowered embedded hardware you'll come across stuff
| like this...
|
| Eg. You work for a doorbell company and the boss says "yo,
| can we make our doorbell have 6 tunes instead of one, because
| our competitors are doing that. No, we don't want to change
| microcontroller".
| ant6n wrote:
| At transit app, we built a domain specific compression for
| transit schedules. So instead of a city like New York taking
| 100mb, it takes like 5mb or so. This was a couple years back
| when data was still more expensive, so one of the things it
| allowed is simply always downloading schedules for offline
| availability, instead of having to ask the user when and what
| to download. Here's a write up (sorry for the cheery tone)
| with some details
|
| https://blog.transitapp.com/how-we-shrank-our-trip-
| planner-t...
| justinlloyd wrote:
| Anything that has limited memory or limited bandwidth, or
| where the data is much larger than the available memory or
| bandwidth, e.g. neural compute models at the edge in a IoT
| device, word databases on limited memory systems, and
| foveated compression in VR/AR on super high bandwidth
| connections that still cannot keep up with the 16K video
| stream given modern video protocols.
| psidebot wrote:
| I have designed task specific data structures/compression
| oriented around memory efficiency. In my experience this
| starts to crop up when datasets get big enough to trigger
| cost for performance sensitivity. This is especially true for
| SaaS offerings, where e.g. an ability to stay under the next
| RAM doubling can result in serious hosting savings.
| noduerme wrote:
| It used to be just best practice to shrink down anything over
| the wire as much as possible. When I started building
| websites around 1996, every byte counted and you would
| "optimize" every GIF image carefully to the smallest size you
| could, taking it down to 256 or 16 or even custom colors -
| like 6 colors in the VGA spectrum that looked good enough
| with dithering.
|
| It kinda didn't matter from 2010 on. But one area I've
| written my own specific "compression" methods in, for the
| last few years, has been in shipping data in and out of
| webworkers (in-browser or in Node). This is where there's
| still enough of a performance penalty on a lot of devices for
| sending 1MB that in use cases where you're spawning lots of
| workers to run long tasks, it makes sense to trade time to
| compression for a smaller transfer size.
| morcheeba wrote:
| I'm echoing a couple of replies before me, but I'll give
| concrete examples - MP3, JPEG, and H.264 are all lossy task-
| specific compressions. Lossless compression includes FLAC and
| TIFF.
|
| For genetic data, HapZipper beats general-purpose
| compression.
| https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3488212/
|
| So, yes, actively researched, but you've got to pick a
| specific task that makes sense. Even small niches are viable;
| I made a task-specific compressor to strip the essential
| numbers out of a remote sensor report to make it small enough
| to squirt to a satellite.
| forgotusername6 wrote:
| Video compression algorithms are fascinating. Choosing the
| correct color space and reducing bit count because the
| human eye doesn't see color as well, using discrete cosine
| transform to "group together" the important parts of an
| image, using diffs from previous and future frames, using
| diffs from movement in the image. There are so many
| techniques.
| voussoir wrote:
| Here's another example from a constrained environment: in
| Andy Gavin's interview with Ars Technica, he talks about a
| domain-specific compressor they made for storing Crash
| Bandicoot's animations, because storing each coordinate of
| each vertex for each frame would have been too large.
|
| https://www.youtube.com/watch?v=izxXGuVL21o&t=21m12s
| justinlloyd wrote:
| Yep, in video games, especially on older systems, we did an
| awful lot of that. Storing vector deltas for bone
| animations rather than the full vector3. Compiled graphics
| on old PC games I worked on, which both helped in size, but
| also in speed of blitting to the display. Vector3 are made
| up of three 32-bit floats, but frequently stored as four
| 32-bit floats so that everything aligns on word boundaries,
| but you don't need to do that for data you aren't currently
| using, so you can save 25% of memory right there. Also,
| interleaving vector3's for packing and alignment on 3d
| models. Lots of bitmask manipulations and interleaved
| SIN/COS and DIV/MUL look-up tables. These last couple of
| techniques go all the way back to the original Atari
| Asteroids game from the arcades in the 1970's.
| willis936 wrote:
| Why use one byte for each character? Why not 3 bytes per word?
| loeg wrote:
| Please see step 2.
|
| > Step 2: Each four letter "word" (or tail of a word) can be
| stored with 5 bits per letter, thereby yielding a 20 bit
| unsigned integer.
| [deleted]
| [deleted]
| bbbbbr wrote:
| There is also a NES port in the works:
| https://twitter.com/FG_Software/status/1495400042722897925
|
| And a C64 port:
| https://twitter.com/roysterini/status/1493540659352985602
|
| A brief quote about compression in the NES port:
|
| https://twitter.com/FG_Software/status/1491044035884371971
| "Official #Wordle dictionary implemented, and the game can now
| select a solution from all those found in the original for the
| cost of 1 extra bit per word! Uncompressed size (Raw text files):
| 76060 bytes Compressed size: 26256 bytes"
|
| https://twitter.com/FG_Software/status/1495298243668099073 "Words
| are stored in 2 bytes: 15 bits data, 1 bit to check if it's a
| solution. They're all sorted alphabetically, so I can
| algorithmically determine the first 2 letters with a lookup
| table, and stick the last 3 letters in 15 bits. Bit more to it
| but you can't fit it all in a Tweet"
|
| I've been working on a Game Boy Color (and regular GB) fork that
| in current builds uses the compression by arpruss.
| https://github.com/bbbbbr/gb-wordle
| syrrim wrote:
| $ grep '^[a-z]\{5\}$' /usr/share/dict/words | python -c ' >
| from sys import stdin > from os import write > N = 26
| ** 5 > data = bytearray((N+7)//8) > for l in stdin:
| > b = 0 > for c in l.strip(): > b *=
| 26 > b += ord(c)-ord("a") > data[b//8] |=
| 1<<(b%8) > write(1, data) > ' | gzip | wc -c
| 12126
|
| decompression code costs extra. Though I imagine someone has a
| small gunzip implementation somewhere.
| JeremyBanks wrote:
| retrac wrote:
| Zlib's implementation, at least, requires more working RAM (~40
| KB) than the Game Boy has (8 KB).
| https://github.com/madler/zlib/blob/master/zconf.h
| The memory requirements for inflate are (in bytes) 1 <<
| windowBits that is, 32K for windowBits=15 (default
| value) plus about 7 kilobytes for small objects.
| hinkley wrote:
| This example above is the entire dict file, not the wordle
| file, so it might be worth looking at this.
|
| I'd have to check the version history, but while 15 bits is
| the default it's also the maximum, and you can go down to 8.
| Hardware has gotten a lot faster.
| habibur wrote:
| > This example above is the entire dict file, not the
| wordle fil
|
| only 5 letter words from the dict, not the entire one.
| check the grep command at the beginning.
| hinkley wrote:
| Right, but it's still many times larger and compresses
| better.
| [deleted]
| [deleted]
| hinkley wrote:
| I think you'll find if you use the real dict that your
| compression numbers are much worse. I got around 25k using a
| list I hunted up.
| rchrch wrote:
| Did you compare this to compression with a trie?
| klyrs wrote:
| See step 1; the first level is stored as a trie. Then, see
| Notes, where it's stated that trie-ifying level 2 requires more
| space.
| they4kman wrote:
| I imagine only having to store 5 bits for the differences
| accounts for a large swath of the savings. With the first
| letter bucketing the rest of the words in a sort of trie-like
| behaviour, I wonder if there's enough duplication of successive
| characters for a full trie to be worth it. After all, there
| would need to be extra bits used to store leaf/node identity,
| as well as whether there are _more_ nodes past the current
| leaf. I suppose instead of using markers to denote ends, the
| parent node could store a count, but that might be wasteful for
| buckets at the fourth character.
|
| I'm very curious about this.
___________________________________________________________________
(page generated 2022-02-20 23:01 UTC)