22 ms·
Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes
- Animats 5y agoI 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 5y agoI think that in this case, the original text is rather strange to start with.
- nitrogen 5y agoWhen 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.
- anon_123g987 5y ago> 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 5y agoI read it as "I don't know how fast a Game Boy runs, so I optimized for speed rather than minimal size"
- Closi 5y agoThe 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.
- jagged-chisel 5y agoAnd 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 5y ago[deleted]
- noduerme 5y agoEven 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 5y agoIf 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 5y agoThat 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 5y agoIt 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 26² = 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! :)
- willis936 5y agoWhy use one byte for each character? Why not 3 bytes per word?
- loeg 5y agoPlease 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 5y ago[deleted]
- deleted 5y ago[deleted]
- rchrch 5y agoDid you compare this to compression with a trie?
- klyrs 5y agoSee 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 5y agoI 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.
- ars 5y agoAre 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 5y agoThat'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.
- totetsu 5y agoLooks like you can try it out on this webassembly Gameboy emulator https://wasmboy.app/ https://wasmboy.app/
- willis936 5y ago>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 5y agoI 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 5y agoProbably 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.
- indigodaddy 5y agoBug? See screenshot. My 5th guess shouldn’t have gone down like that for a conventional Wordle clone. https://ibb.co/93CdVWv https://ibb.co/93CdVWv
- throwanem 5y agoLooks like maybe a bug in highlighting multiple occurrences of a letter in the same word, yeah.
- castratikron 5y agoBlack is right letter right spot. Green is right letter wrong spot.
- PickledHotdog 5y agoAhh thanks for this. Found it super confusing!
- indigodaddy 5y agoOh my fault.. assumed the color scheme was the same:
- dwrensha 5y agoOver on http://golf.horse/ 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 5y agoHasegawa Sayuri wrote up some notes about their submissions at http://sayuri.tx0.org/golfhorse/ http://sayuri.tx0.org/golfhorse/, including an extremely elegant and compact encoding of huffman trees.
- hinkley 5y agoInteresting 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 5y agoThe 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 5y agoThe 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 http://blog.kevinalbs.com/base122
- viraptor 5y agoI 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?
- syrrim 5y ago$ 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 5y ago
- retrac 5y agoZlib'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 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 5y agoThis 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.
- hinkley 5y agoI 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 5y agoIt 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.
- deleted 5y ago[deleted]
- shimonabi 5y agoThe 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 5y agolol yes, I played it and was so confused, the colors are literally backwards!
- zackboe 5y agoMy flashcart's GB emulator doesn't have a color palette that matched perfectly, but works well enough! https://i.imgur.com/ePtY5Jf.jpg https://i.imgur.com/ePtY5Jf.jpg Found a GBC implementation as well: https://github.com/bbbbbr/gb-wordle https://github.com/bbbbbr/gb-wordle
- bbbbbr 5y agoThe 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/wordle_compress/compress_comparison.md https://github.com/bbbbbr/gb-wordle/blob/compress_arpruss/wo... Speed (and code size somewhat) have improved more since then.
- quicktwo 5y agoNot sure what technique you're using for the answers list, but the compress5.py suggests it's doing a basic bitmap. Base bitmap is 12972 bits, or 1622 bytes (your file lists 1619, not sure why it's 3 bytes smaller, but all the same). You can "skip encode" (I don't know the formal name for this technique) into 1232 bytes by encoding runs of three [0, 0, 0] as [0], and anything else as [1, X, X, X], saving another 390 bytes. I tried all combinations of runs between 1 and 7, and 3 is optimal.
- quicktwo 5y agoNot sure how big the word dict is in your latest version, but you can do much better simply by reordering how you create your index. With alphabet in order, assembling letters ABCDE: 17345.00 bytes With alphabet in order, assembling letters EDCBA: 16949.00 bytes With alphabet order tweaked, assembling letters EDCBA: 16309.00 bytes Where tweaked means you build your offset as if each position was ordered like this ([::-1] means reverse if you're unfamiliar with Python). ``` alpha1 = "abcdestfghijklmnopqruvwxyz"[::-1] alpha2 = "eaioustrbcdfghjklmnpqvwxyz" alpha3 = "aeioustrbcdfghjklmnpqvwxyz" alpha4 = "eaiousthrbcdfgjklmnpqvwxyz" alpha5 = "aeioustryhkbcdfgjlmnpqvwxz" ``` You can also use a prefix rather than variable length encoding, this means you can use 2 bits to represent a number bigger than 2^14, rather than 3. This might hurt your ability to decode though, as you'll have bits that cross byte boundaries. breaksv = [2**7, 2**14, 2**21] prefixesv = [[0], [1, 0], [1, 1]] You can get much smaller using length 3 varints rather than 7 (13,110 bytes), but I presume that would perform worse on GB hardware than staying byte aligned.
- a-dub 5y agoi wonder if the letter frequencies across the corpora could justify variable length character encoding.
- dietrichepp 5y agoI 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 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 5y agoBoth of these ideas remind me of tries and radix trees.
- mzs 5y agoNice! Do you have a repo somewhere?
- dietrichepp 5y agoI’ll put one sometime relatively soon, got some other stuff on my plate. The Wordle clone is currently “mostly functional”—no pretty graphics or anything, but gameplay checks. I have a limited stamina for NES programming, but I had fun with the proof of concept.
- cosmiccatnap 5y ago
- charcircuit 5y agoCan we compresses further by optimizing for only testing set membership?
- hinkley 5y agoThere 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.
- corruptio 5y agooo 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
- hinkley 5y agoSince 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 5y agooook 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
- hinkley 5y agoI've been using the cleaned up list, so it's possible that changes the behavior a little bit. But more likely one of us has a bug in their logic.
- justinlloyd 5y agoHmmm... sounds familiar https://justinlloyd.li/blog/word-search-game-part-two/ 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.
- quicktwo 5y agoYou can get down to 15,559 bytes by combining a trie with Huffman coding: https://github.com/adamcw/wordle-trie-packing 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 5y agobrotli 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 5y agoA 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 5y agoRoadroller [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/ 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)
- quicktwo 5y ago
- Someone 5y agoMy 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/lectures/scrabble.pdf 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.
- jhgb 5y ago> 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 5y agoYeah, tries are special cases of FSMs, and so are DAWGs.
- jhgb 5y agoAh, apparently I didn't manage to connect the sentence I quoted with the preceding sentence. Now I get it.
- Someone 5y agoThat’s correct. https://en.wikipedia.org/wiki/Directed_acyclic_word_graph https://en.wikipedia.org/wiki/Directed_acyclic_word_graph links it to Deterministic acyclic finite state automaton (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton https://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.
- quicktwo 5y agoI 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 http://www.wutka.com/dawg.html and http://stevehanov.ca/blog/?id=115 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 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.
- hinkley 5y agoThere'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 5y agoI think you are thinking of a trie
- hinkley 5y agoNo, 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.
- hinkley 5y agoNerd sniping indeed. This morning without putting a whole lot of effort into this, I was able to winnow it down to 27.32 bits per word without any other trickery like 5bit packing. You need at most 1 bit per word to identify the real words, so that's 27.32+1 bits without the bitpacking. Doing 6 bits per letter drops that by 25%. Now having put too much effort in, I'm around 21.6 + 1 bits per word, (17 bit packed) just by using SSP.
- hombre_fatal 5y agoYou can see a trie in action used to build a better regex expression: https://www.npmjs.com/package/trie-regex https://www.npmjs.com/package/trie-regex
- deleted 5y ago[deleted]
- microtonal 5y agoYou 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/download/fsacomp.pdf https://www.cs.put.poznan.pl/dweiss/site/publications/downlo...
- coumbaya 5y agoDoes 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 5y agoIn '94, it was possible to have multi-MB cartridges. They used bank switching to access all the data.
- justinlloyd 5y agoI 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.
- iforgotpassword 5y agoMan, at 11 my programs mainly consisted of INPUT, PRINT and GOTO, which I wrote on my uncle's brand new IBM XT.
- slim109ya 5y agoYeah, me too. Mainly D&D character generators.
- justinlloyd 5y agoD&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.
- nathell 5y agoThere’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.
- cleancoder0 5y agoZero suppressed binary decision diagrams are the best
- haunter 5y agoGood job! Works perfectly on the 3DS (mine is a New 3DS XL) with the NSUI! https://i.imgur.com/TjGYsKC.jpeg https://i.imgur.com/TjGYsKC.jpeg
- tyingq 5y agoThere 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-barclays-bank/ 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 https://news.ycombinator.com/item?id=28348965
- deleted 5y ago[deleted]
- tragomaskhalos 5y agoThere 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.
- quicktwo 5y agoMay have been a DAWG like this: https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l... These days GADDAG are used which are faster, but usually much less space efficient: https://en.wikipedia.org/wiki/GADDAG https://en.wikipedia.org/wiki/GADDAG Neither seem to work well in my attempts on this data as the words all being short and the same length work against it in these schemes.
- u2077 5y agoFor 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.
- kqr 5y agoRelated 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.
- grogers 5y agoOnce 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 5y agoSaves you the CPU cycles of having to step through the entire list when the word is zebra.
- _dujt 5y agoDoes anyone know of a HN client that supports keyboard blocking? I really don’t understand HN’s obsession with this game.
- ecf 5y agoGo downvote someone else, this is something people want. https://news.ycombinator.com/item?id=30440491 https://news.ycombinator.com/item?id=30440491
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- lucb1e 5y agoI'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/compress/full.txt 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 http://mattmahoney.net/dc/text.html
- quicktwo 5y agoYou can beat 15,412 bytes with a much simpler decompression algorithm than xz. Using variable length encoding on a tail-sorted delta-offset array gets down to 13,180 bytes. Neither competes with RoadRoller (which gets down to around 12,200 and includes the code for decoding), but that takes forever to decompress and uses a ton of memory so certainly not applicable for this application. See my other comments in this thread if you have interest!
- bbbbbr 5y agoThere is also a NES port in the works: https://twitter.com/FG_Software/status/1495400042722897925 https://twitter.com/FG_Software/status/1495400042722897925 And a C64 port: https://twitter.com/roysterini/status/1493540659352985602 https://twitter.com/roysterini/status/1493540659352985602 A brief quote about compression in the NES port: https://twitter.com/FG_Software/status/1491044035884371971 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 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 https://github.com/bbbbbr/gb-wordle
- jepler 5y agoLike y'all, I wanted to see how I could do. Of course, I didn't get all the way to tested code on a gameboy. But it does compress & decompress in Python. I took the central idea of encoding deltas (or actually delta less 1, since the delta is always at least one; I'll just say delta below), but did it on the full five letter word. The largest delta was still less than 2*18 but bigger than 2*17. (I'm not sure why the blog mentions 20 bits as the biggest delta; I used the dataset from https://github.com/alex1770/wordle/commit/62520406365ca58a1a30d398a2bfad8666f6c3c4 https://github.com/alex1770/wordle/commit/62520406365ca58a1a...) I decided I wanted a variable length code in bits. Manually, I found the best break-points that I could: breaks = [16, 128, 512, 2**12, 2**18] bitprefixes = ['0', '10', '110', '1110', '1111'] So deltas 0..15 are encoded as '0' plus a 4-bit number, deltas 16..271(=16+256-1) as '10' plus a 7-bit number, etc. Compressed like that, my dictionary runs to 14840 bytes. 1111000000000001010110 // aahed 4839 = 4839- 0 1110100001101100 // aalii 2813 = 7652- 4839 1110110100010010 // aargh 4003 = 11655- 7652 110011000010 // aarti 339 = 11994- 11655 1111000000001101110001 // abaca 5634 = 17628- 11994 00111 // abaci 8 = 17636- 17628 00001 // aback 2 = 17638- 17636 00111 // abacs 8 = 17646- 17638 100111110 // abaft 79 = 17725- 17646 ... However, a non byte aligned code isn't ideal, especially on the gameboy's CPU which doesn't have variable bit shifts as far as I recall. Still, over 3000 bytes beckoning to be re-used for some other purpose. Did they put in a soundtrack yet? Compressor & decompressor: https://gist.github.com/jepler/d502965b57fd52df0838a6def2d32a0c https://gist.github.com/jepler/d502965b57fd52df0838a6def2d32...
- quicktwo 5y agoI like your trick of subtracting the prior node size if it's too small, it gets a number of offsets into the lower bucket to save some bits. I took this technique and made a few changes. Firstly, I effectively did variable length integer encoding in chunks of 3, this mildly outperformed your hand crafted prefixes. self.breaksv = [2**3, 2**6, 2**9, 2**12, 2**15, 2**18, 2**21] self.prefixesv = [ ['0'], ['1', '0'], ['1', '1', '0'], ['1', '1', '1', '0'], ['1', '1', '1', '1', '0'], ['1', '1', '1', '1', '1', '0'], ['1', '1', '1', '1', '1', '1', '0']] Secondly, I made my offsets relative to the overall solution space of 26*5, ordering the words sorting from their ends, and with a little bit of twiddling the order of the alphabet to put common letters near the start: alpha1 = "aeioustrbcdfghjklmnpqvwxyz" alpha2 = "aeioustrbcdfghjklmnpqvwxyz" alpha3 = "aeioustrbcdfghjklmnpqvwxyz" alpha4 = "aeioustrbcdfghjklmnpqvwxyz" alpha5 = "aeioustrybcdfghjklmnpqvwxz" bitmap = [] for ia, a in enumerate(alpha1): for ib, b in enumerate(alpha2): for ic, c in enumerate(alpha3): for id, d in enumerate(alpha4): for ie, e in enumerate(alpha5): bitmap.append(e+d+c+b+a in words) Doing this, and then doing the variable length encoding I got the file down to 13,181 bytes (it was 13,180 bytes, but I needed to add a 7 bit termination string so that you can properly decode the file after you write it to disk, otherwise when the file rounds to the nearest byte you have random 0s that get decoded). I'm sure with some twiddling of the alphabets some more you could save a few more bytes, but this does better than both Brotli on a ASCII trie and the Huffman Trie by almost 1KB (https://github.com/adamcw/wordle-trie-packing#all-words https://github.com/adamcw/wordle-trie-packing#all-words), so I'm very happy.
- deleted 5y ago[deleted]
- andyadams222 5y ago[dead]