In ordinary usage, the word character refers to various things: a letter of an alphabet, a particular mark on a page, a symbol in a certain language, and so on. In Unicode, the term refers to the abstract form of a letter, but in a broad sense, so that it can encompass the fabulous diversity of the world's writing systems. More precise terminology is employed to cover particular forms of use.

A glyph refers to a particular rendition of a character (or composite character) on a page or screen. Different fonts create different glyphs. For example, the character “a” in 12-point Helvetica is one glyph; in 12-point Times it is another. Unicode does not distinguish between different glyphs. It treats characters as abstract members of linguistic scripts, not as graphic entities.

A code point is a Unicode value, specified by prefixing U+ to the numeric value given in hexadecimal. LATIN CAPITAL LETTER G (as the Unicode description goes) is U+0047. A code range gives a range of values: for example, the characters corresponding to ASCII are located at U+0000–U+007F and are called Basic Latin.

A code point does not necessarily represent an individual character. Some code points correspond to more than one character. For example, the code point U+FB01, which is called LATIN SMALL LIGATURE FI, represents the sequence f followed by i, which in most printing is joined together into a single symbol that is technically called a ligature, fi. Other code points specify part of a character. For example, U+0308 is called COMBINING DIAERESIS, and—at least in normal language—is always accompanied by another symbol to form a single unit, such as ü, ë, or ï.

The diaeresis is an example of what Unicode calls a combining character. To produce the single unit ü, the Latin small letter u (which is U+0075) is directly followed by the code for the diaeresis (which is U+0308) to form the sequence U+0075 U+0308. This is the handwriting sequence: first draw the base letter, then place the accent. Combining characters occupy no space of their own: they share the space of the character they combine with. They also may alter the base character's shape: when i is followed by the same combining diaeresis, the result looks like ï—omitting the original dot in the base letter. Drawing Unicode characters is not straightforward: it is necessary to be able to place accents over, under, and even through arbitrary characters—which may already be accented—and still produce acceptable spacing and appearance.

Because of the requirement to be round-trip compatible with existing character sets, Unicode can also have single code points that correspond to precisely the same units as character combinations—in fact, we have seen examples of these in the Latin-1 supplement shown in Figure 8.6a. This means that certain characters have more than one representation. For example, the middle letter of naïve could be represented using the combining character approach by U+0069 U+0308, or as a single, precomposed unit using the already prepared character U+00EF. Around 500 precomposed Latin letters, for instance, in the Unicode standard are superfluous, in that they can be represented using combining character sequences.

Combining characters allow many character shapes to be represented within a limited code range. They also help compensate for omissions. For example, the Guaraní Latin small g with tilde can be expressed without embarking upon a lengthy standardization process to add this previously overlooked character to Unicode. Combining characters are an important mechanism in intricate writing systems like Hangul, the Korean syllabic script. In Unicode, Hangul is covered by 11,172 precomposed symbols (codes AC00 and up in Table 8.1), each of which represents a syllable. Syllables are made up of Jamo, which is the Korean name for a single element of the Hangul script. Each Unicode Hangul syllable has an alternative representation as a composition of Jamo, and these are also represented in Unicode (codes 1100 and up in Table 8.1). The rules for combining Jamo are complex, however—which is why the precomposed symbols are included. But to type medieval Hangul even more combinations are needed, and these are not available in precomposed form.

The existence of composite and combining characters complicates the processing of Unicode text. When searching for a particular word, alternate forms must be considered. String comparison with regular expressions presents a knottier challenge. Even sorting text into lexicographic order becomes nontrivial. Algorithmically, all these problems can be reduced to comparing two strings of text—which is far easier if the text is represented in some kind of normalized form.

Unicode defines four normalized forms using two orthogonal notions: canonical and compatibility equivalence. Canonical equivalence relates code points to sequences of code points that produce the same character—as in the case discussed earlier, where the combination U+0069 U+0308 and the single precomposed character U+00EF both represent ï. Canonical composition is the process of turning combining character sequences into their precomposed counterparts; canonical decomposition is the inverse.

Compatibility equivalence relates ligatures to their constituents, such as the ligature fi (U+FB01) and its components f (U+0066) and i (U+0069). Decomposing ligatures simplifies string comparison, but the new representation no longer maintains a one-to-one character-by-character mapping with the original encoding.

The four normalized forms defined by the Unicode standard are

