5 ms·

Describing a hack that uses a varying number of bytes for different characters as elegant makes me cringe. However, I have no better proposition.

by elwell 13y ago

meowface 13y ago
It's about as good as you're going to get with character encoding. Unicode + UTF-8 will likely be the standard for representation and encoding for decades to come.
kaoD 13y ago
I see you love wasting resources.
Groxx 13y ago
UTF-32?
nly 13y ago
It's not really a 'hack', but making it backward compatible with ASCII while maintaining a lot of other desirable properties is quite elegant. A lot of people complain about not being able to easily or programmatically manipulate UTF-8 strings on a character-by-character basis, like it's a typical programmers daily business to go messing with natural language, but I've never seen the great loss.
crystaln 13y ago
Seems perfectly sensible to me. Why should characters be of fixed size?
- lukasLansky 13y ago
  Getting i-th char in O(1) is a nice thing to have.
  - mikeash 13y ago
    When is that a nice thing to have? It's almost never a useful operation to perform when working with Unicode strings.
  - nostrademons 13y ago
    It is, but it's not worth wasting 4x memory for the common case of mostly-Latin text. It also turns out that you very rarely need arbitrary string indexing. Most of the time, when you're indexing into a string, it's a fixed (and relatively small) number of bytes from the start or end. UTF-8 can do this in a tight inner loop that just checks for bytes that don't start with 0b10. If you need .startswith or .endswith, you can just compare bytes with a byte length offset. If you need to do substring search, you can do Boyer-Moore on bytes. If you need to test for equality, do it on bytes. If you need to chop a string in half for divide & conquer algorithms and only need to be approximately right, you can chop in half by bytes and then use UTF-8's self-synchronizing property to find the nearest character boundary.
  - simias 13y ago
    UTF-8 is a nice format for storage/transmission. If you're going to do some heavy processing with your text you're supposed to convert it to a fixed-width format in memory (typically UTF-32).
    - nostrademons 13y ago
      Most heavy text-processing applications I know actually tokenize text to words (well, technically terms), keep a lexicon mapping from the term ID to textual representation, and then work in term space. Individual letters are usually not semantically meaningful in most languages (both human and machine), and so your analysis becomes much easier if you operate in a space that is semantically meaningful.
    - masklinn 13y ago
      If you do some heavy processing with your text, the triviality of decoding UTF-8 (or anything else) to codepoints is no issue compared to the complexity of actually processing text. If you think UTF-32 makes it (significantly) easier to do text processing, you're not processing text you're destroying it.
  - andrewaylett 13y ago
    Surrogate pairs mean you can't do this with UTF-16 either. Combining characters make it much less useful for UTF-32, as your understanding of a character no longer matches the user's. So arbitrary strings can't be guaranteed to have this property no matter which standard encoding you use.
  - PuercoPop 13y ago
    Except that because, in unicode, there is no one-to-one correspondence between code points an character, so even in utf-32 providing i-th char is not O(1). As Richard O'Keefe clearly explains: "Now as it happens I don't think random access is important. Here's why. Consider Ṏ. There are three ways to encode that: O + ̃ + ̈ | Õ + ̈ | Ṏ. This one "user character" may be one, two, or three code points ..." [1] [1]: http://erlang.org/pipermail/erlang-questions/2011-October/062066.html http://erlang.org/pipermail/erlang-questions/2011-October/06...
    - erichurkman 13y ago
      This is why normalization methods exist, but is also the source of various security flaws, like Spotify's issue in June 2013 [1] with user names that were different at the Unicode level, but normalized into forms that were not unique. (Their example, the account 'ᴮᴵᴳᴮᴵᴿᴰ' could seize control of the account 'bigbird'.) [1] http://labs.spotify.com/2013/06/18/creative-usernames/ http://labs.spotify.com/2013/06/18/creative-usernames/
      - masklinn 13y ago
        > This is why normalization methods exist Not all (base, combining+) have a precomposed version, so no that doesn't work.
  - lambda 13y ago
    Why? When is this a useful thing?
    - chris_wot 13y ago
      I once had to decode an ASCII based datastream that was encoded something like this: * the first 14 characters were the length of the data stream in ASCII, padded with 0 * after this came the records - each record started with the size of the record, including the record header * the record then had each field start with a letter that indicated what sort of record it was - integer, float, character, variable string - all were encoded in ASCII * variable records were the letter "V", then a 14 byte length Yes, the format was awful. But you asked when that would be useful. There's your answer.
      - nostrademons 13y ago
        You could still do this even if strings were encoded in UTF-8. Just define the length of the record to be the length in bytes. This is why most modern programming & serialization languages (Go, Python 3, Protocol Buffers, Cap'n Proto) define separate byte[] and string types. Some things are just binary data and should be treated as such. Other things are encodings of world languages and should also be treated as such.
      - masklinn 13y ago
        You don't show how O(1) random access is useful here. You show a standard length-prefixed stream encoding.
- deleted 13y ago
  [deleted]
anonymous 13y ago
Consider that it's 1. completely backwards-compatible with ASCII 2. you can always tell if you're reading a part of a multibyte character or not, meaning that you can tell if you're reading a message that was cut in some random point and can tell how many bytes to drop before reaching the first start of a character 3. endian-agnostic due to being specified as a byte stream 4. contains no null bytes, so it can fit in any normal C string Point 1 is absolutely vital for backwards-compatibility and 2 makes it better than a lot of other multibyte encodings. Consider for instance chopping one byte off the start of a ucs2-encoded string - you'll get complete garbage. And 3 means you don't get strange endian-related errors. It's a robust, resilient encoding that's a drop-in replacement for ASCII and needs no special support from many utilities - tail and head for instance can work with UTF8 text as if it's plain ASCII, just looking for a \n byte and chopping the input in lines. So yes, I do think it's elegant. It may not be the simplest possible encoding for unicode, but it's extremely practical.
- dbaupp 13y ago
  > 4. contains no null bytes, so it can fit in any normal C string This is false; the encoding of codepoint 0 is 0x00 per the standard; modified utf-8[1] makes 0 a special case with an over-long encoding: 0xC0 0x80. [1]: http://en.wikipedia.org/wiki/UTF-8#Modified_UTF-8 http://en.wikipedia.org/wiki/UTF-8#Modified_UTF-8
  - deathanatos 13y ago
    Have you ever seen codepoint 0 used for anything other than terminating a string?
    - dbaupp 13y ago
      Personally no, but you have to handle 0 correctly (well, mainly, consistently) otherwise you end up with an attack vector, where one part of the application stops at the 0 (e.g. string equality), and another later steps assumes the condition of the previous part but continues past the 0, resulting in it reading bytes that should've been considered previously (but weren't).
