1) Use UTF-32 everywhere. When space is an issue, just compress it - especially on disk. If you need random access to a string, use a seekable compression algorithm on it on-the-fly. Alternatively, use a compression algorithm with checkpoints and maintain a sorted list of where checkpoints start and how far along in the associated decompressed text you are. (Effectively rolling your own.) Note that this method doesn't work well with writes.
2) Use an interesting variant of a rope. Use a rope, but a) keep track of "logical characters" instead of code points - what unicode calls graphimes, IIRC, and b) have each node have an encoding - and restrict that all characters within a specific node have the same width. This allows for pretty much everything being sublinear. If you allow a bit in a node for "special" nodes (i.e. reversed, lazy-loaded, slice of another node, that sort of thing), reversing, among other things, is actually truly O(1). Bunches of optimizations here - you want to fall back to a "node" that's a flat array for small strings, you want to potentially use overlong encodings internally where appropriate (i.e. if you have 1 1-byte character in a bunch of 2-byte characters, that sort of thing), you want to have some encodings that aren't fixed-width (for things like reading a bunch of bytes from a file), you want to have an encoding that's "unknown" / binary data.
Thoughts:
1) Why on earth does any higher-level language still use byte or codepoint counts for length? And why don't lower-level languages at least have a way to count / index by graphimes?
2) I do not like UTF-8 / 16. It's effectively bad huffman encoding. It's an attempt to save space, but it doesn't even do that well. About the only advantage of UTF-8 is that ASCII maps to it reasonably well. And it has a bunch of disadvantages, chief among them being that if you write a single miltibyte character, you potentially have to rewrite the entire string.
> Use UTF-32 everywhere. When space is an issue, just compress it - especially on disk.
> I do not like UTF-8 / 16. It's effectively bad huffman encoding. It's an attempt to save space, but it doesn't even do that well.
UTF-8 + gzip is 32% smaller than UTF-32 + gzip using the HN frontpage as corpus. Even using xz, it's a 13% gain.
> About the only advantage of UTF-8 is that ASCII maps to it reasonably well.
That's a pretty huge advantage, and a big reason why UTF-8 is actually popular. An other one is UTF-8 being byte-based, it does not care for byte order. UTF-32 is split between BE and LE, and requires either out-of-band byte-order communication or a BOM.
> Why on earth does any higher-level language still use byte or codepoint counts for length?
Because it's easy, and generally O(1) in these languages. Can also be useful to know how much space it'll take when stored, which really is the only useful use for a string length.
> And why don't lower-level languages at least have a way to count / index by graphimes?
Counting graphemes is no more useful than counting bytes or codepoints. You could provide a grapheme cluster count, but:
1. that's O(n) period
2. it serves very little purpose since clusters don't have a fixed width, not even with a fixed-width font
3. clusters can be locale-dependent ("tailored" clusters) although the default set is locale-independent. Now you need to ponder whether you include tailored clusters, don't include them, or optionally include them
4. clusters and glyphs are independent, "ch" is a grapheme cluster in Slovak but two glyphs on-screen, whereas an "fi" ligature is a single glyph but two clusters
User-perceived characters are not graphemes, they are grapheme clusters.
You can look at unicode stings in at least four different levels of abstraction: bytes, code points, code units and grapheme clusters. Only advantage UTF-32 has over others is that allcode units fit into single code point (atleast I think so)
If you want a vector where each user-perceived character and whitespace matches one element in the vector, probably the easiest way is to create vector where each element is short unicode string that matches grapheme cluster.
> Only advantage UTF-32 has over others is that allcode units fit into single code point (atleast I think so)
All code points can be encoded as a single code unit in UTF-32. Code points are the things like U+0065 LATIN SMALL LETTER E; code units are what you encode code points as in a given Unicode encoding — i.e., octets in UTF-8 and 32-bit integers in UTF-32.
> 1) Why on earth does any higher-level language still use byte or codepoint counts for length?
For the higher-level languages, I believe both Haskell and Python¹ now return code point lengths when their length function is called on a string.
> And why don't lower-level languages at least have a way to count / index by graphimes?
Even getting a code point count is difficult in most of those, sadly.
> If you need random access to a string
I really think that random access is not something you greatly need for working with strings, and that most operations are going to scan (linearly) into the string. (For example, splitting on a character requires first finding that character, which is a linear scan that can return an iterator to that position: random indexing is not required.) Sadly, most languages I've worked with, with the exception of C++, do not make great use of the concept of iterators.
Options:
1) Use UTF-32 everywhere. When space is an issue, just compress it - especially on disk. If you need random access to a string, use a seekable compression algorithm on it on-the-fly. Alternatively, use a compression algorithm with checkpoints and maintain a sorted list of where checkpoints start and how far along in the associated decompressed text you are. (Effectively rolling your own.) Note that this method doesn't work well with writes.
2) Use an interesting variant of a rope. Use a rope, but a) keep track of "logical characters" instead of code points - what unicode calls graphimes, IIRC, and b) have each node have an encoding - and restrict that all characters within a specific node have the same width. This allows for pretty much everything being sublinear. If you allow a bit in a node for "special" nodes (i.e. reversed, lazy-loaded, slice of another node, that sort of thing), reversing, among other things, is actually truly O(1). Bunches of optimizations here - you want to fall back to a "node" that's a flat array for small strings, you want to potentially use overlong encodings internally where appropriate (i.e. if you have 1 1-byte character in a bunch of 2-byte characters, that sort of thing), you want to have some encodings that aren't fixed-width (for things like reading a bunch of bytes from a file), you want to have an encoding that's "unknown" / binary data.
Thoughts:
1) Why on earth does any higher-level language still use byte or codepoint counts for length? And why don't lower-level languages at least have a way to count / index by graphimes?
2) I do not like UTF-8 / 16. It's effectively bad huffman encoding. It's an attempt to save space, but it doesn't even do that well. About the only advantage of UTF-8 is that ASCII maps to it reasonably well. And it has a bunch of disadvantages, chief among them being that if you write a single miltibyte character, you potentially have to rewrite the entire string.