Certain Unicode characters are officially deprecated, which means that although they are present in the standard, they are not supposed to be used. This is how mistakes are dealt with. Once a character has been defined, it cannot be removed from the standard (because that would sacrifice backward compatibility); the solution is to deprecate it. For example, there are two different Unicode characters that generate the symbol Å, LATIN CAPITAL LETTER A WITH RING ABOVE (U+00C5) and ANGSTROM SIGN (U+212B); the latter is officially deprecated. Deprecated characters are avoided in all normalized forms.

Further complications, which we only mention in passing, are caused by directionality of writing. Hebrew and Arabic are written right to left, but when numbers or foreign words appear, they flow in the opposite direction; thus bidirectional processing may be required within each horizontal line. The Mongolian script can only be written in vertical rows. Another issue is the fact that complex scripts, such as Arabic and Indic scripts, include a plethora of ligatures, and contextual analysis is needed to select the correct glyph.

Because of the complexity of Unicode, particularly with regard to composite characters, three implementation levels are defined:

With future expansion in mind, the ISO standard formally specifies that Unicode characters are represented by 32 bits each. However, all characters so far envisaged fit into the first 21 bits. In fact, the Unicode consortium differs from the ISO standard by limiting the range of values prescribed to the 21-bit range U+000000–10FFFF. The discrepancy is of minor importance; we follow the Unicode route.

So-called planes of 65,536 characters are defined; there are 32 of them in the 21-bit address space. All the examples discussed above lie in the Basic Multilingual Plane, which represents the range U+0000–U+FFFF and contains virtually all characters used in living languages. The Supplementary Multilingual Plane, which ranges from U+10000–U+1FFFF, contains historic scripts, special alphabets designed for use in mathematics, and musical symbols. Next is the Supplementary Ideographic Plane (U+20000–U+2FFFF), which contains 40,000-odd additional Chinese ideographs that were used in ancient times but have fallen out of current use. The Supplementary Special-Purpose Plane (U+E0000–U+EFFFF), or Plane 14, contains a set of tag characters for language identification, to be used with special protocols.

Given the ISO 32-bit upper bound, the obvious encoding of Unicode uses 4-byte values for each character. This scheme is known as UTF-32. A complication arises from the different byte ordering that computers use to store integers: big-endian (where the 4 bytes in each word are ordered from most significant to least significant) versus little-endian (where they are stored in the reverse order), and the standard includes a mechanism to disambiguate the two.

The Basic Multilingual Plane is a 16-bit representation, so a restricted version of Unicode can use 2-byte characters. In fact, a special escape mechanism called surrogate characters (explained below) is used to extend the basic 2-byte representation to accommodate the full 21 bits. This scheme is known as UTF-16. It too is complicated by the endian question, and resolved in the same way. For almost all text, the UTF-16 encoding requires half the space needed for UTF-32.

We mention UTF-8 in Chapter 4. It is a variant of Unicode that extends ASCII—which, as we have seen, is a 7-bit representation where each character occupies an individual byte—in a straightforward way. UTF-8 is a variable-length encoding scheme where the basic entity is a byte. Being byte-oriented, this scheme avoids the endian issue that complicates UTF-32 and UTF-16. We explain the UTF methods more fully in the following sections.

Unicode encoding may seem complex, but it is straightforward enough to use in digital library software. Internally, every string can be declared as an array of 16-bit integers and used to hold the UTF-16 encoding of the characters. In Java this is exactly what the built-in String type does. In C and C++ the data type short is a 16-bit integer, so UTF-16 can be supported by declaring all strings to be unsigned short. Readability is improved by building a new type that encapsulates this. In C++ a new class can be built that provides appropriate functionality. Alternatively, a support library can be used, such as the type wchar_t defined in the ANSI/ISO standard to represent “wide” characters.

Further work is necessary to treat surrogate characters properly. But usually operation can be restricted to the Basic Multilingual Plane, which covers all living languages—more than enough for most applications. A further practical restriction is to avoid combining characters and to work with Unicode level 1, which makes it far easier to implement string matching operations.

Take the problem of accent folding. Speakers of languages like French and Spanish generally type words in the properly accented form, because without accents words look as strange to them as misspellings do to us. But in some circumstances it may be helpful to arrange for queries to match terms in documents whether or not accents are used—either in the document or the query. For example, in a digital library based on the publications of famous 17th-century mathematicians, documents containing the word Hôpital—a French mathematician, as well as the word for hospital—would be returned for the query Hopital. Equally, documents containing the unaccented term (perhaps caused by erroneous optical character recognition) would be returned for the query Hôpital, as well as ones containing the correct spelling.

If the input is Unicode level 1, the software need only check each character in turn, looking up its Unicode value in a table containing the fixed list of accented characters to see whether it should be elided. The situation is a little more complex when working with higher levels of Unicode representation—because combining characters must be checked too—but it is not overly complex.

