Normalization Footprint Description

M. Davis, 2000-11-21

This document describes how much memory the different normalization forms occupy at a minimum (e.g., with an implementation tuned for minimal space consumption).

The code for a simple implementation of Normalization is about 100 lines (discounting comments) in Java, not including code for accessing data. It would take about the same amount of space in C, since it does not need to use any of the Java runtime support, nor even the String class.

The minimal data size is given below. NFC is highlighted because that will be of most interest (see W3C Character Model for the World Wide Web).

A breakdown of the table sizes used for each of these is given at the end of this document. In each case, an index of keys is binary-searched. If the key not is found, then the index is used to fetch a value from a result table. In the case of decomposition, that result value is used to index into a string array. The result is broken into two pieces: 3 bits for length, and 13 bits for starting offset. If the length is 7, then the string in the array is null terminated. Otherwise, the final result consists of the characters in the string array from startingOffset to startingOffset + length, inclusive. The code for doing this is around 30 lines.

Optimizations

In all cases, a trie table could be used for the main lookup instead of a binary search. Trie tables are somewhat larger, but have excellent performance characteristics. Accessing data by character in a typical trie table is simply:

result = data[index[ch>>7] + (ch & 0x7F)];

Optimized Normalization code would also be somewhat larger than the simple code. The simplest code optimization is to use the quickCheck described in Annex 8: Detecting Normalization Forms (which is about 20 lines of code) and do a quick scan of the source to see if normalization is required. For example, the table of suspect characters for NFC consists of  495 characters (Unicode 3.0). This takes an additional table of 4,492 bytes (using a byte-trie; 1,468 using a bit-trie).

For more information on trie tables, inversion tables, and other structures for use with Unicode, see http://www.macchiato.com: "Bits of Unicode". To see a Javascript implementation of Normalization, see NamePrep. For other implementations, see Annex 5 in UAX 15.

Decomposition (NFD)

• Maps pairs of 16-bit codes to strings
• Size in Unicode 3.0 = 1,311 keys, 2,609 resulting characters, string length = 4 (max), 1 (min)
• Simple space-conserving implementation
  • 1,311 * 2 for key, 1,311 * 2 for result, 2,609 * 2 for final result = 11,062 bytes
• Trie implementation (blocks of 128)
  • 11,020 for trie, 2,609 * 2 for final result = 16,238

Decomposition (NFKD)

• Maps pairs of 16-bit codes to variable length strings
• Size in Unicode 3.0 = 3,483 keys, 6,492 resulting characters, string length = 18 (max), 1 (min)
• Simple space-conserving implementation
  • 3,483 * 2 for key, 3,483 * 2 for result, 6,492 * 2 for final, 4 bytes for terminations = 26,918 bytes
• Trie implementation (blocks of 128)
  • 17,420 for trie, 6,492 * 2 for final result = 30,404

Canonical Class (All)

• Maps pairs of 16-bit codes to 8 bit values
• Size in Unicode 3.0 = 276 keys, same number of results
• Simple space-conserving implementation
  • 276 * 2 for key, 276 * 1 for result = 828 bytes
  • Inversion list might be a bit more compact (since there are ranges of characters with the same values)
• Trie implementation (blocks of 128)
  • 2,124 bytes

Composition (NFC, NFKC)

• Maps pairs of 16-bit codes to 16 bit values
• Fixed size (independent of Unicode version) = 918 keys, same number of results
• Simple space-conserving implementation
  • 918 * 4 for pairs, 918 * 2 for result = 5,508 bytes
• Hash table (estimated, load = 50%).
  • 11,000 bytes
  • Could also use a triple-index trie table. Somewhat larger, but more determinate performance.