Hacker News Reader

Comment by microtonal | Hacker News Reader

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...

View on HN

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.

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.

But not for Wordle, since a Bloom filter cannot enumerate items? (So, you can't tell which letters were correct.)

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).

The 12972 are in the old source: https://web.archive.org//web/20220201010250js_/https://www.p...

NYT source: https://www.nytimes.com/games/wordle/main.4d41d2be.js

NYT removed 6 words from the solutions

agora pupal lynch fibre slave wench

and 19 words from the guessable list

bitch chink coons darky dyked dykes dykey faggy fagot gooks homos kikes lesbo pussy sluts spick spics spiks whore

so that's 12972 - 25 = 12947

What in the actual fuck.

I am glad they did that, but I'm not sure I wanted to know that those used to be in the dictionary.

(also you are probably on a list now, but we appreciate your sacrifice)

Reply on news.ycombinator.com