16

According to the Wikipedia article, UTF-8 has this format:

First code Last code Bytes Byte 1    Byte 2    Byte 3    Byte 4
point      point     Used
U+0000     U+007F    1     0xxxxxxx
U+0080     U+07FF    2     110xxxxx  10xxxxxx
U+0800     U+FFFF    3     1110xxxx  10xxxxxx  10xxxxxx
U+10000    U+1FFFFF  4     11110xxx  10xxxxxx  10xxxxxx  10xxxxxx
x means that this bit is used to select the code point.

This wastes two bits on each continuation byte and one bit in the first byte. Why is UTF-8 not encoded like the following?

First code Last code Bytes Byte 1    Byte 2    Byte 3
point      point     Used
U+0000     U+007F    1     0xxxxxxx
U+0080     U+3FFF    2     10xxxxxx  xxxxxxxx
U+0800     U+1FFFFF  3     110xxxxx  xxxxxxxx  xxxxxxxx

It would save one byte when the code point is out of the Basic Multilingual Plane or if the code point is in range [U+800,U+3FFF].

Why is UTF-8 not encoded in a more efficient way?

  • 3
    cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt Your proposed encoding is similar to the original FSS/UTF proposal. Ken Thompson and Rob Pike wanted the self-synchronizing property. – ninjalj Mar 9 '15 at 20:56
  • 3
    Also, your encoding doesn't seem to guarantee that ASCII code values don't appear in any part of the representation for non-ASCII characters. FSS/UTF and UTF-8 are designed to work with legacy programs, (e.g: those using ASCII NUL and slash (path separator) as separators). – ninjalj Mar 9 '15 at 21:08
25

This is done so that you can detect when you are in the middle of a multi-byte sequence. When looking at UTF-8 data, you know that if you see 10xxxxxx, that you are in the middle of a multibyte character, and should back up in the stream until you see either 0xxxxxx or 11xxxxxx. Using your scheme, bytes 2 or 3 could easily end up with patters like either 0xxxxxxx or 11xxxxxx

Also keep in mind that how much is saved varies entirely on what sort of string data you are encoding. For most text, even Asian text, you will rarely if ever see four byte characters with normal text. Also, people's naive estimates about how text will look are often wrong. I have text localized for UTF-8 that includes Japanese, Chinese and Korean strings, yet it is actually Russian that takes most space. (Because our Asian strings often have Roman characters interspersed for proper names, punctuation and such and because the average Chinese word is 1-3 characters while the average Russian word is many, many more.)

  • But with me scheme if you start at a location known to be at the begging of a character, then you can tell how many bytes are in the character and get to the begging of the next character. – qbt937 Nov 9 '14 at 19:59
  • 11
    Sure. Your scheme is more information dense but does not have an important feature UTF-8 provides. In general, people prefer the safety, which is why UTF-8 is possible. Besides, to really prove your scheme is actually more efficient, you'd want to provide statistics using real text. You may well find that in most real text, your scheme saves a very trivial amount and thus the savings isn't worth it. – Steven Burnap Nov 9 '14 at 20:03
  • 3
    One other important characteristic: If there's no embedded zero codepoint, there are no embedded zeroes in the string. – Deduplicator Apr 28 '15 at 11:12
  • For Thai script you need to allow 4 bytes per printed character. Not only did they come late to the party and so got a high numbered code group. Many things that look like a single character when printed are actually composed of three different unicode characters. – James Anderson Apr 28 '15 at 11:27
  • @qbt937: Using your scheme, how would one quickly scan to find out if one string contains another? – supercat Jun 1 '15 at 7:10
6

The official way lets the decoder know when it's in the middle of the tuple and it knows to skip bytes (or go backwards) until the byte starts with 0 or 11; this prevents garbage values when a single byte gets corrupted.

3

Short answer, your proposal does not differentiate between the first byte and continuation bytes.

The bit pattern at the high end of the first byte tells you with how many bytes the actual character is built. These patterns provide also some error recognition while parsing a string. If you are reading the (seemingly) first byte of a character and you get 10xxxxxx then you know that you are out of synch.

2

What hasn't been mentioned is that if you have a correct sequence of code points, and a pointer that is guaranteed to point to the first byte of a code point, with UTF-8 you can very easily find the pointer to the first byte of the previous code point (skip all bytes that start with 01xx xxxx). With your encoding, it's impossible without potentially examining all bytes up to the start of the string.

Consider the sequences of (2n + 2) bytes

0xxxxxxx
n times (10xxxxxx, 10xxxxxx)
0xxxxxxx

and

n times (10xxxxxx, 10xxxxxx)
(10xxxxxx, 0xxxxxxx)

If you have a pointer to the first byte of the first code point after this sequence, you must examine all bytes to find out whether the last codepoint is 0xxxxxxx or (10xxxxxx, 0xxxxxxx).

There are actually more efficient encoding schemes, where going to the previous code point can be done in constant time, and pointers to the middle of a code point can be fixed. Allow the following codes:

X where X < 128
YX where 128 ≤ Y < 236, X < 128
ZYY where 236 ≤ Z < 256, 0 ≤ Y < 236. 

If one of the previous three bytes is ≥ 236 then it is the start of a 3 byte sequence, because there can be no two such bytes within any valid 3 byte sequence. Otherwise, if one of the previous two bytes is ≥ 128 then it is the start of a two byte sequence. Otherwise, the previous byte is a single byte < 128.

Searching for a substring becomes slightly more difficult. You may want to exclude zero bytes so that a string only contains a zero byte if it contains a zero code point.

  • What hasn't been mentioned… – not really as this follows directly from observation made in @ratchet freak's answer. – Piotr Dobrogost Mar 1 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.