2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ $4.6 MB$ instead of $1.8 MB$ is not "far greater", it's only a factor of $\approx 2.5$ difference. It makes sense since you have plenty of short lines (length $\le 40$), while, if you select a random mapping from indices to names, a vast majority of names should have length $\ge 80$. $\endgroup$
    – user114966
    Mar 14 at 21:35
  • $\begingroup$ colab.research.google.com/drive/… The first plot is your string length distribution, the second plot is the actual name length distribution. Also note that your file has strings that are much longer than what you stated (e.g. there is a string with length 200). And finally, it's not true that $1.4⋅10^7≈4.6MB$. $\endgroup$
    – user114966
    Mar 14 at 21:55
  • $\begingroup$ This question refers multiple times to "the information-theoretic lower bound", but that doesn't make any sense in isolation. We can have a lower bound on some quantity; but you must specify what quantity you want a lower bound on. Do you want a lower bound on the number of bits it takes to represent a Unicode Name? (The answer to that will depend on what you assume about the distribution on Names, i.e., the likelihood of each Name.) On something else? $\endgroup$
    – D.W.
    Mar 15 at 5:13
  • $\begingroup$ @Dmitry: Regarding the megabyte estimation: Thanks, that was an arithmetic error. I’ve fixed it. Regarding the lengths of lines: Your Colaboratory notebook doesn’t split the lines by semicolons. Like the original post says, the names are in the second semicolon-delimited field. The longest such name, ARABIC LIGATURE UIGHUR KIRGHIZ YEH WITH HAMZA ABOVE WITH ALEF MAKSURA ISOLATED FORM, is 83 characters long. $\endgroup$
    – jschoi
    Mar 15 at 15:26
  • 1
    $\begingroup$ Perhaps you might either (1) understand how/why they care about that, and then summarize that in the question, or (2) ask a separate question about that relationship in general (the part you're still trying to understand). No, the minimum number of bits it takes to represent an element of a set (such as the set of all Names) does not depend on how that set is going to be used. $\endgroup$
    – D.W.
    Mar 15 at 16:51
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer; this helps clarify things a lot. So the answer to the original post’s third question is (kind of) yes: The “information-theoretic lower bound” (in the sense that the literature on succinct data structures uses the term) of a large dictionary of strings does depend on how compressible the strings are. Your comment that figuring out the bound for a lot of text is very hard helps me a lot, too. So far I’ve been able to squeeze the Name list down to 97 kB with Brotli and with encoding incremental code points (which will mostly repeat 1 more than the previous code point). $\endgroup$
    – jschoi
    Mar 15 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.