Information-theoretic lower bound for succinct string dictionary of the Unicode Name property

Question

Background

The literature on succinct data structures refers often to the “information-theoretic lower bound” of encoding data, i.e., the minimum number of bits needed to store the data – a concept related to information-theory entropy. For instance, the definition of a succinct data structure is one that takes up $Z + o(Z)$ bits of space, where $Z$ is the “information-theoretic lower bound” of the data.

However, I am having difficulty figuring out how to actually use this concept for my purposes: creating a succinct string dictionary for Unicode Standard’s Name property. The best general definition that I can find is from Grossi and Ottaviano (2013), who define it as $\lceil \log_2 |𝐷| \rceil$, where $𝐷$ is the domain from which the data were originally drawn. They give the information-theoretic lower bound of a bitvector — having length $n$ and containing $m$ one-bits — as $\lceil \log_2 {𝑛 \choose 𝑚} \rceil$, which is equivalent to any subset (made of $𝑚$ items) drawn from a universe set (made of $𝑛$ possibilities).

Now, the Unicode Standard’s Name property injectively associates a unique immutable name (made of capital English alphanumeric characters, hyphens, and spaces: a repertoire of $38$ characters) with code points (integers ranging between $0$ and $\mathrm{10FFFF}$, in hexadecimal). For instance, the value of the code point $20$ (in hexadecimal) is SPACE, and the value of the code point $\mathrm{E01EF}$ is VARIATION SELECTOR-256. Name values never start or end with spaces, and they never start with numbers or hyphens. Not all code points have Name values. At the time of this writing, the longest name is ARABIC LIGATURE UIGHUR KIRGHIZ YEH WITH HAMZA ABOVE WITH ALEF MAKSURA ISOLATED FORM ($83$ characters long), and the shortest name is OX (two characters).

The Name property is defined by the text file UnicodeData.txt (along with several other rules that generate names for certain characters such as Hangul syllables, which will be ignored here). UnicodeData.txt is (as of March 2021) a highly repetitive 32297-line text file that looks like this:

0000;<control>;Cc;0;BN;;;;;N;NULL;;;;
0001;<control>;Cc;0;BN;;;;;N;START OF HEADING;;;;
0002;<control>;Cc;0;BN;;;;;N;START OF TEXT;;;;
0003;<control>;Cc;0;BN;;;;;N;END OF TEXT;;;;
0004;<control>;Cc;0;BN;;;;;N;END OF TRANSMISSION;;;;
0005;<control>;Cc;0;BN;;;;;N;ENQUIRY;;;;
0006;<control>;Cc;0;BN;;;;;N;ACKNOWLEDGE;;;;
0007;<control>;Cc;0;BN;;;;;N;BELL;;;;
0008;<control>;Cc;0;BN;;;;;N;BACKSPACE;;;;

…and then this:

001E;<control>;Cc;0;B;;;;;N;INFORMATION SEPARATOR TWO;;;;
001F;<control>;Cc;0;S;;;;;N;INFORMATION SEPARATOR ONE;;;;
0020;SPACE;Zs;0;WS;;;;;N;;;;;
0021;EXCLAMATION MARK;Po;0;ON;;;;;N;;;;;
0022;QUOTATION MARK;Po;0;ON;;;;;N;;;;;
0023;NUMBER SIGN;Po;0;ET;;;;;N;;;;;
0024;DOLLAR SIGN;Sc;0;ET;;;;;N;;;;;

…and then this:

004C;LATIN CAPITAL LETTER L;Lu;0;L;;;;;N;;;;006C;
004D;LATIN CAPITAL LETTER M;Lu;0;L;;;;;N;;;;006D;
004E;LATIN CAPITAL LETTER N;Lu;0;L;;;;;N;;;;006E;
004F;LATIN CAPITAL LETTER O;Lu;0;L;;;;;N;;;;006F;
0050;LATIN CAPITAL LETTER P;Lu;0;L;;;;;N;;;;0070;
0051;LATIN CAPITAL LETTER Q;Lu;0;L;;;;;N;;;;0071;

…and then later this:

090D;DEVANAGARI LETTER CANDRA E;Lo;0;L;;;;;N;;;;;
090E;DEVANAGARI LETTER SHORT E;Lo;0;L;;;;;N;;;;;
090F;DEVANAGARI LETTER E;Lo;0;L;;;;;N;;;;;
0910;DEVANAGARI LETTER AI;Lo;0;L;;;;;N;;;;;
0911;DEVANAGARI LETTER CANDRA O;Lo;0;L;;;;;N;;;;;
0912;DEVANAGARI LETTER SHORT O;Lo;0;L;;;;;N;;;;;

