Fast Lookup of Unicode Properties

Killing Redundancy

Unicode property data is highly redundant, which can be exploited to implement a data compression scheme. How much you can save depends on which properties you store and how exactly you implement the compression and lookup. Roughly a 99% size reduction seems to be the norm in practice, incredible as that may sound on first glance.

Imagine the naive array mentioned above. From it we are going to create three linked arrays in such a way that a lot of the redundancy disappears and lookup does not get more complex than a few array lookups and bit shifts. That keeps memory consumption low and lookup fast.

1. Unicode tends to group similar characters together. That leads to long runs of code points with the identical property data. If we divide the naive array into fixed size blocks a lot of those blocks are identical. This leads to the first two of the three arrays. The second one contains the blocks, eliminating all duplicates. The first one indexes into the second one to get to the correct block for each code point.
2. The second array still duplicates a lot of data. We introduce a third array holding the actual property data, again eliminating duplicates. Then we change the second array to contain indexes into the third one. Because indexes are significantly smaller than the actual data in all but the most trivial cases, we save a lot of space.

Essentially we now have a three-stage system that starts with a particular code point number. A part of that number is used as the index into stage 1. Then stage 1 together with the rest of the code point number indexes into stage 2 which indexes into stage 3 which contains the actual property data.

The diagram above is still a high level overview glossing over a few finer points, for example the exact role of the code point number. To explain these we’ll take a closer look at a real implementation.

3-Stage Lookup Implementation

Basically all the professional implementations work the same – at least the ones I looked at: CPython, the D standard library, utf8proc. The following describes my own implementation for unicode_algorithm, which follows the same tried and true approach.

Even within that approach there is some wiggle room to fine tune the tradeoff between size and performance. I’ll probably discuss that in more detail in a future article. Here is quick overview:

• Three stages.
• 16/8 bits (2/1 bytes) split of the code point number, resulting in a block size of 256.
• Stage 1 contains stage 2 indexes instead of block numbers.

Any Unicode code point can be represented by three bytes because the highest possible code point number is 0x10FFFF. In my implementation the two most significant bytes – the first four digits in normal human-readable hexadecimal notation – are used as the index into the stage 1 array. The remaining least significant byte is a part of the index into the stage 2 array. Where the code point number is split also determines the block size in stage 2. One byte as the partial stage 2 index gives us 256 possible values and a block size of 256.

For efficiency the blocks are stored consecutively in a simple array (stage 2). Still, the boundaries between blocks are real boundaries. In no situation are blocks allowed to overlap.

constexpr const std::array<std::uin16_t, 4352> stage1{
    0, 256, 256, 512, 768,
    // a lot more numbers ...
    256, 256
};

constexpr const std::array<std::uin8_t, 20992> stage2{
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
    // a lot more numbers ...
    0, 0
};

constexpr const std::array<character_properties, 14> stage3{
    {boundary_class::control},
    // ...
    {boundary_class::regional_indicator},
};

uint32_t cpoint = 0x1F601;
Properties props =
    stage3[
        stage2[
            stage1[cpoint >> 8] + cpoint & 0xFF
        ]
    ];