6

I remember reading that there are no existing data structures which allow for random-access into a variable length encoding, like UTF-8, without requiring additional lookup tables.

The main question I have is, is this even a useful property? I mean, to look up and replace random single codepoints in O(1) time.

7

I would give the traditional, and really quite boring answer of it depends.

Is random access to individual characters (glyphs) in a string a useful property? Yes, definitely.

Do you need access to individual code points? I guess that could be useful in certain situations that aren't too contrived if you are doing extensive handling of text data, such as in for example word processing or text rendering. Data (text encoding) normalization is another possible use-case that I can think of. I'm sure there are other good uses as well.

Does it need to be in O(1) time? Really, with a few exceptions that are unlikely to apply in the general case, not necessarily. If O(1) time access is a requirement, it's probably easier to just use a fixed-length encoding such as UTF-32. (And you will still be dealing with cache misses and swap space fetches, so for sufficiently long strings it won't be O(1) anyway... :))

  • Could you give an example situation where random access to glyphs is useful? – John Bartholomew Nov 11 '12 at 19:51
  • @JohnBartholomew I was just about to do that as you posted your comment. See my edit. I'm sure there are plenty more, but that's a fairly obvious one I can think of off the top of my head on a Sunday evening. – a CVn Nov 11 '12 at 19:52
  • Sorry, did you forget to push the change? I don't see any specific example of an operation that benefits from random access, only mention of the general areas of word processing and text rendering. – John Bartholomew Nov 11 '12 at 20:02
  • @JohnBartholomew I guess that depends on how specific an example you want. I'm not particularly familiar with the low-level details of translating (bytes into) code points into graphemes into characters into pixels on a rendering surface, but I can definitely see that at some point in that stack of operations, dealing with code points separately is useful. – a CVn Nov 11 '12 at 20:06
  • Ok, here is a specific example: if you're rendering with a monospace font, then being able to jump into the text by codepoint allows you to select a segment of the text to display a scrolling ticker/marquee, or place the cursor at the right codepoint boundary based on the position of a mouse click. (For the ticker, it's easier to store a byte-index directly, so it just turns into normal sequential iteration over the text which doesn't need random access. In either case it'll only work for a subset of Unicode -- combining marks, bi-di text, complex shaping rules et c. will break it) – John Bartholomew Nov 11 '12 at 21:15
1

The Swift standard library has gone around this problem. You can access the first, second, third item in a string, but it takes linear time.

But it is rather rare that this is needed. You work with indices, which represent positions inside a string. If you ask “where’s the position of the latter z in this string, the answer is not say “6th character” but say “index 9”.

PS The indexes seem to be indexes of UTF-16 words (or bytes if a string is plain ASCII), but that is an implementation detail. Units can be UTF-8 bytes, UTF-16 words, code points or characters = grapheme clusters.

  • And are items code-points, graphemes, grapheme-clusters, or what? Anyway, that's the solution most languages and libraries choose. – Deduplicator Oct 23 '18 at 20:49
0

Off the top of my head:

Since the vast majority of code points from eurocentric perspective are single-byte, perhaps a good O(1) for those cases and O(N) for longer characters would be useful. Perhaps you store the primary byte of the code point in the main fixed-length array, but if the byte indicates an extended char (1 in the first bit IIRC for utf-8) then that tells the algorithm those extended chars are in a secondary storage array that is not uniform length.

This secondary storage array would track the extended bytes as well as the index in the primary fixed-byte array the character appeared in. For a cold lookup, you'd have O(N) where N is the number of extra byte characters. If you were iterating through the array, you could have a following pointer in the extended chars storage and not have any real impact on the extra byte chars. Cache lines shouldn't be horrible since they are both arrays.

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.