4
$\begingroup$

I'm designing a language that I intend to be implemented on the .NET platform. To my understanding, the native string representation uses UTF-16, by storing an array of char (an unsigned 16-bit type) and offering an API that treats each 16-bit code unit as an element.

This isn't the indexing behaviour I want for strings in my language. At the very least, I want to index character-by-character, returning the nth code point from the data - which is different from the nth code unit, because of surrogate pairs.

Given an unknown amount and position of surrogate pairs in the underlying data, it seems that a naive algorithm to index by character would be forced into O(N) performance (i.e., iterating over the code units until there are enough to make N code points). Is it possible to do better than this, perhaps by recording auxiliary data or using a more complex data structure? Or is resorting to UCS-32 or another such "flat" encoding the only viable option?

Is it possible to support better-than-O(N) indexing for grapheme clusters (notwithstanding the work required to identify the clusters)?

What approaches are taken by real-world languages to store and use such string data?

This is not a duplicate of How have modern language designs dealt with Unicode strings? or Prior art on modeling characters of variable lengths in that I am specifically interested in the implementation of indexing operators, the performance characteristics afforded by various designs, and any relevant optimization techniques.

$\endgroup$
4
  • 3
    $\begingroup$ Generally, indexing by code-point is not useful as there are many combining code points (mulitple code points that combine into a single character), besides just the surrogate pairs. So UCS-32 doesn't really help. $\endgroup$
    – Chris Dodd
    Commented Nov 27, 2023 at 11:40
  • $\begingroup$ @ChrisDodd hence the part about grapheme clusters. But in principle, I imagine that the general form of a solution would apply more or less the same way to both, because either way it's about indexing an abstract sequence of variable-length clusters within a lower-level sequence... yes? $\endgroup$ Commented Nov 27, 2023 at 11:41
  • 1
    $\begingroup$ It's not your question, but you should rethink your plan to treat strings as arrays of code points. Treating strings as arrays of anything just encourages people to write buggy ad-hoc lexers. It's better that string indices be opaque like fgetpos/fsetpos cookies in C, and be manipulated by higher-level functions than integer arithmetic. This is something that most languages handle poorly and I wish newer languages would break the cycle. $\endgroup$
    – benrg
    Commented Nov 29, 2023 at 7:03
  • 1
    $\begingroup$ Your question about efficient indexable representations of strings seems like it might be more appropriate on CS.SE, since the fact that the elements are code points or grapheme clusters is unlikely to matter. Look at the [succinct-data-structures] tag. $\endgroup$
    – benrg
    Commented Nov 29, 2023 at 7:11

2 Answers 2

2
$\begingroup$

Is it possible to support better-than-O(N) indexing for grapheme clusters (notwithstanding the work required to identify the clusters)?

You can of course do it by indirecting. That would be quite inefficient. MoarVM does it with what it calls 'synthetic codepoints', which take advantage of the fact that most grapheme clusters have just one code point: a string is represented by a sequence of 32-bit entities; if the high bit of one is clear, then the low bits are a code point; if the high bit is set, then the low bits represent a pointer to an indirect grapheme cluster object.

In MoarVM, the implementation knows about synthetic codepoints; atop something like .net, you would be at a bit of a disadvantage, but it would still be possible to implement the strategy with some performance penalty. Represent a string with a pair of two arrays: an array of 32-bit integers, as above, and an array of indirect grapheme cluster objects; for an element of the first array whose high bit is set, the low 31 bits are an index into the second array. (You could also make the second array contain the contents of the grapheme clusters directly, skipping an indirection in some cases, but then you would not be able to share structure between strings, so there are tradeoffs.)

One common strategy orthogonal to this that you can use is to notice when a string is all Latin-1, or all UCS-2 with no grapheme clusters of more than one codepoint, and when it is, represent it compactly with just one or two bytes per codepoint.

Also note that this strategy does not allow you to represent a string with more than $2^{31}$ distinct grapheme clusters of more than one codepoint. So it might be desirable to have an additional representation that's fully indirect, as a simple array of words—one per grapheme cluster.

recording auxiliary data

This is how swift works, using what it calls breadcrumbs. But this seems inferior to just using a string representation that's fit for purpose to begin with.

$\endgroup$
-1
$\begingroup$

Depends on what you mean by "possible."

If you mean "never have to iterate over the string," no, it's not possible because even if you do use a custom data structure, you need to iterate at least once to build that data structure.

But if you mean, "don't have to iterate to index a character or grapheme cluster," then what you could do is build a second list containing the location (start and end) of the characters, in order.

You index into the location list, then index into the string.

You could do the same for grapheme clusters.

$\endgroup$
2
  • $\begingroup$ -1, this does not answer the question. The question specifically asks “What approaches are taken by real-world languages to store and use such string data?” which this does not answer. $\endgroup$
    – Alexis King
    Commented Nov 27, 2023 at 16:45
  • $\begingroup$ That's unfair because this does answer the highlighted question. There are three questions in OP. I answered two. $\endgroup$ Commented Nov 27, 2023 at 18:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .