4 ms·

> Actually it does seem feasible to make an encoding that's backwards compatible with all printable ASCII characters, and uses 3 bytes for all other code points

> Actually it does seem feasible to make an encoding that's backwards compatible with all printable ASCII characters, and uses 3 bytes for all other code points. Sorry, you can’t squeeze Unicode in that way, even unsynchronised: you fall just over 2½ bits short. No, reserving the 95 printable ASCII characters scuttles your hopes, meaning you get less than 1½ bits of that byte to use for the rest of Unicode, when you needed a touch over 4 bits. To represent all the rest: Unicode scalar values minus printable ASCII is U+0000–U+10FFFF minus U+D800–U+DFFF minus U+0020–U+007E: 1,111,969 possibilities, log₂(1111969) ≈ 20.085 bits of entropy. (Removing the 2048 surrogates and 95 printable ASCII characters barely made a dent, under 0.003 bits, but I had to remove it for informational correctness.) 95 printable ASCII characters, log₂(95) ≈ 6.57 bits. Subtract that reservation from the three bytes available and you’ve got about 17.43 bits left for the rest of Unicode, but you needed over 20. [Edit: I observe you’ve removed what I was quoting before I posted my comment. Still fun mathematics.] > If you discarded ASCII compatibility, you could create a 1-3 byte self-synchronizing unicode encoding. Not quite. If you discarded ASCII compatibility, then you’d have almost four bits to spare, which is enough for a self-synchronising fixed-width 3-byte encoding (reserving the first bit of each byte to signal if it’s a start byte) or for an unsynchronised variable-width encoding of some kind; but to make it even 2-or-3 or 1-or-3 (rather than 1–3) bytes wide variable-width, you’d need four bits (3 + log₂ 2) for self-synchronisation, and you’re about 0.085 bits short. (1–3 bytes variable-width would require 3 + log₂ 3 ≈ 4.58 bits.) —⁂— I just got nerd-sniped, didn’t I?

kingcharles 5y ago
I had to Google ⁂ as I've never seen that character before. Fascinating! It makes a nice Christmas snowflake stand-in. I wonder what HN's rules are with sanitizing Unicode, as they won't allow emojis?
- chrismorgan 5y ago
  I use “—⁂—” as my horizontal rule in plain text, via my Compose key (Compose+h+r). HN removes things that are officially marked as emoji, normalises whitespace to space (which annoys me because I sometimes want to type things like narrow no-break space in equations which it makes wider and loses the no-breakyness of), and that’s all I’ve noticed. Control characters probably get some treatment or other too.
Dylan16807 5y ago
> Sorry, you can’t squeeze Unicode in that way, even unsynchronised: you fall just over 2½ bits short. No, reserving the 95 printable ASCII characters scuttles your hopes, meaning you get less than 1½ bits of that byte to use for the rest of Unicode, when you needed a touch over 4 bits. So it depends on exactly what we mean by compatible, and that's why I removed it. But in particular, the encoding I had in mind when I wrote that was one that allows most ASCII characters as the middle byte of a triplet. That way whether you truncate from beginning or end you'll never have a rogue byte successfully decode. So something like: Lead bytes from C0-FF, middle bytes from 00-BF, final bytes from 00-1F or 7F-BF. If you also exclude null, tab, newline, and line feed, that gives you 64 x 188 x 93, which is just enough for every code point. But arguably that's not compatible enough because you couldn't search for single ASCII characters with a dumb byte-wise algorithm. > Not quite. If you discarded ASCII compatibility, then you’d have almost four bits to spare, which is enough for a self-synchronising fixed-width 3-byte encoding (reserving the first bit of each byte to signal if it’s a start byte) or for an unsynchronised variable-width encoding of some kind; but to make it even 2-or-3 or 1-or-3 (rather than 1–3) bytes wide variable-width, you’d need four bits (3 + log₂ 2) for self-synchronisation, and you’re about 0.085 bits short. (1–3 bytes variable-width would require 3 + log₂ 3 ≈ 4.58 bits.) I don't know where you got that equation but it's not the right one for the situation. Here's a really simple encoding just to disprove it: Leading bytes encode the plane (17 options) plus two more bits into decimal values 0 through 67. Continuation bytes encode 7 bits into decimal values 128 through 255. 17 planes + 2 bits + 7 bits + 7 bits, perfect fit. The remaining values, 68-127, can be used for single byte (and two byte) encodings. But also the definition I was using for self-synchronizing doesn't seem to match the one on wikipedia. My intent was a code where you can guarantee sync after a specific small number of bytes (unlike UTF-1). In particular, if you let standalone bytes and continuation bytes overlap each other, you can still guarantee sync within 3 bytes. This gives you lots of space to play with, and you could make a very useful encoding. You could have >150 single byte codepoints and thousands of double byte codepoints and fit everything else into three bytes.
- chrismorgan 5y ago
  My (3 + log₂ 2) came from reckoning that you needed one whole bit as a signal in each byte (3), and that the byte-width thing (log₂ 2) was extra to that. As you correctly point out, this was incorrect: the first byte doesn’t need one full bit of entropy to signal that it’s the first byte.

