UCS vs. UTF-8 as Internal String Encoding
lucumr.pocoo.org
lucumr.pocoo.org
It is better to provide string-manipulation facilities which rely on iteration and keep track of offset internally.
For an extended explanation, see Tom Christiansen's comment on this old Python issue: http://bugs.python.org/issue12729#msg142036
1. you're added a layer of complexity to the system because now your strings are all rope-like, except they're not arbitrarily nested so they don't have the IO and compositional advantages of ropes
2. Unicode provides 3 classes of grapheme clusters (legacy, extended and tailored) at least one of which (tailored) is locale-dependent (`ch` is a single tailored grapheme cluster under the Slovak locale, because it's the ch digraph)
And, philosophically, I'd say that something close to (but not quite) this, is what people want to know from a lot of systems when they ask for a string's "length." They don't care how much memory the string is taking up (though they can have some low-level assertions to that effect); they care about whether the supplied text will fit in a given em-width container, or a given number of form blanks. This is what Twitter actually cares about these days; this is what wc(1) or Microsoft Word wants to tell you when you look at "character count"; this is what ncurses thinks in terms of in order to lay out monospaced text between various borders.
Now, ligatures and digraphs are a slight problem, in that people think of fl/fi/etc. as two characters, even if they are visually composed of one, but they don't think of, for example, ß as two characters. Thus why I said "glyph"—people expect "ss" to be two glyphs; "fi" to be two glyphs, and "ß" to be one glyph. On the other hand, they expect diacritics added to any of those things to not add any additional glyphs, even if they introduce kerning; the Japanese http://en.wikipedia.org/wiki/Sokuon, for example, is part of the glyph that follows it, even though it makes the word wider.
It's not a presentation-level characteristic, it's a "the way humans count things on the page" characteristic. But you can very easily build the presentation-level characteristic (grapheme cluster length) from it.
Which is all to say, maybe raw Unicode strings are good for systems languages—but in my day-to-day programming solving business-domain problems, I'd much rather be using a "text library" that provides "text objects" with a length measured in glyphs.
A controller backing a text-editing control can easily maintain an intermediate data structure mapping code points (or even code units) to whatever its unit of editing is.
> And, philosophically, I'd say that something close to (but not quite) this, is what people want to know from a lot of systems when they ask for a string's "length." They don't care how much memory the string is taking up (though they can have some low-level assertions to that effect); they care about whether the supplied text will fit in a given em-width container, or a given number of form blanks. This is what Twitter actually cares about these days; this is what wc(1) or Microsoft Word wants to tell you when you look at "character count"
Sure, I don't disagree about that.
> Thus why I said "glyph"—people expect "ss" to be two glyphs; "fi" to be two glyphs, and "ß" to be one glyph.
Except fi is a single glyph (but should be two grapheme clusters).
> Which is all to say, maybe raw Unicode strings are good for systems languages—but in my day-to-day programming solving business-domain problems, I'd much rather be using a "text library" that provides "text objects" with a length measured in glyphs.
That's a completely different concern, the internal representation and external interface to the string don't have to match. And in my experience, neither glyph length nor grapheme cluster length are of much use outside of providing a mostly pointless character count for a document. Useful metrics are encoded size (for storage) and rendered dimensions (to fit things to displays), the latter not being computable without more or less fully rendering the string anyway. Neither would benefit much or at all from a string representation with first-class grapheme clusters (let alone first-class glyphs)
For big strings like web pages, we already do use zlib (via gzip).
Though, of course, constant-time indexing isn't what it's hyped up to be. That's only for codepoints. Actual characters you see on screen are often combinations of codepoints.
So I've answered my own question really. Why does nobody use it? Because there's no point in it.
http://stackoverflow.com/questions/10143836/why-is-there-no-...
So, there is no encoding that actually has 1 word (of whatever byte length) to a character on the screen?
That question doesn't really make sense. Unbounded cluster sizes is simply a result of unicode design because there's no reason to bound it.
> Does anyone in real writing of languages and not some concocted test case need this?
In the real writing of languages there are languages with grapheme clusters of size 4+ e.g. क्षि (Devanagari kshi) is a single cluster made up of क, ्, ष and ि.
> I understood there is some conflict in the encoding of kanji into unicode, does this relate?
It's unrelated. Han Unification compressed the number of clusters by unifying han characters across simplified Chinese, traditional Chinese, Japanese and Korean. Han characters were an issue in the original 16 bits unicode because supporting all of them was estimated as possibly topping out 100,000 codepoints (where 16 bits unicode only supported 65k codepoints). AFAIK Han characters don't use much if any composition (outside of romanisation). Brahmic scripts, Hebrew and Arabic scripts, on the other hand, pile on diacritics.
If I'm trying to draw a character on the screen, it makes a lot of sense. I guess I'm struck about how hard it would be to select the 4th through 8th character displayed on the screen from rows 3 through 13.
Glyphs vary in width. There are combining characters. There are ligatures (and in some languages, ligatures are necessary for the text to be readable, not just stylistic). There is contextual reordering of characters. There's bi-directional text, which can switch direction mid-sentence when quoting some Roman text in Hebrew or vice versa. There's vertical text. There are a number of fonts, font weights, font styles, font sizes, font features like alternative characters, language dependent selection of glyphs, and so on, plus fallback if the user doesn't have the designated fonts or fonts that cover the given Unicode range installed. There's line breaking, which can't always operate on spaces because not all languages include spaces between words. There's justification of text, distributing the spacing between characters to make a block of text even on both sides.
All of this complexity exists regardless of the encoding that you use. Simply picking a fixed width encoding will not do anything about the vast majority of the complexity; and the fixed width encoding will cause problems of its own (size bloat of strings in memory), as well as leading people astray in thinking that maybe they can get away with making some of the same assumptions that apply to ASCII on a fixed-width terminal (and even there, assuming that 1 character equals 1 unit of width fails in the case of tabs), when in fact they can't and most text handling beyond simply appending strings together is best handled by dedicated libraries that have had hundreds of developer-years of effort put into solving all of these problems.
>> What is the practicality of an unbounded number of
>> possible graphemes?
>That question doesn't really make sense. Unbounded
>cluster sizes is simply a result of unicode design
>because there's no reason to bound it.
UAX15-D3. Stream-Safe Text Format: A Unicode string is said to be in
Stream-Safe Text Format if it would not contain any sequences of
non-starters longer than 30 characters in length when normalized
to NFKD.
* Such a string can be normalized in buffered serialization with a
buffer size of 32 characters, which would require no more than
128 bytes in any Unicode Encoding Form.
* Incorrect buffer handling can introduce subtle errors in the
results. Any buffered implementation should be carefully checked
against the normalization test data.
* The value of 30 is chosen to be significantly beyond what is
required for any linguistic or technical usage. While it would have
been feasible to chose a smaller number, this value provides a very
wide margin, yet is well within the buffer size limits of practical
implementations.
* NFKD was chosen for the definition because it produces the
potentially longest sequences of non-starters from the same text.
[1] http://www.unicode.org/reports/tr15/#Stream_Safe_Text_Format
Whether it needs to be unbounded is a different discussion: Programmers tend to avoid constants that aren't 0, 1, or a power of two. "Unbounded" is easier than guessing (e.g. UCS16) wrong.
In addition, since the existing Unicode standard does not impose a bound, and implementations support stacking of large numbers of diacritics, people have used combinations of extremely large numbers of diacritics as a stylistic device, for example: http://stackoverflow.com/a/1732454/69755. Since examples like this exist in the wild, they need to be supported properly, and so the fundamental string types and operations in string handling libraries should be able to handle it.
How would it be helpful to waste a huge amount of space for the vast majority of text, impose additional limitations on the number of combining characters, just for the benefit of fixed-width encoding of graphemes, which even in itself is not all that helpful since for most applications, you are either going to need to scan through the text linearly, or you could use byte offsets in the variable width encoding just as well as you could use grapheme offsets in a fixed width encoding?
What do you mean by "getting the number of characters actually displayed on the screen"? Do you mean number of glyphs? Number of grapheme clusters? The number of glyphs is dependent on your text rendering system and fonts; even with plain ASCII, you may have multiple codepoints rendered as a single glyph, such as in ligatures like "ffi" in certain fonts. The number of grapheme clusters can be computed by the given algorithm along with some tables of character properties; it's not particularly simple, but trying to represent languages that were originally hand-written on a computer is not simple: http://unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries
1. holding onto opaque string binaries until you need to compose them all together at the end (i.e. the way Erlang's iolists work)
and 2. applying encapsulated operations over a given string (e.g. "split", "scan with regular expression") rather than trying to index into it;
I've never understood why we can't just use a really inefficient-but-practical string encoding, e.g. UTF-32, with a very low-cost stream compression algorithm on top.
That's right. We could figure out how to represent common characters with less bits. For low-cost character stream compression, byte granularity should work nicely with computers, so we should it. A byte could have a bit that indicates the range is extended, like highest bit, because it's easy to process. Same idea could be chained to represent full range of unicode characters. That way we'd have compressed UTF-32 characters!
How would you efficiently scan for a specific 24-bit character by using SIMD? Say you're not running on Haswell, but something older that's not as good with unaligned memory accesses?
Any modern system would use UTF-8.
I know it's not a power of 2, and that's the most common reason cited against using it, but multiplying by 3 is basically n + 2n or a shift-and-add so it's not really hard to do.
Every time someone tries to promote UTF-16, UTF-32, or some imagined encoding like UTF-24, they bring up constant time access to code points, but I have never heard of a reason why you would want that.
Pretty much every use case I have ever heard for constant-time access can be handled just as well by constant-time access at the code unit (byte in UTF-8, 16 bit value in UTF-16, 32 bit value in UTF-32) level. Matching text exactly? Matching works just as well at the code unit level. Doing any kind of fuzzy or regular expression match? You're going to need to iterate over each item anyhow to normalize it or classify it. Need to store offsets? That works just fine at the code unit level.
Most of the other suggestions I've heard for what to do with constant-time access to code points is incorrect when you consider combining characters, normalization, different character widths, need for linguistically appropriate word splitting, etc. If you're doing something that doesn't take these into account, why are you using Unicode instead of just ASCII?
In addition, for the ASCII range, UTF-24 would take up 3 times the space as UTF-8, and the vast majority of text processed is actually in the ASCII range due to verbose markup formats like HTML, XML, etc. Plus if you do anything with the code points in UTF-24, you need to do a bunch of bit-fiddling to move them into 32 bit alignment, so as far as actually decoding the individual code points, it's pretty much a wash with UTF-8.
Compute an offset into a string in one part of your code, and then pass a representation of that offset to another part of your code that then accesses that part of the string and does something with it.
It is theoretically possible to produce an abstract representation of such an offset that would allow constant-time access into a non-uniformly-represented string, but no programming language that I know of has this feature. Even Common Lisp, which is probably the most flexible and future-proof language ever designed, requires that offsets into strings be integers. (Actually, it's even worse than that: Common Lisp requires that strings be arrays of characters, which is truly ironic if you think about it.)
Actually, you can do it in C because you can use a raw pointer, but that is fraught with all manner of other perils.
With UCS-4 (and UCS-2 as implemented in practice), the iterator representation and character index are the same, which makes retrofitting those implementations to use UTF-8-based strings impossible. But for new environments, where UCS-2-backwards-compatibility isn't a requirement, it's not hard to make a string API that properly exposes the difference between iterators and character indexes, which is why newer environments are gravitating towards UTF-8 strings.
And how, exactly, are you going to do that in any extant programming language other than C or assembler?
If your language already uses a Unicode-compatible string type, you should probably use that.
If you are designing a new language, rewriting a language's basic string primitives, or writing an API or application in a language that doesn't have a well-standardized Unicode string type like C or C++, then it is probably better to pick UTF-8; if your app is necessarily single platform and tied to a platform API, choose that API's encoding, but for anything cross platform, the encoding is going to differ between the platforms so choosing UTF-8 and then transcoding at the API boundaries on the different platforms is fine.
By the way, most languages do have the concept of a byte array, and you can provide UTF-8 string operations on top of that; but as I said, in general, you should be using the language's native string type unless you have a very good reason not to.
The original article that we're discussing does mention one of those very good reasons; in Python, it uses an 8-bit Latin-1 encoding if the characters can fit, upgrades to 16-bit UCS-2 if they can fit in that range, and finally upgrades to 32-bit UTF-32 if they don't fit in the UCS-2 range. But that means that if you're appending strings, and one of them contains an emoji (for instance, in a web templating system that encounters an emoji in a comment), that can mean that all of a sudden your string has to grow to four times its original size, which can cause serious problems; so one workaround for that may be to actually write everything out to a UTF-8 encoded string (which in Python can be represented as a byte array) rather than trying to append strings together and hitting that behavior.
Furthermore, several languages already do use UTF-8 as their internal string type; Rust, Go, and Ruby all use UTF-8 as their default or only string type.
And by the way, Rust and Go both use slices to handle the use case you describe; a slice is represented as a pointer to the first byte of interest, and a number representing how many bytes it extends. I don't know about in Go, but in Rust the API guarantees that all string slices created from a string begin and end on proper codepoint boundaries. Go: https://blog.golang.org/slices, Rust: https://doc.rust-lang.org/std/primitive.str.html.
> Why would you want constant time access to code points?
And the answer is: because you might want to compute an offset into a string in one place in your code, and then use that offset to access the string at that offset somewhere else in your code in constant time.
A code point (http://unicode.org/glossary/#code_point) is a value in the range from 0x0 to 0x10FFFF. In a fixed-width type, you need at least 21 bits to represent that, which is why 32 bits is the most common form for representing any arbitrary code point; but if you don't mind the alignment issues, you could even pack it to 24 bits or even 21 bits if you don't mind a little bit twiddling to extract it.
A code unit (http://unicode.org/glossary/#code_unit) is the smallest unit of encoding in the encoding that you are using. In UTF-8, that's a single byte; in UTF-16, it's two bytes, in UTF-32, four bytes.
In order to be able to have constant time offsets, you only need to store a code unit index, not a code point index.
The thing is, individual code points are not really all that interesting from the perspective of text processing. Almost all meaningful processing of them could potentially involve multiple code points, splitting on arbitrary code point boundaries without regards to higher level semantics can cause all kinds of problems, etc. So a desire to have constant time indexing by code points is misguided.
All offsets can be stored by code unit (byte in UTF-8). That gives you all of the constant time access to given points of interest in a string that constant time indexing by code point would have given you.
Well, sort of. What you really want is constant-time access to (semantically meaningful) substrings. Not all code points are semantically meaningful, but the situation is even worse for code units. A pointer to a random code point may or may not designate the boundary of a semantically meaningful substring. But whatever problems that causes, the situation for code units is even worse, because a pointer to a random code unit may or may not designate the start of a code point, and even if it does then you still have the previous problem that a random code point may or may not designate yada yada yada. (And yes, I know that UTF-8 is self-synchronizing. But that doesn't help with the problem I'm talking about, and if you think it does then you haven't understood the problem.)
What you really want is constant-time dereferencing of designators for semantically meaningful substrings. But no language AFAIK actually has that. The fundamental problem is that most languages have painted themselves into a corner by carving into stone the fact that strings can be dereferenced by integers. Once you've done that, you're pretty much screwed. It's not that you can't make it work, it's just that it requires an awful lot of machinery. You basically need to build an index for every string you construct, and that can get very expensive. Fixed-width representations are a less-than-perfect-but-still-not-entirely-unreasonable engineering solution to this problem.
> (And yes, I know that UTF-8 is self-synchronizing. But that doesn't help with the problem I'm talking about, and if you think it does then you haven't understood the problem.)
I would like to retract this, and apologize for the snarky tone. I had mis-remembered the design of UTF-8, and so pretty much everything I said was wrong (well, not all of it was wrong, but the parts that weren't were exactly what you were saying).
I'd edit or delete my comment if I could, but the deadline has passed so this is the best I can do.
> Why would you want constant time access to code points?
The answer is: because you might want to compute an offset into a string in one place in your code, and then pass that offset to another place in your code which then accesses the string at that offset in constant time.
My point is that to make this work you must have string offset be an abstract class, not an integer.
Wouldn't you want that? I would.
> the same is true if you have constant width code points
True, but the validity check for the constant-width case can be done in constant time.
The same is true of UTF-8 because it is self-synchronizing. You only have to check that the byte at the given offset is either 0xxxxxxx or 11xxxxxx.
So you could use a BreakIterator [1] to iterate through grapheme clusters. The iterator returns the index to the cluster though, not the cluster itself. The index is in terms of code units, not in terms of grapheme clusters.
[1] https://docs.oracle.com/javase/6/docs/api/java/text/BreakIte...
Well, it makes it easier to avoid putting an ellipsis in the middle of a multi-byte character, which could crash the user's phone when something else tries to display your now-invalid string.
Truncating between code points to insert an ellipsis is not correct. Not all characters have the same width, even in a fixed-width font; for instance, combining characters have zero width. Truncating between a base character and a following combining character makes no sense. If you're truncating the word "exposé" to fit into six characters, it makes no sense to count that as 7 characters, truncate the accent, and wind up with "expose...". (Yes, normally that will be represented as a pre-composed character, but there are base-character/diacritic combinations that have no pre-composed character, so you will necessarily get a combining diacritic).
Truncating based on character count can also mean that you exceed your width requirement; CJK characters are twice the width of most alphabetic characters.
Additionally, most text is displayed using variable width fonts, where truncation should depend on the precise sum of the widths of characters, but even text that isn't can have the previous two issues. These mean that to do truncation properly, you need to iterate over the characters counting width until you exceed your required width in order to truncate, then truncate at the previous grapheme boundary, which requires walking through the string in order and can be done just as efficiently in a variable width encoding as in fixed.
I think it's valid to pick an approach that makes it more likely I'll do things correctly.
Sounds like these "verbose" markup formats are the real problem in taking up too much space, not the Unicode transformation formats.
Furthermore, even beyond the markup, the vast majority of written content is in the Roman alphabet, of which most characters are in the ASCII range, and those that aren't fit into 2 bytes of UTF-8. 55% of text on the web is in English, then languages using the Roman script or other scripts in the 2-byte UTF-8 range make up 21 of the next 25 most commonly used languages on the internet; of the top 25 languages, only Chinese, Japanese, Korean, and Thai are in ranges that require 3 bytes in UTF-8 for the majority of their characters (https://en.wikipedia.org/wiki/Languages_used_on_the_Internet).
So for the vast majority of text that is processed, UTF-8 is dramatically more efficient than a hypothetical UTF-24 or the real UTF-32. Now, you might say "well, it should all compress away anyhow", but when dealing with text in RAM, it is generally not compressed (and that would make handling it far more complex than just using UTF-8), and memory capacity, latency, and bandwidth can all be important.
Trying to deal with text as fixed-width characters is simply incorrect. Almost every non-trivial means of handling text needs to support arbitrary length strings, needs to deal with clusters of more than one codepoint as a single unit, and needs to iterate over the characters linearly at least once (and can then store byte offsets for random access later on). Dramatically increasing storage requirements of text for the non-benefit of being able to deal with fixed-width codepoints just doesn't make sense.