4 ms·

My first thought would be “DAWG”. That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. https://www.cs.cmu.edu/afs/cs

My first thought would be “DAWG”. That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l... compresses a 780k word list into 175k. That’s about 22% of the size. This accomplishes 27%. This list is a lot shorter, so there will be fewer opportunities for savings. On the other hand, all words are five letters, so the ‘is a word’ bit can be taken out.

jhgb 5y ago
> 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.
- NieDzejkob 5y ago
  Yeah, tries are special cases of FSMs, and so are DAWGs.
  - jhgb 5y ago
    Ah, apparently I didn't manage to connect the sentence I quoted with the preceding sentence. Now I get it.
- Someone 5y ago
  That’s correct. https://en.wikipedia.org/wiki/Directed_acyclic_word_graph https://en.wikipedia.org/wiki/Directed_acyclic_word_graph links it to Deterministic acyclic finite state automaton (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...) I guess a strategy for compressing a word set could be to compile a regular expression recognizing it using a good regex engine and to then construct a compact representation of the resulting automaton.
quicktwo 5y ago
I tried this method today, but a huge shortcoming here is that a DAWG needs these large pointers between nodes. I based my approach on http://www.wutka.com/dawg.html http://www.wutka.com/dawg.html and http://stevehanov.ca/blog/?id=115 http://stevehanov.ca/blog/?id=115. I generated a DAWG with 12,822 nodes, which means you need 14 bits for each pointer. A trie representation can be packed much smaller because you don't need to randomly jump around the graph, you can just read it out sequentially. With huffman coded labels and offsets, I got the size down to approximately: - 94,761 bits for offsets. - 56,900 bits for labels. - 12,822 bits for indicating when you're at the end of a next chain. = 164,483 bits + Size of Huffman Table = ~20,560 bytes I assumed I didn't need any bits for indicating end of word, because all Wordle words are length 5. Meanwhile, bitpacked trie can get down to 15,599 bytes. https://github.com/adamcw/wordle-trie-packing#all-words https://github.com/adamcw/wordle-trie-packing#all-words It's not clear to me a path that will compress the DAWG so much that it could cut another 5000 bytes and whatever the Huffman table size is.
- Someone 5y ago
  I feared that (“This list is a lot shorter, so there will be fewer opportunities for savings”) However, I think you can layout the tree so that no pointers point backwards. If so, can you make those offsets smaller by making them relative to the current point in the tree? Also, since the list only has five-letter words, for the last letter, you don’t even need the letters themselves, just 26 bits for what letters can complete a word. That might be a saving. Also, the crab source code is available (DEC: http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt, Mac: http://www.gtoal.com/wordgames/jacobson+appel/mac/Crab_sources/Macintosh/ http://www.gtoal.com/wordgames/jacobson+appel/mac/Crab_sourc.... Both via http://www.gtoal.com/wordgames/scrabble.html http://www.gtoal.com/wordgames/scrabble.html) Both are nice examples of C the way it is intended to be written, or rather, was intended to be written decades ago. I don’t remember how that stores the data, but it might do a trick you didn’t think of. And finally, I just realize that, for fairness, you need to look at (data size + decompressor size). Did you do that?
  - quicktwo 5y ago

jhgb 5y ago

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

NieDzejkob 5y ago
Yeah, tries are special cases of FSMs, and so are DAWGs.
- jhgb 5y ago
  Ah, apparently I didn't manage to connect the sentence I quoted with the preceding sentence. Now I get it.
Someone 5y ago
That’s correct. https://en.wikipedia.org/wiki/Directed_acyclic_word_graph https://en.wikipedia.org/wiki/Directed_acyclic_word_graph links it to Deterministic acyclic finite state automaton (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...) I guess a strategy for compressing a word set could be to compile a regular expression recognizing it using a good regex engine and to then construct a compact representation of the resulting automaton.

quicktwo 5y ago

I tried this method today, but a huge shortcoming here is that a DAWG needs these large pointers between nodes. I based my approach on http://www.wutka.com/dawg.html http://www.wutka.com/dawg.html and http://stevehanov.ca/blog/?id=115 http://stevehanov.ca/blog/?id=115. I generated a DAWG with 12,822 nodes, which means you need 14 bits for each pointer. A trie representation can be packed much smaller because you don't need to randomly jump around the graph, you can just read it out sequentially. With huffman coded labels and offsets, I got the size down to approximately: - 94,761 bits for offsets. - 56,900 bits for labels. - 12,822 bits for indicating when you're at the end of a next chain. = 164,483 bits + Size of Huffman Table = ~20,560 bytes I assumed I didn't need any bits for indicating end of word, because all Wordle words are length 5. Meanwhile, bitpacked trie can get down to 15,599 bytes. https://github.com/adamcw/wordle-trie-packing#all-words https://github.com/adamcw/wordle-trie-packing#all-words It's not clear to me a path that will compress the DAWG so much that it could cut another 5000 bytes and whatever the Huffman table size is.

Someone 5y ago
I feared that (“This list is a lot shorter, so there will be fewer opportunities for savings”) However, I think you can layout the tree so that no pointers point backwards. If so, can you make those offsets smaller by making them relative to the current point in the tree? Also, since the list only has five-letter words, for the last letter, you don’t even need the letters themselves, just 26 bits for what letters can complete a word. That might be a saving. Also, the crab source code is available (DEC: http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt, Mac: http://www.gtoal.com/wordgames/jacobson+appel/mac/Crab_sources/Macintosh/ http://www.gtoal.com/wordgames/jacobson+appel/mac/Crab_sourc.... Both via http://www.gtoal.com/wordgames/scrabble.html http://www.gtoal.com/wordgames/scrabble.html) Both are nice examples of C the way it is intended to be written, or rather, was intended to be written decades ago. I don’t remember how that stores the data, but it might do a trick you didn’t think of. And finally, I just realize that, for fairness, you need to look at (data size + decompressor size). Did you do that?
- quicktwo 5y ago