Sorting Unicode strings into order is a more involved problem. English can be sorted simply and efficiently by numerically ordering a given list of strings by their ASCII values (ignoring, for now, complications like case difference), but things are more complex in an international setting. Although the code pages in Unicode present characters in logical groups that have a systematic ordering, extending the simple approach to sort strings according to each character's Unicode value quickly runs into difficulties. Corrections in later versions of the standard are necessarily out of order. In German, the letter ö precedes z in the alphabet, but the opposite convention is used in Swedish. In Slovak, ch is treated as a single letter and positioned after h. Even within a language, the rules for ordering can differ depending on the context. (In certain English-speaking countries, telephone directories treat names beginning with Mc and Mac as though they were the same, with MacAdam and McAdam appearing together and Maguire later on.) The situation is more complex for non-European languages, and for ideographic scripts like Chinese characters, the notion of ordering is not well defined—we return to this at the end of Section 8.4.

The good news is that Unicode defines an approach that takes all these issues into account: the so-called collation algorithm. This algorithm first transforms each string into the first of the four Unicode normal forms—the process of canonical decomposition. Then a lookup table is used to map the characters to a set of numeric values known as levels. Different levels are used to achieve different types of ordering, such as ignoring case or accents. The standard defines a 4-level scheme as the default. At the first level is the base character: such as the difference between an A and a B. Accent differences are taken into account in the second level, case differences at the third, and punctuation differences at the fourth, as illustrated in Table 8.3. The default table is then combined with a mechanism known as tailoring that allows for language-specific variations. The scheme is powerful enough to support the ordering described in Section 8.4, such as by the number of strokes in an ideograph.

Most programming languages provide library support for the Unicode collation algorithm. Although efficiency is a primary objective, generality comes at a price, and ordering strings this way carries a significant computation cost—far greater than accent folding, for example. This will become less of a concern over time as technological advances improve computer performance.

When writing Unicode characters to disk in a digital library, the 16-bit character representation is usually converted to UTF-8; the process is reversed when the disk is read. This normally reduces file size greatly and increases portability, because the files do not depend on the order in which the bytes are written.

Care is necessary to display and print Unicode characters properly. Most Unicode-enabled applications incorporate an arsenal of fonts and use a lookup table to map each character to a displayable glyph in a known font. Complications include composite Unicode characters and the direction in which the character sequence is displayed. Digital library software benefits immensely from the Unicode support already present in modern Web browsers.

During the 1970s the Indian Department of Official Languages began working on devising codes that catered to all official Indic scripts. A standard keyboard layout was developed that provides a uniform way of entering them all. Despite the very different scripts, the alphabets are phonetic and have a common Brahmi root that was used for ancient Sanskrit. The simultaneous availability of multiple Indic languages was intended to accelerate technological development and to facilitate national integration in India.

The result was ISCII, the Indian Script Code for Information Interchange. Announced in 1983 (and revised in 1988), it is an extension of ASCII that places new characters in the upper region of the code space. The code table supplies all the characters required in the Brahmi-based Indic scripts. Figure 8.9a shows the ISCII code table for the Devanagari script. Tables for the other scripts in Figure 8.8 are similar but contain differently shaped characters (and some entries are missing because there is no equivalent character in that script). The code table contains 56 characters, 10 digits (in the last line of Figure 8.9a), and 18 accents and combining characters. There are also three special escape codes, but we will not delve into their meaning here.

The Unicode developers adopted ISCII lock, stock, and barrel—they had to, because of their policy of round-trip compatibility with existing codes. They used different parts of the code space for the various scripts, which means that (in contrast to ISCII) documents containing multiple scripts can easily be represented. However, they also included some extra characters—about 10 of them—that in the original ISCII design were supposed to be formed from combinations of other keystrokes. Figure 8.9b shows the Unicode code table for the Devanagari script.

Most of the extra characters give a shorthand for frequently used characters, and they differ from one language to another. An example in Devanagari is the character Om, a Hindu religious symbol:

Although it is not part of the ISCII set, it can be created from the keyboard by typing the sequence of characters

The third character (ISCII E9) is a special diacritic sign called the Nukta (which phonetically represents nasalization of the preceding vowel). ISCII defines Nukta as an operator used to derive some little-used Sanskrit characters that are not otherwise available from the keyboard, such as Om. However, Unicode includes these lesser-used characters as part of the character set (U+0950 and U+0958 through U+095F).

