Hacker News Reader

Comment by hinkley | Hacker News Reader

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?

View on HN

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

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)

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.

You can see a trie in action used to build a better regex expression: https://www.npmjs.com/package/trie-regex

https://en.wikipedia.org/wiki/De_Bruijn_sequence

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.

I think you are thinking of a trie

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.

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

See tom7's portmontout

http://tom7.org/portmantout/

an extension of portmanteau:

https://en.m.wikipedia.org/wiki/Portmanteau

De Bruijn sequence is more restricted: a cyclic portmontout over a "complete" lexicon of fixed sized words, where every possible string is a valid word.

Strictly speaking, treating the word list as a ring buffer might actually make it a little smaller. Perhaps more importantly, the cycle makes the problem almost exactly analogous to the Traveling Salesman Problem (Although there is an acyclic TSP, it is somewhat lacking in interesting properties like isomorphism)

Reply on news.ycombinator.com