Re: Byte Addressability And Beyond

Lawrence D'Oliveiro wrote:

On Mon, 27 May 2024 15:09:23 -0000 (UTC), John Levine wrote:
 

According to Lawrence D'Oliveiro  <ldo@nz.invalid>:

>
It is easy enough to come up with a fixed-size representation for
characters in Python (or other suitably powerful language), where
“character” = “non-combining code point plus all immediately
-following combining code points”.

>
I have to ask, how much storage do each of these fixed-size character
things take?

>
That’s not important; what’s important is that you can put characters as
elements in an array, randomly accessible just by array index.

>
How am I supposed to write my code with an array of fixed size things if
I don't know how big the things are?

 The fixed-size things are references to objects. Or in a lower-level
language like C, they could indeed be pointers/indexes into an array of
code points.
 

If you mean an array of pointers to sequences of code points, well sure,
but now we're back to variable length encodings.

 We’re not, because we still have easy random access, and the length of the
array is the number of characters.

If you need efficient random read access to particular unicode characters, possibly consisting of multiple codepoints, then I would guess a skip list to be very efficient:
Just a helper array containing the starting offsets to every ~32 or so utf8 characters. This would add 12.5% overhead for a file containing only US ASCII if using 32-bit offsets, while the more longer characters you have the lower the overhead.
When accessing a particular character you could of course use linear scanning past the nearest preceeding index entry.
If you also need to edit the utf8 character array, then you could augment the primary index with one or more higher layers, i.e. a classic skip list.
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"