111–120 of 170 posts
That system used some sort of lossy compression that created artifacts like fake words that don't exist but look enough like real words from the dictionary's point of view that they can be generated.
I find it fascinating.
Earlier quoted context omitted.
> That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. That sounds like a DAG-shaped FSM to me...? At least I can't spot the difference.
Yeah, tries are special cases of FSMs, and so are DAWGs.
Earlier quoted context omitted.
Even though it's domain specific, it's a pretty clever idea that could carry over to other things. I wonder if you couldn't cleverly reorder any text document in chunks and get the maximum word differences per chunk, keep a map of word order and compress it this way. With a 2 bit minimum per word, maybe you could take all replica words in two bits.
If you have enough space to store the fully decompressed list, then you could in transpose the list of words - so instead of 5 by 12972 make them 12972 by 5, and get enormously long repeated runs of first, letters, second letters, etc. Any lz77 based compression will compress pretty well after that
Earlier quoted context omitted.
Interesting that page suggests that the wordle dictionary is 'at most 11.11 bits per word', which works out to 18015 bytes, slightly higher than was achieved here. Golf.horse is measuring the payload plus the compressor, which I don't believe the author is doing, and is important when trying to be objective about the relative strength of solutions. Otherwise you can store the entire file out of band in the compressor…
There's definitely apocryphal stories of someone winning a compression contest with this very approach :)
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?
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.
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?
https://en.wikipedia.org/wiki/De_Bruijn_sequence
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 love little compression hacks like the one given in the article. I created a word search game way back in late 1978/early 1979 4KB of RAM. I had about 2KB for storing the word database. And I recall I had about 2,500 words. Which I had to type in by hand. I used the 26 tables of words trick too, to drop the first letter. I also treated each word being made up of 32 symbols. I called them letters, but they didn't re…
Once you have the delta encoding scheme, do you actually gain anything by splitting into 26 lists by first letter? It seems like the wrapping delta from a->b, b->c, etc would take similar space as the 2 byte pointer in the table, but simplify the code.
Are there general purpose compression tools that preserve the data, but not the ordering? [One of] the reasons gzip does worse is it also preserves the order of input.