Although the Unicode solution is designed to adequately represent all the Indic scripts, it has not yet found widespread acceptance. A practical problem is that these scripts contain numerous clusters of two to four consonants without any intervening vowels, called conjuncts. Conjuncts are similar to the ligatures discussed earlier, characters represented by a single glyph whose shape differs from the shapes of the constituents. Indic scripts contain far more of these, and there is a greater variation in shape. For example, the conjunct

is equivalent to the two-character combination

In this particular case, the conjunct happens to be defined as a separate code in Unicode (U+090C)—just as the ligature fi has its own code (U+FB01). The problem is that this is not always the case. In the ISCII design, all conjuncts are formed by placing a special character between the constituent consonants, in accordance with the design goal of a uniform representation for input of all Indic languages on a single keyboard. In Unicode, some conjuncts are given their own code—like the one above—but others are not.

Figure 8.9c shows the code table for a particular commercially available Devanagari font, Surekh (a member of the ISFOC family of fonts). Although there is much overlap, there is certainly not a one-to-one correspondence between the Unicode and Surekh characters, as can be seen in Figures 8.9b and c. Some conjuncts, represented by two to four Unicode codes, correspond to a single glyph that does not have a separate Unicode representation but does have a corresponding entry in the font. And in fact the converse is true: there are single glyphs in the Unicode table that are produced by generating pairs of characters. For example, the Unicode symbol

is drawn by specifying a sequence of three codes in the Surekh font.

We cannot give a more detailed explanation of why such choices have been made—it is a controversial subject, and a full discussion would require a book in itself. However, the fact is that the adoption of Unicode in India has been delayed because some people feel that it represents an uncomfortable compromise between the clear but spare design principles of ISCII and the practical requirements of actual fonts. They prefer to represent their texts in the original ISCII, because they regard it as conceptually cleaner.

The problem is compounded by the fact that today's word processors and Web browsers take a simplistic view of fonts. In reality, combination rules are required—and were foreseen by the designers of Unicode—that take a sequence of Unicode characters and produce the corresponding single glyph from Figure 8.9c. Such rules can be embodied in the “composite fonts” that were described in Section 4.5. But ligatures in English, such as fi, have their own Unicode entry, which makes things much easier. For example, the “insert-symbol” function of word processors implements a one-to-one correspondence between Unicode codes and the glyphs on the page.

The upshot is that languages like Hindi are not properly supported by current Unicode-compliant applications. A table of glyphs, one for each Unicode value, is insufficient to depict text in Hindi script. To make matters worse, in practice some Hindi documents are represented using ISCII while others are represented using raw font codes like that of Figure 8.9c, which are specific to the particular font manufacturer. Different practices have grown up for different scripts. For example, the majority of documents in the Kannada language on the Web seem to be represented using ISCII codes, whereas in the Malayalam language, diverse font-specific codes are used. Often, to read a new Malayalam newspaper in your Web browser you have to download a new font!

To accommodate Indic documents in a digital library that represents documents internally in Unicode, it is necessary to implement several mappings:

The first is a simple transliteration, because Unicode was designed for round-trip compatibility. However, both of the other mappings involve translating sequences of codes in one space into corresponding sequences in the other space (although all sequences involved are very short). Figure 8.10 shows a page produced by such a scheme.

Finding word boundaries in the absence of spaces is a non-trivial problem, and ambiguities often arise. To help you appreciate the problem, Figure 8.11a shows two interpretations of the same Chinese characters. The text is a play on the ambiguity of phrasing. Once upon a time, the story goes, a man embarked on a long journey. Before he could return home the rainy season began, and he took shelter at a friend's house. As the rains continued he overstayed his welcome, and his friend wrote him a note: the first line in Figure 8.11a. As shown in the second line, it reads “It is raining, the god would like the guest to stay. Although the god wants you to stay, I do not!” But before taking the hint and leaving, the visitor added the punctuation shown in the third line, making three sentences whose meaning is totally different—“The rainy day, the staying day. Would you like me to stay? Sure!”

This is an example of ambiguity related to phrasing, but ambiguity also can arise with word segmentation. Figure 8.11b shows a more prosaic example. For the ordinary sentence on the first line, there are two different interpretations, depending on the context: “I like New Zealand flowers” and “I like fresh broccoli.”

Written Chinese documents are unsegmented, and readers are accustomed to inferring the corresponding sequence of words almost unconsciously. Accordingly, machine-readable text is usually unsegmented. To render them suitable for full-text retrieval, a segmentation scheme should be used to insert word boundaries at appropriate positions prior to indexing.

One segmentation method is to use a language dictionary. Boundaries are inserted to maximize the number of the words in the text that are also present in the dictionary. Of course, there may be multiple valid segmentations, and heuristics are needed to resolve ambiguities.