lambda 13y ago
Why? The concept of a "character" actually becomes a lot less meaningful as you add support for all of the world's writing systems (and even all of the features of even the Latin alphabet, such as diacritics and ligatures). Between combining characters, ligatures, case mapping rules that map one character to many, and so on, you realize that actually, there are very few cases where you want to address a "character" as a single independent entity. In fact, for almost everything you do, just acting on a string of bytes is more useful than trying to act on characters individually.

Describing a hack that uses a varying number of bytes for different characters as elegant makes me cringe. However, I have no better proposition.

by elwell 13y ago

Describing a hack that uses a varying number of bytes for different characters as elegant makes me cringe. However, I have no better proposition.

meowface 13y ago

It's about as good as you're going to get with character encoding. Unicode + UTF-8 will likely be the standard for representation and encoding for decades to come.

kaoD 13y ago

I see you love wasting resources.

Groxx 13y ago

UTF-32?

nly 13y ago

It's not really a 'hack', but making it backward compatible with ASCII while maintaining a lot of other desirable properties is quite elegant. A lot of people complain about not being able to easily or programmatically manipulate UTF-8 strings on a character-by-character basis, like it's a typical programmers daily business to go messing with natural language, but I've never seen the great loss.

crystaln 13y ago

Seems perfectly sensible to me. Why should characters be of fixed size?

lukasLansky 13y ago
Getting i-th char in O(1) is a nice thing to have.
- mikeash 13y ago
  When is that a nice thing to have? It's almost never a useful operation to perform when working with Unicode strings.
- nostrademons 13y ago
  It is, but it's not worth wasting 4x memory for the common case of mostly-Latin text. It also turns out that you very rarely need arbitrary string indexing. Most of the time, when you're indexing into a string, it's a fixed (and relatively small) number of bytes from the start or end. UTF-8 can do this in a tight inner loop that just checks for bytes that don't start with 0b10. If you need .startswith or .endswith, you can just compare bytes with a byte length offset. If you need to do substring search, you can do Boyer-Moore on bytes. If you need to test for equality, do it on bytes. If you need to chop a string in half for divide & conquer algorithms and only need to be approximately right, you can chop in half by bytes and then use UTF-8's self-synchronizing property to find the nearest character boundary.
- simias 13y ago
  UTF-8 is a nice format for storage/transmission. If you're going to do some heavy processing with your text you're supposed to convert it to a fixed-width format in memory (typically UTF-32).
  - nostrademons 13y ago
    Most heavy text-processing applications I know actually tokenize text to words (well, technically terms), keep a lexicon mapping from the term ID to textual representation, and then work in term space. Individual letters are usually not semantically meaningful in most languages (both human and machine), and so your analysis becomes much easier if you operate in a space that is semantically meaningful.
  - masklinn 13y ago
    If you do some heavy processing with your text, the triviality of decoding UTF-8 (or anything else) to codepoints is no issue compared to the complexity of actually processing text. If you think UTF-32 makes it (significantly) easier to do text processing, you're not processing text you're destroying it.
