3 ms·
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
by hinkley 5y ago
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?
- 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...
- hinkley 5y ago5.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 agoBut not for Wordle, since a Bloom filter cannot enumerate items? (So, you can't tell which letters were correct.)
- hinkley 5y agoWhat 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 agoThe 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
- rasz 5y agohttps://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence
- hinkley 5y agoInteresting. 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.
- alisonkisk 5y agoSee tom7's portmontout http://tom7.org/portmantout/ http://tom7.org/portmantout/ an extension of portmanteau: https://en.m.wikipedia.org/wiki/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.
- hinkley 5y agoStrictly 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)