4 ms·

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

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/download/fsacomp.pdf https://www.cs.put.poznan.pl/dweiss/site/publications/downlo...

hinkley 5y ago
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.
- microtonal 5y ago
  But not for Wordle, since a Bloom filter cannot enumerate items? (So, you can't tell which letters were correct.)
  - hinkley 5y ago
    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).
    - elahieh 5y ago
      The 12972 are in the old source: https://web.archive.org//web/20220201010250js_/https://www.powerlanguage.co.uk/wordle/main.e65ce0a5.js https://web.archive.org//web/20220201010250js_/https://www.p... NYT source: https://www.nytimes.com/games/wordle/main.4d41d2be.js 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
      - hinkley 5y ago
        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)
quicktwo 5y ago
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 https://github.com/adamcw/wordle-trie-packing#all-words). 8 * 15,599/64,860 = 1.92 bits per byte.

hinkley 5y ago

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.

microtonal 5y ago
But not for Wordle, since a Bloom filter cannot enumerate items? (So, you can't tell which letters were correct.)
- hinkley 5y ago
  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).
  - elahieh 5y ago
    The 12972 are in the old source: https://web.archive.org//web/20220201010250js_/https://www.powerlanguage.co.uk/wordle/main.e65ce0a5.js https://web.archive.org//web/20220201010250js_/https://www.p... NYT source: https://www.nytimes.com/games/wordle/main.4d41d2be.js 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
    - hinkley 5y ago
      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)

quicktwo 5y ago

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 https://github.com/adamcw/wordle-trie-packing#all-words). 8 * 15,599/64,860 = 1.92 bits per byte.