- andrewaylett 13y ago
  Surrogate pairs mean you can't do this with UTF-16 either. Combining characters make it much less useful for UTF-32, as your understanding of a character no longer matches the user's. So arbitrary strings can't be guaranteed to have this property no matter which standard encoding you use.
- PuercoPop 13y ago
  Except that because, in unicode, there is no one-to-one correspondence between code points an character, so even in utf-32 providing i-th char is not O(1). As Richard O'Keefe clearly explains: "Now as it happens I don't think random access is important. Here's why. Consider Ṏ. There are three ways to encode that: O + ̃ + ̈ | Õ + ̈ | Ṏ. This one "user character" may be one, two, or three code points ..." [1] [1]: http://erlang.org/pipermail/erlang-questions/2011-October/062066.html http://erlang.org/pipermail/erlang-questions/2011-October/06...
  - erichurkman 13y ago
    This is why normalization methods exist, but is also the source of various security flaws, like Spotify's issue in June 2013 [1] with user names that were different at the Unicode level, but normalized into forms that were not unique. (Their example, the account 'ᴮᴵᴳᴮᴵᴿᴰ' could seize control of the account 'bigbird'.) [1] http://labs.spotify.com/2013/06/18/creative-usernames/ http://labs.spotify.com/2013/06/18/creative-usernames/
    - masklinn 13y ago
      > This is why normalization methods exist Not all (base, combining+) have a precomposed version, so no that doesn't work.
- lambda 13y ago
  Why? When is this a useful thing?
  - chris_wot 13y ago
    I once had to decode an ASCII based datastream that was encoded something like this: * the first 14 characters were the length of the data stream in ASCII, padded with 0 * after this came the records - each record started with the size of the record, including the record header * the record then had each field start with a letter that indicated what sort of record it was - integer, float, character, variable string - all were encoded in ASCII * variable records were the letter "V", then a 14 byte length Yes, the format was awful. But you asked when that would be useful. There's your answer.
    - nostrademons 13y ago
      You could still do this even if strings were encoded in UTF-8. Just define the length of the record to be the length in bytes. This is why most modern programming & serialization languages (Go, Python 3, Protocol Buffers, Cap'n Proto) define separate byte[] and string types. Some things are just binary data and should be treated as such. Other things are encodings of world languages and should also be treated as such.
    - masklinn 13y ago
      You don't show how O(1) random access is useful here. You show a standard length-prefixed stream encoding.
deleted 13y ago
[deleted]

anonymous 13y ago

Consider that it's 1. completely backwards-compatible with ASCII 2. you can always tell if you're reading a part of a multibyte character or not, meaning that you can tell if you're reading a message that was cut in some random point and can tell how many bytes to drop before reaching the first start of a character 3. endian-agnostic due to being specified as a byte stream 4. contains no null bytes, so it can fit in any normal C string Point 1 is absolutely vital for backwards-compatibility and 2 makes it better than a lot of other multibyte encodings. Consider for instance chopping one byte off the start of a ucs2-encoded string - you'll get complete garbage. And 3 means you don't get strange endian-related errors. It's a robust, resilient encoding that's a drop-in replacement for ASCII and needs no special support from many utilities - tail and head for instance can work with UTF8 text as if it's plain ASCII, just looking for a \n byte and chopping the input in lines. So yes, I do think it's elegant. It may not be the simplest possible encoding for unicode, but it's extremely practical.

dbaupp 13y ago
> 4. contains no null bytes, so it can fit in any normal C string This is false; the encoding of codepoint 0 is 0x00 per the standard; modified utf-8[1] makes 0 a special case with an over-long encoding: 0xC0 0x80. [1]: http://en.wikipedia.org/wiki/UTF-8#Modified_UTF-8 http://en.wikipedia.org/wiki/UTF-8#Modified_UTF-8
- deathanatos 13y ago
  Have you ever seen codepoint 0 used for anything other than terminating a string?
  - dbaupp 13y ago
    Personally no, but you have to handle 0 correctly (well, mainly, consistently) otherwise you end up with an attack vector, where one part of the application stops at the 0 (e.g. string equality), and another later steps assumes the condition of the previous part but continues past the 0, resulting in it reading bytes that should've been considered previously (but weren't).

lambda 13y ago

Why? The concept of a "character" actually becomes a lot less meaningful as you add support for all of the world's writing systems (and even all of the features of even the Latin alphabet, such as diacritics and ligatures). Between combining characters, ligatures, case mapping rules that map one character to many, and so on, you realize that actually, there are very few cases where you want to address a "character" as a single independent entity. In fact, for almost everything you do, just acting on a string of bytes is more useful than trying to act on characters individually.