5 ms·

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.

When is that a nice thing to have? It's almost never a useful operation to perform when working with Unicode strings.

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.