kingcharles 5y ago

I had to Google ⁂ as I've never seen that character before. Fascinating! It makes a nice Christmas snowflake stand-in. I wonder what HN's rules are with sanitizing Unicode, as they won't allow emojis?

chrismorgan 5y ago
I use “—⁂—” as my horizontal rule in plain text, via my Compose key (Compose+h+r). HN removes things that are officially marked as emoji, normalises whitespace to space (which annoys me because I sometimes want to type things like narrow no-break space in equations which it makes wider and loses the no-breakyness of), and that’s all I’ve noticed. Control characters probably get some treatment or other too.

Dylan16807 5y ago

> Sorry, you can’t squeeze Unicode in that way, even unsynchronised: you fall just over 2½ bits short. No, reserving the 95 printable ASCII characters scuttles your hopes, meaning you get less than 1½ bits of that byte to use for the rest of Unicode, when you needed a touch over 4 bits. So it depends on exactly what we mean by compatible, and that's why I removed it. But in particular, the encoding I had in mind when I wrote that was one that allows most ASCII characters as the middle byte of a triplet. That way whether you truncate from beginning or end you'll never have a rogue byte successfully decode. So something like: Lead bytes from C0-FF, middle bytes from 00-BF, final bytes from 00-1F or 7F-BF. If you also exclude null, tab, newline, and line feed, that gives you 64 x 188 x 93, which is just enough for every code point. But arguably that's not compatible enough because you couldn't search for single ASCII characters with a dumb byte-wise algorithm. > Not quite. If you discarded ASCII compatibility, then you’d have almost four bits to spare, which is enough for a self-synchronising fixed-width 3-byte encoding (reserving the first bit of each byte to signal if it’s a start byte) or for an unsynchronised variable-width encoding of some kind; but to make it even 2-or-3 or 1-or-3 (rather than 1–3) bytes wide variable-width, you’d need four bits (3 + log₂ 2) for self-synchronisation, and you’re about 0.085 bits short. (1–3 bytes variable-width would require 3 + log₂ 3 ≈ 4.58 bits.) I don't know where you got that equation but it's not the right one for the situation. Here's a really simple encoding just to disprove it: Leading bytes encode the plane (17 options) plus two more bits into decimal values 0 through 67. Continuation bytes encode 7 bits into decimal values 128 through 255. 17 planes + 2 bits + 7 bits + 7 bits, perfect fit. The remaining values, 68-127, can be used for single byte (and two byte) encodings. But also the definition I was using for self-synchronizing doesn't seem to match the one on wikipedia. My intent was a code where you can guarantee sync after a specific small number of bytes (unlike UTF-1). In particular, if you let standalone bytes and continuation bytes overlap each other, you can still guarantee sync within 3 bytes. This gives you lots of space to play with, and you could make a very useful encoding. You could have >150 single byte codepoints and thousands of double byte codepoints and fit everything else into three bytes.

chrismorgan 5y ago
My (3 + log₂ 2) came from reckoning that you needed one whole bit as a signal in each byte (3), and that the byte-width thing (log₂ 2) was extra to that. As you correctly point out, this was incorrect: the first byte doesn’t need one full bit of entropy to signal that it’s the first byte.