Another method is based on the fact that text divided into words is more compressible than text that lacks word boundaries. You can demonstrate this with a simple experiment. Take a text file, compress it with any standard compression utility (such as gzip), and measure the compression ratio. Then remove all the spaces from the file, making it considerably smaller (about 17 percent smaller, because in English approximately one letter in six is a space). When you compress this smaller file, the compression ratio is noticeably worse than for the original file. Inserting word boundaries improves compressibility.

This fact can be used to divide text into words, based on a large corpus of hand-segmented training data. Between every two characters lies a potential space. A text compression model can be trained on presegmented text, and coupled with a search algorithm to interpolate spaces to maximize the overall compression. Section 8.5 (“Notes and sources”) at the end of this chapter points to a fuller explanation of the technique.

For non-Chinese readers, the success of the space-insertion technique can be illustrated by applying it to English. Table 8.4 shows original text at the top, complete with spaces. Below is the input to the segmentation procedure. Underneath that is the output of two segmentation schemes: one dictionary-based and the other compression-based. The training text was a substantial sample of English, although far smaller than the corpus used to produce the word dictionary.

Word-based segmentation fails badly when the words are not in the dictionary. In this case both crocidolite and Micronite are segmented incorrectly. In addition, inits is treated as a single word because it occurred that way in the text from which the dictionary was created, and in cases of ambiguity the algorithm prefers longer words. The strength of the compression-based method is that it performs well on unknown words. Although Micronite does not occur in the training corpus, it is correctly segmented. The compression-based method makes two errors, however. First, a space was not inserted into LoewsCorp because it happens to require fewer bits to encode than Loews Corp. Second, an extra space was added to crocidolite because that also reduced the number of bits required.

Several different schemes underlie printed Chinese dictionaries and telephone directories. Characters can be ordered according to the number of strokes they contain; or they can be ordered according to their radical, which is a core symbol on which they are built; or they can be ordered according to a standard alphabetical representation called Pinyin, where each ideograph is given a one- to six-letter equivalent. Stroke ordering is probably the most natural way of ordering character strings for Chinese users, although many educated people prefer Pinyin (not all Chinese people know Pinyin). This presents a problem when creating lists of Chinese text that are intended for browsing.

To help you appreciate the issues involved, Figure 8.12 shows title browsers for a large collection of Chinese documents. The rightmost button on the green access bar near the top invokes Figure 8.12a. Here, titles are ordered by the number of strokes in their first character, which is given across the top: the user has selected six. In all the titles that follow, the first character has six strokes. This is probably not obvious from the display, because you can only count the strokes in a character if you know how to write it. To illustrate this, the initial characters for the first and seventh titles are singled out and their writing sequence is superimposed on the screen shot: the first stroke, the first two strokes, the first three strokes, and so on, ending with the complete character, which is circled. All people who read Chinese know immediately how many strokes are needed to write any particular character.

There are generally more than 200 characters corresponding to a given number of strokes, almost any of which could occur as the first character of a title. Hence the titles in each group are displayed in a particular conventional order, again determined by their first character. This ordering is more complex. Each character has an associated radical, the basic structure that underlies it. For example, the radical in the upper example singled out in Figure 8.12a (the first title) is the pattern corresponding to the initial two strokes, which in this case form the left-hand part of the character. Radicals have a conventional ordering that is well known to educated Chinese; this particular one is number 9 in the Unicode sequence. Because this character requires four more strokes than its radical, it is designated by the two-part code 9.4. In the lower example singled out in Figure 8.12a (the seventh title), the radical corresponds to the initial three strokes, which form the top part of the character, and is number 40; thus this character receives the designation 40.3. These codes are shown to the right of Figure 8.12a but would not form part of the final display.

The codes form the key on which titles are sorted. Characters are grouped first by radical number, then by how many strokes are added to the radical to make the character. Ambiguity occasionally arises: the code 86.2, for example, appears twice. In such situations, the tie is broken randomly.

Stroke-based ordering is quite complex, and Chinese readers have to work harder than we do to identify an item in an ordered list. It is easy to decide on the number of strokes, but once a page like Figure 8.12a is reached, most people simply scan it linearly. A strength of computer displays is that they can at least offer a choice of access methods.

The central navigation button of Figure 8.12a invokes the Pinyin browser in Figure 8.12b, which orders characters alphabetically by their Pinyin equivalent. The Pinyin codes for the titles are shown to the right of the figure, but again would not form part of the final display. Obviously, this arrangement is much easier for Westerners to comprehend.