29 ms·

An idea I had a few years ago which someone might be able to run with is to develop new charsets based on the underlying data, not just some arbitrary numerical

An idea I had a few years ago which someone might be able to run with is to develop new charsets based on the underlying data, not just some arbitrary numerical range. The idea being that characters that are more common in the underlying language would be represented as lower integers and then use varint encoding so that the data itself is smaller. I did some experiments here and was able to compress our data by 25-45% in many situations. There are multiple issues here though. If you're compressing the data anyway you might not have as big of a win in terms of storage but you still might if you still need to decode the data into its original text.

beached_whale 6y ago
This sounds a lot like Huffman Coding/Gray Codes, the basis of lz family of compression. No need to change the character encoding, just build a table for text and use that for encoding/decoding. Or for better results, build it from the frequency of use in the document and store the table. This is gzip/pkzip...
- derefr 6y ago
  The parent is suggesting something complementary to compression. An altered character encoding (even if just internal to the software, like UCS-16 is to Windows) would mean that strings would be smaller not just on disk/on the network, but in memory, while held in random-access mutable form. This might be a win for heavy text-manipulation systems like ElasticSearch.
  - cheerlessbog 6y ago
    And not so good if you want to do O(1) indexing
    - derefr 6y ago
      True for the GP's suggestion of a varint encoding, but also true for UTF-8 (which is a varint encoding.) So that's not much of a loss; we're already biting this bullet. Still, though, you could have a fixed-size encoding that could still be more compact than UTF-8, if you limited what it could encode (and then held either it, or UTF-8 text, in a tagged union, as an ADT wrapped with an API of string operations that will implicitly "promote" your limited encoding to UTF-8 if the other arg is UTF-8, the same way integers get "promoted" to floats when you math them together.) Then your limited-encoding text could hold and manipulate e.g. ASCII, or Japanese hiragana and katakana, or APL, or whatever else your system mostly holds, as a random-access array of single-octet codepoints; until something outside of that stream comes up, at which point you get UTF-8 text instead and your random-access operations become shimmed by seq-scans. (Or you get a rope with both UTF-8 strings and limited-encoding strings as leaf nodes!) Of course, if you didn't catch it, I'm talking about going back to having code pages. :) Just, from a perspective where everything is "canonically" UTF-8 and code pages are an internal optimization within your string ADT; rather than everything "canonically" being char[] of the system code page.
- thomasrognon 6y ago
  Although he says "able to compress our data", he means that the uncompressed representation is smaller. In addition to memory savings, iteration could theoretically be faster due to fewer missed branches (imagine iterating through mostly similar width characters vs iterating through characters of varying widths).
- byefruit 6y ago
  This is close but incorrect. Most common Lempel-Ziv compressors (gzip/brotli/zstd) use some form of entropy encoding (Huffman/Arithmetic/ANS) but that is in addition to lz algorithm (usually lz77) itself. You can have a Lempel-Ziv compressor that doesn't use entropy encoding, look at something like lz4. lz77 essentially works by copying parts of the recent window of decompressed data. e.g if a phrase of length 10 was used 100 characters ago we could encode 100,10 instead of the phrase itself. Most compressors use entropy encoding on those offset and length streams.
layoutIfNeeded 6y ago
It’s called Huffman coding.
deleted 6y ago
[deleted]

beached_whale 6y ago

This sounds a lot like Huffman Coding/Gray Codes, the basis of lz family of compression. No need to change the character encoding, just build a table for text and use that for encoding/decoding. Or for better results, build it from the frequency of use in the document and store the table. This is gzip/pkzip...

derefr 6y ago
The parent is suggesting something complementary to compression. An altered character encoding (even if just internal to the software, like UCS-16 is to Windows) would mean that strings would be smaller not just on disk/on the network, but in memory, while held in random-access mutable form. This might be a win for heavy text-manipulation systems like ElasticSearch.
- cheerlessbog 6y ago
  And not so good if you want to do O(1) indexing
  - derefr 6y ago
    True for the GP's suggestion of a varint encoding, but also true for UTF-8 (which is a varint encoding.) So that's not much of a loss; we're already biting this bullet. Still, though, you could have a fixed-size encoding that could still be more compact than UTF-8, if you limited what it could encode (and then held either it, or UTF-8 text, in a tagged union, as an ADT wrapped with an API of string operations that will implicitly "promote" your limited encoding to UTF-8 if the other arg is UTF-8, the same way integers get "promoted" to floats when you math them together.) Then your limited-encoding text could hold and manipulate e.g. ASCII, or Japanese hiragana and katakana, or APL, or whatever else your system mostly holds, as a random-access array of single-octet codepoints; until something outside of that stream comes up, at which point you get UTF-8 text instead and your random-access operations become shimmed by seq-scans. (Or you get a rope with both UTF-8 strings and limited-encoding strings as leaf nodes!) Of course, if you didn't catch it, I'm talking about going back to having code pages. :) Just, from a perspective where everything is "canonically" UTF-8 and code pages are an internal optimization within your string ADT; rather than everything "canonically" being char[] of the system code page.
thomasrognon 6y ago
Although he says "able to compress our data", he means that the uncompressed representation is smaller. In addition to memory savings, iteration could theoretically be faster due to fewer missed branches (imagine iterating through mostly similar width characters vs iterating through characters of varying widths).
byefruit 6y ago
This is close but incorrect. Most common Lempel-Ziv compressors (gzip/brotli/zstd) use some form of entropy encoding (Huffman/Arithmetic/ANS) but that is in addition to lz algorithm (usually lz77) itself. You can have a Lempel-Ziv compressor that doesn't use entropy encoding, look at something like lz4. lz77 essentially works by copying parts of the recent window of decompressed data. e.g if a phrase of length 10 was used 100 characters ago we could encode 100,10 instead of the phrase itself. Most compressors use entropy encoding on those offset and length streams.

layoutIfNeeded 6y ago

It’s called Huffman coding.

deleted 6y ago

[deleted]