4 ms·

Mightn't the raw data be a good candidate for huffman encoding https://en.wikipedia.org/wiki/Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding

lifthrasiir 6y ago
Base65536 is not a compression algorithm but rather an encoding scheme that can convey any data compressed or not. Compression algorithms have an implicit input of the list of output symbols, which is commonly but not necessarily an octet (0 through 255). If your output format is the tweet you will eventually end up with something like Base65536 for output symbols.
- GuB-42 6y ago
  The article mentions compression briefly. They are using basic run-length encoding. There are probably better algorithms. GP suggested Huffman but I don't think it will work. Something like the algorithm used by crinkler [1] (context modeling + arithmetic coding) may work better. It can be made even better if combined with the encoding (the base doesn't have to be a power of two). Anyways, no need to overdo it, the author's technique works. At least for the newer base2048 version, optimized for long tweets [1] https://xoofx.com/blog/2010/12/28/crinkler-secrets-4k-intro-executable/ https://xoofx.com/blog/2010/12/28/crinkler-secrets-4k-intro-...
redrobein 6y ago
How would this be considered more efficient if you need an additional character to mark each character?
Dylan16807 6y ago
The HATETRIS moves? You could try but because Huffman coding works at a bit level and there are only 4 moves it's going to have absolutely awful efficiency. You'd want arithmetic encoding at least.
- recursive 6y ago
  Left and right seem like they'd be a lot more common than whatever the other two moves are, so maybe a 1-bit code code be assigned to one of those, and still do better than RLE.
ziml77 6y ago
If they went out of their way to make base65536, I'd be surprised if they didn't evaluate at least a few compression schemes. It's mentioned in the readme that they are using RLE so it seems reasonable to assume that their data tends to have long runs that compress well with RLE.

lifthrasiir 6y ago

Base65536 is not a compression algorithm but rather an encoding scheme that can convey any data compressed or not. Compression algorithms have an implicit input of the list of output symbols, which is commonly but not necessarily an octet (0 through 255). If your output format is the tweet you will eventually end up with something like Base65536 for output symbols.

GuB-42 6y ago
The article mentions compression briefly. They are using basic run-length encoding. There are probably better algorithms. GP suggested Huffman but I don't think it will work. Something like the algorithm used by crinkler [1] (context modeling + arithmetic coding) may work better. It can be made even better if combined with the encoding (the base doesn't have to be a power of two). Anyways, no need to overdo it, the author's technique works. At least for the newer base2048 version, optimized for long tweets [1] https://xoofx.com/blog/2010/12/28/crinkler-secrets-4k-intro-executable/ https://xoofx.com/blog/2010/12/28/crinkler-secrets-4k-intro-...

redrobein 6y ago

How would this be considered more efficient if you need an additional character to mark each character?

Dylan16807 6y ago

The HATETRIS moves? You could try but because Huffman coding works at a bit level and there are only 4 moves it's going to have absolutely awful efficiency. You'd want arithmetic encoding at least.

recursive 6y ago
Left and right seem like they'd be a lot more common than whatever the other two moves are, so maybe a 1-bit code code be assigned to one of those, and still do better than RLE.

ziml77 6y ago

If they went out of their way to make base65536, I'd be surprised if they didn't evaluate at least a few compression schemes. It's mentioned in the readme that they are using RLE so it seems reasonable to assume that their data tends to have long runs that compress well with RLE.