4 ms·
Dictionary Compression
- Scene_Cast2 5y agoI wonder what the lower bound on the entropy is.
- lifthrasiir 5y agocmix version 19 [1] compressed the wordle wordlist (using the golf.horse dataset [2] as the canonical version) into 9,714 bytes in about three minutes and ~15 GB of memory. This obviously excludes the decompressor size; my golf.horse entry corresponds to the information entropy of at most 11.7 KB though. [1] https://github.com/byronknoll/cmix https://github.com/byronknoll/cmix [2] http://golf.horse/wordle/list http://golf.horse/wordle/list
- mpais 5y agopaq8px v206 [1] with option "-8art" compresses it to 9,145 bytes using ~2GB of memory in 82s, mostly due to a better pre-training stage. [1] https://github.com/hxim/paq8px https://github.com/hxim/paq8px
- willis936 5y agoHmm. My own entropy estimating code suggests a minimum entropy of 17443 bits with a 63 bit word size (I would need to change how I do things to search above 64 bits, which I would like to do and probably will one day). I used this list: https://gist.github.com/cfreshman/a03ef2cba789d8cf00c08f767e0fad7b#file-wordle-answers-alphabetical-txt https://gist.github.com/cfreshman/a03ef2cba789d8cf00c08f767e... Here is the code: X = fread(fid, sprintf('*ubit%d', nBits)); M = numel(X); words = double(unique(X))'; binEdges = [words-0.5; words+0.5]; binEdges = unique(binEdges(:)); P = histcounts(X, binEdges) / M; P(P == 0) = []; H = -sum(P .* log(P) ./ log(max([nBits, 2]))) / nBits * log2(max([nBits, 2])); E = H * M * nBits; This is a textbook entropy implementation and I've been under the impression that you'll never do better than this (for a given word size).
- lifthrasiir 5y agoYou calculated the sum of entropys of each word, not the entropy of the entire word list as a whole (which would be much lower due to the cross-correlation).
- deleted 5y ago[deleted]
- _moof 5y ago> I would have expected at least some simple domain-specific compression. Why? The site is static, so it's cached and browsers get a 304 when they come back. For new players the server compresses the whole thing in flight, not just the word list. Doing some fancy domain-specific compression on the word list would have added unnecessary complexity (read: places for bugs to creep in) and taken time/effort away from more important things.
- marcellus23 5y agoYeah, this seems like a classic case of optimization for optimization's sake.
- gabagool 5y agoThis is really cool and I love that people are using Wordle to explore and explain computer science concepts (to people like me). > The speed-up is significant, about 20x faster. This makes sense because instead of scanning half of all words on average, you only need to scan half of the words with the same first letter. I’ll assume this isn’t exactly 13x due to letter distribution. Extremely minor, but I think one would still expect a 26x speedup, right? You go from searching half of all words to half of 1/26th of all words. Obviously there are more words starting with S than X and all, but my question is just in theory.
- naniwaduni 5y agoRight. The effect of letter distribution, however, is that you're more likely to be searching a bucket with more words in it. So getting somewhat less than 26x speedup makes sense.
- kevincox 5y agoAh, you are absolutely right. I'll update the post. I think your logic for why you get less than 26x makes sense too.
- lifthrasiir 5y agoFor the reference, it seems that the most publicized attempts on compressing the Wordle dictionary is the Game Boy Wordle clone [1]. There are also several other independent attempts, including the golf.horse Kolmogorov complexity competition [2] (where my entry is incidentally at the first place ;-). [1] https://news.ycombinator.com/item?id=30402407 https://news.ycombinator.com/item?id=30402407 [2] http://golf.horse/wordle/ http://golf.horse/wordle/
- iib 5y agoIsn't this best done with the trie-based dictionary (as in lexical dictionary) approach? Am I missing something here? Is there some additional compression opportunity due to the fact that all the words are the same length?
- lifthrasiir 5y agoTries are generally a good choice if you need to access the word list without first decompressing them. If you are looking for the best compression possible though, there may be more latent contexts that you may not realize their existence but can still leverage.
- bob1029 5y agoI've been wondering about this per a unique business system I've been working on... Hypothetically, if you have a situation where you are not allowed to delete any prior business data (i.e. append-only event log), what would stop you from directly using prior log entries as the basis for some sort of incremental/recursive compression dictionary? Put differently, is there any way to leverage scenarios where you have a practically-unlimited dictionary size and willingness to retain all data forever? Or, am I playing with some basic information theory equation the wrong way in my mind?
- lifthrasiir 5y agoYou can have an adaptive dictionary, favoring recently seen entries. The dictionary would have to be rebuilt periodically in practice, but it has an advantage of being able to cope with the ever-changing ("non-stationary") data distribution. Sometimes the dictionary doesn't even need to be stored and instead can be calculated as the data gets decompressed; this is so big deal that many compression algorithms indeed omit and adaptively build the dictionary instead.
- deleted 5y ago[deleted]
- throwaway889900 5y agoWhat you're thinking of is a journaling archiver. Something like zpaq.
- geeio 5y agoThis might be a good fit for roaring bitmaps [1] or Minimal Perfect Hashing [1] http://roaringbitmap.org/ http://roaringbitmap.org/
- kevincox 5y agoI haven't got a full comprehension of 1 and why it would compress a lot better. It would be interesting to take a look. I did consider perfect hashing, however IIUC it will map a fixed set of entries to sequential integers, but it won't do something clever for items not in the set, so I couldn't find a way to make it work well for this problem. I did see someone talking about perfect bloom filters but to be honest I didn't quite understand it https://iswsa.acm.org/bloom.html https://iswsa.acm.org/bloom.html