If you are a developer and faced with the task of choosing a character encoding, Unicode is almost always the correct choice. The specific representation method depends on the context, but more often than not, there is a universal answer — UTF-8. It is advantageous as it allows the use of all Unicode characters without wasting too many bytes in most cases. However, for languages that use more than just the Latin alphabet, 'not too many' means at least two bytes per character. Can we do better without reverting to prehistoric encodings that limit us to only 256 available characters?
Below, I invite you to explore my attempt to provide an answer to this question and the implementation of a relatively simple algorithm that allows storing strings in most languages of the world without adding the overhead present in UTF-8.
Disclaimer. I will make a few important clarifications right away: the solution described is not proposed as a universal replacement for UTF-8, it is suitable only in a narrow list of cases (which will be outlined below), and it should never be used for interaction with third-party APIs (which are not familiar with it). Most often, for compact storage of large volumes of text data, general-purpose compression algorithms (such as deflate) will suffice. Moreover, during the creation of my solution, I found an existing standard within Unicode that addresses the same problem — it is somewhat more complex (and often worse), but it is still an accepted standard, rather than something hastily put together. I will also discuss it.
About Unicode and UTF-8
To start — a few words about what exactly Unicode and UTF-8.
As is known, 8-bit encodings were popular in the past. They were simple: 256 characters can be numbered from 0 to 255, and numbers from 0 to 255 can obviously be represented in one byte. Going back to the origins, ASCII encoding is limited to 7 bits, which is why the highest bit in its byte representation equals zero, and most 8-bit encodings are compatible with it (they only differ in the 'upper' part, where the highest bit equals one).
How does Unicode differ from those encodings, and why are there so many specific representations associated with it — UTF-8, UTF-16 (BE and LE), UTF-32? Let's break it down in order.
The main Unicode standard only describes the correspondence between characters (and in some cases, the individual components of characters) and their numbers. And there are many possible numbers in this standard — ranging from 0x00 up to 0x10FFFF (1,114,112). If we wanted to store a number within such a range in a variable, neither 1 nor 2 bytes would be enough. And since our processors are not very well suited for working with three-byte numbers, we would have to use a full 4 bytes for one character! This is UTF-32, but due to this “wastefulness,” this format is not popular.
Fortunately, the characters within Unicode are not arranged randomly. Their multitude is divided into 17 “planes,” each containing 65,536 (0x10000) «code points). The concept of a “code point” here is simply a number assigned to a character, which Unicode has assigned to it. However, as mentioned earlier, not only individual characters are numbered in Unicode, but also their components and control marks (and sometimes, a number does not correspond to anything at all — perhaps for the time being, but that is not too important for us), so it is more accurate to always refer to the number of actual numbers, rather than characters. However, for brevity, I will often use the term “character,” implying the term “code point.”
Unicode planes. As can be seen, most of them (planes 4 to 13) are still unused.
What’s remarkable is that all the main “core” lies in the zero plane, which is called "Basic Multilingual Plane". If the string contains text from one of the modern languages (including Chinese), you will not go beyond this plane. But you also cannot cut off the rest of Unicode — for example, emojis are mainly located at the end of the next plane, "Supplementary Multilingual Plane" (it extends from 0x10000 up to 0x1FFFF). Therefore, UTF-16 operates as follows: all characters that fall into Basic Multilingual Planeare encoded "as is," with their corresponding two-byte number. However, some numbers in this range do not represent specific characters at all, but indicate that the next pair of bytes needs to be considered — combining the values of these four bytes together, we get a number that encompasses the entire valid range of Unicode. This representation is called “surrogate pairs” — you may have heard of them.
Thus, UTF-16 requires two or (in very rare cases) four bytes for a single 'code point'. This is better than using four bytes all the time, but the Latin script (and other ASCII characters) in this encoding consumes half of its space in zeros. UTF-8 aims to rectify this: ASCII takes just one byte again; codes from 0x80 up to 0x7FF — two bytes; from 0x800 up to 0xFFFF — three, and from 0x10000 up to 0x10FFFF — four. On one hand, the Latin script has improved: compatibility with ASCII has returned, and the distribution is more evenly 'spread out' from 1 to 4 bytes. However, alphabets other than Latin do not gain any advantage compared to UTF-16, and many now even require three bytes instead of two — the range covered by two-byte encoding has shrunk 32 times, from 0xFFFF up to 0x7FF, and it no longer includes either Chinese or, for example, Georgian. Cyrillic and five other alphabets — hooray — got lucky with 2 bytes per character.
Why is this the case? Let's look at how UTF-8 represents character codes:
Directly for representing numbers, bits marked by the symbol are used here. xIt can be seen that in two-byte encoding, there are only 11 such bits (out of 16). The leading bits here serve only a functional purpose. In the case of four-byte encoding, a full 21 bits out of 32 are allocated for the code point number — it seems like three bytes (which give a total of 24 bits) would be enough, but control markers consume too much.
Is this bad? In fact, not really. On one hand — if we are very concerned about the space used, we have compression algorithms that can easily eliminate all unnecessary entropy and redundancy. On the other — Unicode's goal was to provide the most universal encoding possible. For instance, a string encoded in UTF-8 can be handed off to code that previously only worked with ASCII, without fear that it will see a character from the ASCII range that isn't actually there (since in UTF-8, all bytes starting with a zero bit are indeed ASCII). And if suddenly we want to trim a small tail off a large string without decoding it from the beginning (or restore part of the information after a damaged section) — it’s not difficult for us to find the offset where a certain character begins (just skip the bytes that have a bit prefix) 10).
So why invent something new?
At the same time, there are rare situations when compression algorithms like deflate are poorly applicable, yet there is a desire to achieve compact storage of strings. Personally, I encountered such a task while contemplating the construction of for a large dictionary that includes words from arbitrary languages. On one hand, each word is very short, so compressing it would be ineffective. On the other hand, the tree implementation I was considering was designed for the condition that each byte of the stored string would create a separate tree node, making it very useful to minimize their number. In my library (as in , on which it is based) this problem is solved simply—strings packed in -dictionary are stored there in . But, as one can easily understand, this works well only for a limited alphabet—a string in Chinese can't be accommodated in such a dictionary.
I would also like to point out another unpleasant nuance that arises when using UTF-8 in such a data structure. In the picture above, it can be seen that when a character is written in two bytes, the bits related to its number are not consecutive but are interrupted by a couple of bits 10 in the middle: 110xxxxx 10xxxxxx. Because of this, when the lower 6 bits of the second byte overflow in the character code (i.e., a transition occurs 10111111 → 10000000), the first byte also changes. As a result, the letter 'п' is represented by the bytes 0xD0 0xBF, while the following letter 'р' is already 0xD1 0x80. In the prefix tree, this leads to splitting the parent node into two—one for the prefix 0xD0, and the other for 0xD1 (even though all Cyrillic could be encoded using only the second byte).
What I came up with
Facing this task, I decided to practice bit manipulation and at the same time get to know the structure of Unicode a bit better. The result was a coding format called UTF-C (the 'C' stands for compact), which uses no more than 3 bytes for one code point and often allows just one extra byte for the entire encoded string. This results in such encoding being 30-60% more compact than UTF-8 for many non-ASCII alphabets..
I documented examples of the encoding and decoding algorithms in the form of , you can freely use them in your code. However, I would like to emphasize that in some sense, this format remains a 'bicycle', and I do not recommend using it without understanding why you need it. After all, it’s more of an experiment than a serious 'improvement of UTF-8'. Nevertheless, the code is written neatly, concisely, with a lot of comments and test coverage.
Test results and comparison with UTF-8
I also created , where you can evaluate the algorithm's performance, and I will discuss its principles and development process in more detail.
Eliminating redundant bits
I based it on UTF-8, of course. The first and most obvious thing to change is to reduce the number of control bits in each byte. For example, the first byte in UTF-8 always starts with either 0, or 11 — and the prefix 10 only exists for subsequent bytes. Let's replace the prefix 11 to 1, and for subsequent bytes, we will completely remove the prefixes. What do we get?
0xxxxxxx — 1 byte
10xxxxxx xxxxxxxx — 2 bytes
110xxxxx xxxxxxxx xxxxxxxx — 3 bytes
Wait, where is the four-byte representation? It has become unnecessary — with three-byte encoding, we now have access to 21 bits, which is more than enough for all numbers up to 0x10FFFF.
What have we sacrificed here? The most important thing — detecting the boundaries of characters from arbitrary positions in the buffer. We cannot point to an arbitrary byte and find the start of the next character from it. This is a limitation of our format, but in practice, the need for this rarely arises. Usually, we can run through the buffer from the beginning (especially when dealing with short strings).
The situation with covering languages with 2 bytes has also improved: now the two-byte format provides a range of 14 bits, which corresponds to codes up to 0x3FFF. The Chinese are unfortunate (their characters mainly fall in the range from 0x4E00 up to 0x9FFF), but for Georgians and many other nations, it has become better — their languages also fit into 2 bytes per character.
Introducing the encoder state
Now let's think about the properties of the strings themselves. In a dictionary, words are most often composed of characters from one alphabet, and this is also true for many other texts. It would be good to specify this alphabet once and then only indicate the letter number within it. Let's see if the arrangement of characters in the Unicode table helps us.
As mentioned above, Unicode is divided into planes up to 65536 codes each. However, this is not a very useful division (as already mentioned, we are most often in the zero plane). A more interesting division is into blocks. These ranges no longer have a fixed length and carry more meaning — as a rule, each combines characters of one alphabet.
A block containing characters of the Bengali alphabet. Unfortunately, for historical reasons, this is an example of not very dense packing — 96 characters are scattered across 128 code points of the block.
The beginnings of blocks and their sizes are always multiples of 16 — this is simply done for convenience. Additionally, many blocks start and end at values that are multiples of 128 or even 256 — for example, the main Cyrillic occupies 256 bytes from 0x0400 up to 0x04FF. This is quite convenient: if we save the prefix once 0x04, then any Cyrillic character can be written in one byte afterwards. However, this way we lose the ability to revert to ASCII (and to any other characters at all). Therefore, we do it this way:
- Two bytes
10yyyyyy yxxxxxxxnot only denote the character with numberyyyyyy yxxxxxxx, but also change the current alphabet toyyyyyy y0000000i.e. we remember all bits except the least significant 7 bits); - One byte
0xxxxxxxis a character of the current alphabet. It simply needs to be added to the offset we memorized in step 1. As long as we haven't changed the alphabet, the offset is zero, so we have maintained compatibility with ASCII.
Similarly for codes that require 3 bytes:
- Three bytes
110yyyyy yxxxxxxx xxxxxxxxdenote the character with numberyyyyyy yxxxxxxx xxxxxxxx, change the current alphabet toyyyyyy y0000000 00000000we remember everything except the least significant 15 bits), and set a flag that we are now in long mode (when switching the alphabet back to two-byte, we will reset this flag); - Two bytes
0xxxxxxx xxxxxxxxin long mode, this is the current alphabet character. Similarly, we add it to the offset from step 1. The only difference is that now we read two bytes (because we've switched to that mode).
Sounds good: now as long as we need to encode characters from the same 7-bit Unicode range, we spend 1 extra byte at the beginning and only one byte per character.
The work of one of the early versions. It already often surpasses UTF-8, but there is still room for improvement.
What became worse? Firstly, we have a state, namely the offset of the current alphabet and a flag for long mode.This additionally limits us: now the same characters can be encoded differently in different contexts. For instance, substring searches will have to consider this, rather than simply comparing bytes. Secondly, as soon as we switched alphabets, encoding ASCII characters became problematic (this includes not only Latin letters but also basic punctuation, including spaces) — they require a re-switching of the alphabet to 0, which introduces an extra byte (and another one to revert to our main alphabet).
One alphabet is good, two are better.
Let's try to slightly modify our bit prefixes, adding another one to the three described above:
0xxxxxxx — 1 byte in normal mode, 2 in long mode.
11xxxxxx — 1 byte
100xxxxx xxxxxxxx — 2 bytes
101xxxxx xxxxxxxx xxxxxxxx — 3 bytes
Now, in the two-byte encoding, one available bit has become less — code points can fit up to 0x1FFF, not 0x3FFF. However, it’s still noticeably more than in two-byte UTF-8 codes, most of the common languages still fit, with the most notable loss being and , the Japanese are sad.
What is this new code 11xxxxxx? Это небольшой «загашник» размером в 64 символа, он дополняет наш основной алфавит, поэтому я назвал его вспомогательным (auxiliary) alphabet. When we switch the current alphabet, a piece of the old alphabet becomes auxiliary. For example, switching from ASCII to Cyrillic — now there are 64 characters in the 'backup', containing Latin letters, digits, a space, and a comma (the most frequent inserts in non-ASCII texts). Switching back to ASCII — and the main part of Cyrillic will become the auxiliary alphabet.
Thanks to access to two alphabets, we can handle a large number of texts with minimal costs for switching alphabets (punctuation will most often lead us back to ASCII, but afterwards many non-ASCII characters will be drawn from the additional alphabet without needing to switch again).
Bonus: by defining the additional alphabet with a prefix 11xxxxxx and setting its initial offset to 0xC0, we achieve partial compatibility with CP1252. In other words, many (but not all) Western European texts encoded in CP1252 will appear the same in UTF-C.
However, there is a challenge: how to obtain an auxiliary alphabet from the main one? You can keep the same offset, but — alas — here the Unicode structure already plays against us. Very often, the main part of the alphabet is not at the beginning of the block (for example, the Russian capital 'А' has the code 0x0410, while the Cyrillic block starts with 0x0400). Therefore, by taking the first 64 characters into the 'stash', we may lose access to the tail of the alphabet.
To address this issue, I manually went through some blocks corresponding to various languages and indicated the offset of the auxiliary alphabet within the main one. The Latin alphabet was entirely reordered, akin to base64, as an exception.
Final Touches
Let's take one last look at where we can make further adjustments.
Note that the format 101xxxxx xxxxxxxx xxxxxxxx allows for encoding numbers up to 0x1FFFFF, while Unicode ends earlier, at 0x10FFFF. In other words, the last code point will be represented as 10110000 11111111 11111111. Thus, we can say that if the first byte appears as 1011xxxx (where xxxx is greater than 0), it signifies something else. For instance, we can add another 15 characters, constantly available for encoding in a single byte, but I chose a different approach.
Let's take a look at the Unicode blocks that currently require three bytes. Mostly, as mentioned, these are Chinese characters — but it's difficult to do anything with them, there are 21,000. Additionally, there's also Hiragana and Katakana — they are fewer, less than two hundred. And since we're mentioning the Japanese, emojis are also included (actually, they're scattered in many places within Unicode, but the main blocks fall within the range of 0x1F300 – 0x1FBFF). Considering that there are emojis that consist of several code points (for example, the emoji is made up of 7 codes!), it's quite unfortunate to spend three bytes on each (7×3 = 21 bytes for a single symbol, it's a nightmare).
Therefore, we select several chosen ranges corresponding to emojis, Hiragana, and Katakana, renumber them into a single continuous list, and encode them using two bytes instead of three:
1011xxxx xxxxxxxx
Great: the aforementioned emoji , consisting of 7 code points, takes up 25 bytes in UTF-8, and we managed to fit it into 14 (exactly two bytes for each code point). By the way, Habr refused to process it (in both the old and the new editor), so I had to insert it as an image.
Let's try to fix another issue. As we remember, the main alphabet is essentially the upper 6 bits, which we keep in mind and attach to the code of each subsequent decoded symbol. In the case of Chinese characters, which are in the block 0x4E00 – 0x9FFF, it is either bit 0 or 1. This is not very convenient: we will need to constantly switch the alphabet between these two values (i.e., spending three bytes each time). However, we note that in long mode we can subtract the number of characters we are encoding with short mode (after all the tricks described above, this is 10240) — then the range of characters will shift to 0x2600 – 0x77FF, and in this case, the upper 6 bits (out of 21) over this entire range will be equal to 0. Thus, sequences of characters will use two bytes per character (which is optimal for such a large range), without requiring alphabet switching.
Alternative solutions: SCSU, BOCU-1
Unicode experts, upon merely reading the title of the article, will likely rush to remind that directly among Unicode standards there is (SCSU), which describes an encoding method quite similar to what is described in the article.
I must confess: I only learned of its existence after deeply immersing myself in writing my own solution. Had I known about it from the very beginning, I would probably have tried to write its implementation instead of inventing my own approach.
Interestingly, SCSU uses ideas quite similar to those I arrived at independently (instead of the concept of 'alphabets', it uses 'windows', and there are more of them than I have). At the same time, this format also has its drawbacks: it is somewhat closer to compression algorithms rather than encoding. In particular, the standard provides many ways of representation but does not specify how to choose the optimal one — for this, the encoder must apply certain heuristics. Thus, an SCSU encoder that provides good packing will be more complex and cumbersome than my algorithm.
For comparison, I ported a relatively simple SCSU implementation to JavaScript — in terms of code volume, it turned out to be comparable to my UTF-C, but in some cases, it showed results that were tens of percent worse (though it might sometimes outperform it, but not by much). For example, texts in Hebrew and Greek were encoded by UTF-C a 60% better than SCSU (probably due to their compact alphabets).
I would like to add that besides SCSU, there is also another method for compact representation of Unicode — , but it aims for compatibility with MIME (which wasn't required for me), and uses a slightly different approach to encoding. I haven't evaluated its efficiency, but I think it is unlikely to be higher than that of SCSU.
Possible enhancements
The algorithm I provided is not universal by design (this is where my goals diverge most from those of the Unicode consortium). I have already mentioned that it was primarily developed for one task (storing a multilingual dictionary in a prefix tree), and some of its features may not be well-suited for other tasks. However, the fact that it is not a standard can also be a plus — you can easily modify it to fit your needs.
For example, one can obviously eliminate state, making the encoding stateless — simply by not updating variables offs, auxOffs and is21Bit in the encoder and decoder. In this case, it won't be possible to efficiently pack sequences of characters from the same alphabet, but there will be a guarantee that the same character is always encoded with the same bytes, regardless of context.
Furthermore, you can tailor the encoder to a specific language by changing the default state — for example, focusing on Russian texts, you can set at the beginning of the encoder and decoder offs = 0x0400 and auxOffs = 0. This especially makes sense in a stateless mode. Overall, this will resemble the use of an old eight-bit encoding, but it does not exclude the possibility of inserting characters from the entire Unicode as needed.
Another drawback mentioned earlier — in large text encoded in UTF-C, there is no quick way to find the boundary of a character nearest to an arbitrary byte. Cutting off the last, say, 100 bytes from the encoded buffer risks getting garbage that cannot be processed. While the encoding is not designed for storing multi-gigabyte logs, this can generally be corrected. A byte 0xBF should never occur as the first byte (but can be the second or third). Therefore, during encoding, a sequence can be inserted ¿¿¿ Every, say, 10 KB — then, if necessary, finding the boundary will be enough to scan the selected chunk until a similar marker is found. Following the last 0xBF will guarantee the start of the character. (When decoding, this three-byte sequence will, of course, need to be ignored.)
In summary
If you've read this far — congratulations! I hope you, like me, learned something new (or refreshed your memory) about how Unicode works.
Demonstration page. The advantages over both UTF-8 and SCSU are visible through the example of Hebrew.
The above findings should not be regarded as encroachments on standards. However, I am generally satisfied with the results of my work, and therefore I am happy to : for example, the JS library in minified form weighs only 1710 bytes (and has no dependencies, of course). As I mentioned earlier, you can familiarize yourself with its operation on the (there's also a set of texts that you can compare it with against UTF-8 and SCSU).
Lastly, I would like to reiterate the cases in which using UTF-C is not advisable:
- If your strings are sufficiently long (from 100-200 characters). In this case, you should consider using compression algorithms like deflate.
- If you need ASCII transparency, meaning it's important that no ASCII codes that were not in the original string appear in the encoded sequences. You can avoid this need if, when interacting with external APIs (for example, when working with a database), you transmit the encoding result as an abstract byte set, rather than as strings. Otherwise, you risk encountering unexpected vulnerabilities.
- If you want to be able to quickly find character boundaries at arbitrary offsets (for example, when part of the string is corrupted). This can be done, but only by scanning the string from the beginning (or applying the enhancement described in the previous section).
- If you need to perform operations on string contents quickly (sorting them, searching for substrings, concatenating), the strings need to be decoded first, which is why UTF-C will be slower than UTF-8 in these cases (but faster than compression algorithms). Since the same string is always encoded the same way, precise decoding comparison is not necessary, it can be done byte by byte.
Update: user posted a chart highlighting the applicability limit of UTF-C. It shows that UTF-C is more efficient than general-purpose compression algorithms (variations of LZW) as long as the packed string is shorter than ~140 characters (I should note that the comparison was conducted on one text; results may vary for other languages).
Source: habr.com