…until getting to the end:

E01EC;VARIATION SELECTOR-253;Mn;0;NSM;;;;;N;;;;;
E01ED;VARIATION SELECTOR-254;Mn;0;NSM;;;;;N;;;;;
E01EE;VARIATION SELECTOR-255;Mn;0;NSM;;;;;N;;;;;
E01EF;VARIATION SELECTOR-256;Mn;0;NSM;;;;;N;;;;;
F0000;<Plane 15 Private Use, First>;Co;0;L;;;;;N;;;;;
FFFFD;<Plane 15 Private Use, Last>;Co;0;L;;;;;N;;;;;
100000;<Plane 16 Private Use, First>;Co;0;L;;;;;N;;;;;
10FFFD;<Plane 16 Private Use, Last>;Co;0;L;;;;;N;;;;;

Specifically, each line denotes the data of a code point, in fields separated by semicolons: the first field contains the code point itself in hexadecimal, and the second field contains the Name property. If a line’s second field starts with a <, or if the field is blank, then there is no Name value for that code point. The other fields may be ignored for the purposes of the Name property.

Questions

I want to determine the information-theoretic lower bound of the Name property. My eventual goal is to create a succinct data structure that supports bidirectional remote-access lookup of the Name property, between code points and their names.

My questions are:

1. Does the Unicode Name property have two information-theoretic lower bounds (one for looking up Name values → code points and one for looking up code points → Name values)?
2. What is the information-theoretic lower bound(s) for looking up Name values → code points and for looking up code points → Name values?
3. Does the information-theoretic lower bound(s) change if Huffman coding or other kinds of data compression is applied to the Name values?

My current best guess is that the information-theoretic lower bound for the Unicode Name property (in both directions) is $\lceil \log_2 {𝑛 \choose 𝑚}\rceil \approx 1.4 \cdot 10^7 \approx 1.8 MB$, where $𝑛$ is the number of strings between $2$ and $83$ characters long from a $38$-character alphabet $(38^2 + 38^3 + … + 38^{83} \approx 1.4 \cdot 10^{131})$ and $𝑚$ is the number of Name values defined in UnicodeData.txt (a little less than its number of lines, which is 32297). But I’m almost certain that this is not correct—this is about as large as the entire size of UnicodeData.txt, in uncompressed UTF-8 encoding, and which contains much extraneous non-Name-related data.

Answer 1

The "information-theoretic lower bound" that you mention here is correct if you are encoding an element of a set, all of whose elements should be considered equiprobable. That doesn't really apply to this problem.

It's true that you could encode each character name as though it was a random element of the set of strings of length between 2 and 38 over the alphabet ABC...XYZ0123456789- . But an encoding that assigns the same number of bits to every member of that set will use the vast majority of its coding space on strings like FKCYE 7BAYBM1UIDHF3K3LN9P07IGWEMNTJH31MX2JJ-S3W LGKA0WFU-MHR67E5HD7CUMHWYEX1UW4EO9T, and only a tiny fraction on strings like LATIN CAPITAL LETTER A. You can do much better by assigning shorter bit sequences to "more probable" strings using a more sophisticated model that looks for the presence of words like LETTER, and not just length and alphabet.

An information-theoretic lower bound that is closer to what you're looking for is Kolmogorov entropy. The Kolmogorov entropy of a string is the shortest program (in some agreed-upon language) that outputs that string. You want a program that produces different outputs for different inputs, but that only requires a minor change to the definition. Unfortunately it's practically impossible to determine the Kolmogorov entropy of a string of any significant length. Also, Kolmogorov entropy doesn't say anything about the efficiency of the program; for long strings the shortest program is likely to be extremely slow.

---

My recommendation is to compress the concatenation of all of the strings with something like zlib or liblzma to get a target size, which will probably be in the 100K-200K range. This is not really a valid theoretical "bound" but it's probably a good approximation to how much you can reasonably compress your strings in practice.

If there is a decent compression library (like zlib) that you can use without needing to count its code size, then you might have success in compressing the strings in small groups, or compressing each string separately with a prebuilt dictionary containing common strings like LETTER . If not, you could use a Huffman code with each code mapping to some common string or single character. Picking a good set of strings is a black art, and I don't know much about it.