Table 4.1 shows the ASCII character set, with code values in decimal, octal, and hexadecimal. Codes 65–90 (decimal) represent the uppercase letters of the Roman alphabet, while codes 97–122 are lowercase letters. Codes 48–57 give the digits zero through nine. Codes 0–32 and 127 are control characters that have no printed form. Some of these govern physical aspects of the printer—for instance, BEL rings the bell (now downgraded to an electronic beep), BS backspaces the print head (now the cursor position). Others indicate parts of a communication protocol: SOH starts the header, STX starts the transmission. Interspersed between these blocks are sequences of punctuation and other nonletter symbols (codes 33–47, 58–64, 91–96, 123–126). Each code is represented in seven bits, which fits into a computer byte with one bit (the top one) free. In the original vision for ASCII, this was earmarked for a parity check.

ASCII was a great step forward. It helped computers evolve over the following decades from scientific number-crunchers and fixed-format card-image data processors to interactive information appliances that permeate all walks of life. However, it has proved a great source of frustration to speakers of other languages. Many different extensions have been made to the basic character set, using codes 128–255 to specify accented and non-Roman characters for particular languages. ISO 8859-1, from the International Organization for Standardization (the international counterpart of the American standards organization, ANSI), extends ASCII for Western European languages. For example, it represents é as the single decimal value 233 rather than the ASCII sequence “ e followed by backspace followed by ´.” The latter is alien to the French way of thinking, for é is really a single character, generated by a single keystroke on French keyboards. For non-European languages like Hebrew and Chinese, ASCII is irrelevant. For them, other schemes have arisen: for example, GB and Big-5 are competing standards for Chinese; the former is used in the People's Republic of China and the latter in Taiwan and Hong Kong.

As the Internet exploded into the World Wide Web and burst into all countries and all corners of our lives, the situation became untenable. The world needed a new way of representing text.

In 1988, Apple and Xerox began work on Unicode, a successor to ASCII that aimed to represent all the characters used in all the world's languages. As word spread, the Unicode Consortium, a group of international and multinational companies, government organizations, and other interested parties, was formed in 1991. The result was a new standard, ISO-10646, ratified by the International Organization for Standardization in 1993. In fact, the standard melded the Unicode Consortium's specification with ISO's own work in this area.

Unicode continues to evolve. The main goal of representing the scripts of languages in use around the world has been achieved. Current work is addressing historic languages, such as Egyptian hieroglyphics and Indo-European languages, and notations like music. A steady stream of additions, clarifications, and amendments eventually lead to new published versions of the standard. Of course, backward compatibility with the existing standard is taken for granted.

A standard is sterile unless it is adopted by vendors and users. Programming languages like Java have built-in Unicode support. Earlier ones—C, Perl, Python, to name a few—have standard Unicode libraries. Today's operating systems all support Unicode, and application programs, including Web browsers, have passed on the benefits to the end user. Unicode is the default encoding for HTML and XML. People of the world, rejoice!

Unicode is universal: any document in an existing character set can be mapped into it. But it also satisfies a stronger requirement: the resulting Unicode file can be mapped back to the original character set without any loss of information. This requirement is called round-trip compatibility with existing coding schemes, and it is central to Unicode's design. If a letter with an accent is represented as a single character in some existing character set, then an equivalent must also be placed in the Unicode set, even though there might be another way to achieve the same visual effect. Because the ISO 8859-1 character set mentioned above includes é as a single character, it must be represented as a single Unicode character—even though an identical glyph can be generated using a sequence along the lines of “ e followed by backspace followed by ´.”

Round-trip compatibility is an attractive way to facilitate integration with existing software and was most likely motivated by the pressing need for a nascent standard to gain wide acceptance. You can safely convert any document to Unicode, knowing that it can always be converted back again if necessary to work with legacy software. This is indeed a useful property. However, multiple representations for the same character can cause complications. These issues are discussed further in Chapter 8 (Section 8.2), which gives a detailed account of the Unicode standard.

In the meantime, it is enough to know that the most popular method of representing Unicode is called UTF-8. UTF stands for “UCS Transformation Format,” which is a nested acronym: UCS is Unicode Character Set—so called because Unicode characters are “transformed” into this encoding format. UTF-8 is a variable-length encoding scheme where the basic entity is a byte. ASCII characters are automatically 1-byte UTF-8 codes; existing ASCII files are valid UTF-8.

Unicode provides an all-encompassing form for representing characters, including manipulation, searching, storage, and transmission. Now we turn attention to document representation. The lowest common denominator for documents on computers has traditionally been plain, simple, raw ASCII text. Although there is no formal standard for this, certain conventions have grown up.

A text document comprises a sequence of character values interpreted in ordinary reading order: left to right, top to bottom. There is no header to denote the character set used. While 7-bit ASCII is the baseline, the 8-bit ISO ASCII extensions are often used, particularly for non-English text. This works well when text is processed by just one application program on a single computer, but when transferring between different applications—perhaps through e-mail, news, the Web, or file transfer—the various programs involved may make different assumptions. An alphabet mismatch often means that characters in the range 128–255 are displayed incorrectly.

Plain text documents are formatted in simple ways. Explicit line breaks are usually included. Paragraphs are separated by two consecutive line breaks, or else the first line is indented. Tabs are frequently used for indentation and alignment. A fixed-width font is assumed; tab stops usually occur at every eighth character position. Common typing conventions are adopted to represent characters like dashes (two hyphens in a row). Headings are underlined manually using rows of hyphens or equal signs. Emphasis is often indicated by surrounding text with a single underscore (_like this_), or flanking words with asterisks (*like* *this*).

Different operating systems have adopted conflicting conventions for specifying line breaks. Historically, teletypes were modeled after typewriters. The line-feed character (ASCII 10, LF in Table 4.1) moves the paper up one line but retains the position of the print head. The carriage-return character (ASCII 13, CR in Table 4.1) returns the print head to the left margin but does not move the paper. A new line is constructed by issuing carriage return followed by line feed (logically the reverse order could be used, but the carriage return line feed sequence is conventional, and universally relied upon). Microsoft Windows uses this teletype-oriented interpretation. However, Unix and the Apple Macintosh adopt a different convention: the ASCII line-feed character moves to the next line and returns the print head to the left margin. This difference in interpretation can produce a strange-looking control character at the end of every line: ^∧M or “carriage return.” (Observe that CR and M are in the same row of Table 4.1. Control characters in the first column are often made visible by prefixing the corresponding character in the second column with ^∧.) While the meaning of the message is not obscured, the effect is distracting.

People who use the standard Internet file transfer protocol (FTP) sometimes wonder why it has separate ASCII and binary modes. The difference is that in ASCII mode, new lines are correctly translated when copying files between different systems. It would be wrong to apply this transformation to binary files, however. Modern text-handling programs conceal the difference from users by automatically detecting which new-line convention is being used and behaving accordingly. Of course, this can lead to brittleness: if assumptions break down, all line breaks are messed up and users are mystified.

Plain text is a simple, straightforward, but impoverished representation of documents in a digital library. Metadata cannot be included explicitly (except, possibly, as part of the file name). However, automatic processing is sometimes used to extract title, author, date, and so on. Extraction methods rely on informal document structuring conventions. The more consistent the structure, the easier extraction becomes. Conversely, the simpler the extraction technique, the more seriously things break down when formatting quirks are encountered. Unfortunately you cannot normally expect complete consistency and accuracy in large plain text document collections.

Rapid searching is a core function of digital libraries that distinguishes them from physical libraries. The ability to search full text adds great value when large document collections are used for study or reference. Search can be used for particular words, sets of words, or sequences of words. Obviously, it is less important in recreational reading, which normally takes place sequentially, in one pass.

Before computers, full-text searching was confined to highly valued—often sacred—works for which a concordance had already been prepared. For example, some 300,000 word appearances are indexed in Cruden's concordance of the Bible, printed on 774 pages. They are arranged alphabetically, from Aaron to Zuzims, and any particular word can be located quickly using binary search. Each probe into the index halves the number of potential locations for the target, and the correct page for an entry can be located by looking at no more than 10 pages—fewer if the searcher interpolates the position of an entry from the position of its initial letter in the alphabet. A term can usually be located in a few seconds, which is not bad considering that simple manual technology is being employed. Once an entry has been located, the concordance gives a list of references that the searcher can follow up. Figure 4.1 shows some of Cruden's concordance entries for the word search.

In digital libraries searching is done by a computer, rather than by a person, but essentially the same techniques are used. The difference is that things happen faster. Usually it is possible to keep a list of terms in the computer's main memory, and the list can be searched in a matter of microseconds. When the computer's equivalent of the concordance entry becomes too large to store in main memory, secondary storage (usually a disk) is accessed to obtain the list of references, which typically takes a few milliseconds.

A full-text index to a document collection gives, for each word, the position of every occurrence of that word in the collection's text. A moment's reflection shows that the size of the index is commensurate with the size of the text, because an occurrence position is likely to occupy roughly the same number of bytes as a word in the text. (Four-byte integers, which are convenient in practice, are able to specify word positions in a 4-billion-word corpus. Conversely, an average English word has five or six characters and so also occupies a few bytes, the exact number depending on how it is stored and whether it is compressed.) We have implicitly assumed a word-level index, where occurrence positions give actual word locations in the collection. Space will be saved if locations are recorded within a unit, such as a paragraph, chapter, or document, yielding a coarser index—partly because pointers can be smaller, but chiefly because when a particular word occurs several times in the same unit, only one pointer is required for that unit.

A comprehensive index, capable of rapidly accessing all documents that satisfy a particular query, is a large data structure. Size, as well as being a drawback in its own right, also affects retrieval time, for the computer must read and interpret appropriate parts of the index to locate the desired information. Fortunately, there are interesting data structures and algorithms that can be applied to solve these problems. They are beyond the scope of this book, but references can be found in the “Notes and sources” section at the end of the chapter.

The basic function of a full-text index is to provide, for any particular query term, a list of all the units that contain it, along with (for reasons to be explained shortly) the number of times it occurs in each unit on the list. It's simplest to think of the “units” as being documents, although the granularity of the index may use paragraphs or chapters as the units instead—or even individual words, in which case what is returned is a list of the word numbers corresponding to the query term. And it's simplest to think of the query term as a word, although if stemming or case-folding is in effect, the term may correspond to several different words. For example, with stemming, the term computer may correspond to the words computer, computers, computation, compute, and so on; and with case-folding it may correspond to computer, Computer, COMPUTER, and even CoMpUtEr (an unusual word, but not completely unknown—for example, it appears in this book!).

When one indexes a large text, it rapidly becomes clear that just a few common words—such as of, the, and and—account for a large number of the entries in the index. People have argued that these words should be omitted, since they take up so much space and are not likely to be needed in queries, and for this reason they are often called stop words. However, some index compilers and users have observed that it is better to leave stop words in. Although a few dozen stop words may account for around 30 percent of the references that an index contains, it is possible to represent them in a way that consumes relatively little space.

A query to a full-text retrieval system usually contains several words. How they are interpreted depends on the type of query. Two common types, both explained in Section 3.4, are Boolean queries and ranked queries. In either case, the process of responding to the query involves looking up, for each term, the list of documents it appears in, and performing logical operations on these lists. In the case of Boolean queries, the result is a list of documents that satisfy the query, and this list (or the first part of it) is displayed to the user.

In the case of ranked queries, the final list of documents is sorted according to the ranking heuristic that is in place. As Section 3.4 explains, these heuristics gauge the similarity of each document to the set of terms that constitute the query. For each term, they weigh the frequency with which it appears in the document being considered (the more it is mentioned, the greater the similarity) against its frequency in the document collection as a whole (common terms are less significant). This is why the index stores the number of times each word appears in each document. A great many documents—perhaps all documents in the collection—may satisfy a particular ranked query (if the query contains the word the, all English documents would probably qualify). Retrieval systems take great pains to work efficiently even on such queries; for example, they use techniques that avoid the need to sort the list fully in order to find the top few elements.

In effect, the indexing process treats each document (or whatever the unit of granularity is) as a “bag of words.” What matters is the words that appear in the document and (for ranked queries) the frequency with which they appear. The query is also treated as a bag of words. This representation provides the foundation for full-text indexing. Whenever documents are presented in forms other than word-delineated plain text, they must be reduced to this form so that the corresponding bag of words can be determined.

Before an index is created, the text must first be divided into words. A word is a sequence of alphanumeric characters surrounded by white space or punctuation. Usually some large limit is placed on the length of words—perhaps 16 characters, or 256 characters. Another practical rule of thumb is to limit numbers that appear in the text to a far smaller size—perhaps four numeric characters, so that only numbers less than 9,999 are indexed. Without this restriction, the size of the vocabulary might be artificially inflated—for example, a long document with numbered paragraphs could contain hundreds of thousands of different integers—which negatively affects certain technical aspects of the indexing procedure. Years, however, which have four digits, should be preserved as single words.

In some languages, plain text presents special problems. Languages like Chinese and Japanese are written without any spaces or other word delimiters (except for punctuation marks). This causes obvious problems in full-text indexing: to get a bag of words, we must be able to identify the words. One possibility is to treat each character as an individual word. However, this produces poor retrieval results. An extreme analogy is an English-language retrieval system that, instead of finding all documents containing the words digital library, found all documents containing the constituent letters a b d g i l r t y. Of course the searcher will receive all sought-after documents, but they are diluted with countless others. And ranking would be based on letter frequencies, not word frequencies. The situation in Chinese is not so bad, for individual characters are far more numerous, and more meaningful, than individual letters in English. But they are less meaningful than words. Chapter 8 discusses the problem of segmenting such languages into words.

The result of the first stage, scanning, is a digitized image of each page. The image resembles a digital photograph, although its picture elements or pixels may be either black or white—whereas photos have pixels that come in color, or at least in different shades of gray. Text is well represented in black and white, but if the image includes nontextual material, such as pictures, or exhibits artifacts like coffee stains or creases, grayscale or color images will resemble the original pages more closely. Image digitization is discussed more fully in the next chapter.

When scanning page images you need to decide whether to use black-and-white, grayscale, or color, and you also need to determine the resolution of the digitized images—that is, the number of pixels per linear unit. A familiar example of black-and-white image resolution is the ubiquitous laser printer, which generally prints 600–1200 dots per inch. Table 4.2 shows the resolution of several common imaging devices.

The number of bits used to represent each pixel also helps to determine image quality. Most printing devices are black and white: one bit is allocated to each pixel. When putting ink on paper, this representation is natural—a pixel is either inked or not. However, display technology is more flexible, and computer screens allow several bits per pixel. Color displays range up to 24 bits per pixel, encoded as 8 bits for each of the colors red, green, and blue, or even 32 bits per pixel, encoded in a way that separates the chromatic, or color, information from the achromatic, or brightness, information. Color scanners can be used to capture images having more than 1 bit per pixel.

More bits per pixel can compensate for a lack of linear resolution and vice versa. Research on human perception has shown that if a dot is small enough, its brightness and size are interchangeable—that is, a small bright dot cannot be distinguished from a larger, dimmer one. The critical size below which this phenomenon takes effect depends on the contrast between dots and their background, but corresponds roughly to a very low-resolution (640 × 480) display at normal viewing levels and distances.

When digitizing documents for a digital library, think about what you want the user to be able to see. How closely does it need to resemble the original document pages? Are you concerned about preserving artifacts? What about pictures in the text? Will users see one page on the screen at a time? Will they want to magnify the images?

You will need to obtain scanned versions of several sample pages, chosen to cover the kinds and quality of images in the collection, and digitized to a range of different qualities (e.g., different resolutions, different gray levels, and color versus monochrome). You should conduct trials with end users of the digital library to determine what qualities are necessary for actual use.

It is always tempting to say that quality should be as high as it possibly can be. But there is a cost: the downside of accurate representation is increased storage space on the computer and—probably more importantly—increased time required for page access by users, particularly remote users. Doubling the linear resolution quadruples the number of pixels, and although this increase is ameliorated by compression techniques, users still pay a toll in access time. Your trials should take place on typical computer configurations using typical communications facilities, so that you can assess the effect of download time as well as image quality. You might also consider generating thumbnail images, or images at several different resolutions, or using a “progressive refinement” form of image transmission (see Section 5.3), so that users who need high-quality pictures can be sure they’ve got the right one before embarking on a lengthy download.

The second stage of digitizing library material is to transform the scanned image into a digitized representation of the page content—in other words, a character-by-character representation rather than a pixel-by-pixel one. This is known as optical character recognition (OCR). Although the OCR process itself can be entirely automatic, subsequent manual cleanup is invariably necessary and is usually the most expensive and time-consuming operation involved in creating a digital library from printed material. OCR might be characterized as taking “dumb” page images that are nothing more than images and producing “smart” electronic text that can be searched and processed in many different ways.

As a rule of thumb, a resolution of 300 dpi is needed to support OCR of regular fonts (10-point or greater), and 400 to 600 dpi for smaller fonts (9-point or less). Many OCR programs can tune the brightness of grayscale images appropriately for the text being recognized, so grayscale scanning tends to yield better results than black-and-white scanning. However, black-and-white images generate much smaller files than grayscale ones.

Not surprisingly, the quality of the output of an OCR program depends critically on the quality of the input. With clear, well-printed English, on clean pages, in ordinary fonts, digitized to an adequate resolution, laid out on the page in the normal way, with no tables, images, or other nontextual material, a leading OCR engine is likely to be 99.9 percent accurate or above—say 1 to 4 errors per 2,000 characters, which is a little under a page of this book. Accuracy continues to increase, albeit slowly, as technology improves. Replicating the exact format of the original image is more difficult, although for simple pages an excellent approximation will be achieved.

Unfortunately, the OCR operation is rarely presented with favorable conditions. Problems occur with proper names, with foreign names and words, and with special terminology—like Latin names for biological species. Problems are incurred with strange fonts, and particularly with alphabets that have accents or diacritical marks, or non-Roman characters. Problems are generated by all kinds of mathematics, by small type or smudgy print, and by overly dark characters that have smeared or bled together or overly light ones whose characters have broken up. OCR has problems with tightly packed or loosely set text where, to justify the margins, character and word spacing diverge widely from the norm. Hand annotation interferes with print, as does water-staining, or extraneous marks like coffee stains or squashed insects. Multiple columns, particularly when set close together, are difficult. Other problems are caused by any kind of pictures or images—particularly ones that contain some text; by tables, footnotes, and other floating material; by unusual page layouts; and by text in the image that is skewed, or lines of text that are bowed from the attempt to place book pages flat on the scanner platen, or by the book's binding if it interferes with the scanned text. These problems may sound arcane, but almost all OCR projects encounter them.

The highest and most expensive level of accuracy attainable from commercial service bureaus is typically 99.995 percent, or 1 error in 20,000 characters of text (approximately six pages of this book). Such a level is often most easily achieved by having the text retyped manually rather than by having it processed automatically by OCR. Each page is processed twice, by different operators, and the results are compared automatically. Any discrepancies are resolved manually.

As a rule of thumb, OCR becomes less efficient than manual keying when its accuracy rate drops below 95 percent. Moreover, once the initial OCR pass is complete, costs tend to double with each halving of the accuracy rate. However, in a large digitization project, errors are usually non-uniformly distributed over pages: often 80 percent of errors come from 20 percent of the page images. It may be worthwhile to have the worst of the pages manually keyed and to perform OCR on the remainder.

Human intervention is often valuable for cleaning up both the image before OCR and, afterward, the text produced by OCR. The actual recognition part can be time-consuming—maybe one or two minutes per page—and it is useful to perform interactive preprocessing for a batch of pages, have them recognized offline, and return them to the batch for interactive cleanup. Careful attention to such practical details can make a great deal of difference in a large-scale project.

Interactive OCR involves six steps: image acquisition, cleanup, page analysis, recognition, checking, and saving.

Let us return to the process of scanning the page images and consider some practical issues. Physically handling the pages is easiest if you can “disbind” the documents by cutting off their bindings (obviously, this destroys the source material and is only possible when spare copies exist). At the other extreme, originals cans be unique and fragile, and specialist handling is essential to prevent their destruction. For example, most books produced between 1850 and 1950 were printed on acid paper (paper made from wood pulp generated by an acidic process), and their life span is measured in decades—far shorter than earlier or later books. Toward the end of their lifetime they decay and begin to fall apart (see Chapter 9).

Sometimes the source material has already been collected on microfiche or microfilm, and the expense of manual paper handling can be avoided. Although microfilm cameras are capable of very high resolution, quality is compromised because an additional generation of reproduction is interposed; furthermore, the original microfilming may not have been done carefully enough to permit digitized images of sufficiently high quality for OCR. Even if the source material is not already in this form, microfilming may be the most effective and least damaging means of preparing content for digitization. It capitalizes on substantial institutional and vendor expertise, and as a side benefit the microfilm masters provide a stable long-term preservation format.

Generally the two most expensive parts of the whole process are handling the source material on paper, and the manual interactive processes of OCR. A balance must be struck. Perhaps it is worth the extra generation of reproduction that microfilm involves to reduce paper handling, at the expense of more labor-intensive OCR; perhaps not.

Microfiche is more difficult to work with than microfilm, because it is harder to reposition automatically from one page to the next. Moreover, it is often produced from an initial microfilm, in which case one generation of reproduction can be eliminated by digitizing directly from the film.

Image digitization may involve other manual processes apart from paper handling. Best results may be obtained by manually adjusting settings like contrast and lighting individually for each page or group of pages. The images may have to be manually deskewed. In some cases, pictures and illustrations will need to be copied from the digitized images and pasted into other files.

Any significant image digitization project will normally be outsourced. The cost varies greatly with the size of the job and the desired quality. For a small simple job, with material in a form that can easily be handled (e.g., books whose bindings can be removed), text that is clear and problem-free, and with few images and tables that need to be handled manually, you could expect to pay

for scanning and OCR, with a discount for large quantities. If difficulties arise, costs increase to many dollars per page. Using a third-party service bureau eliminates the need for you to become an expert in state-of-the-art image digitization and OCR. However, you will need to set standards for the project and to ensure that they are adhered to.

Most of the factors that affect digitization can be evaluated only by practical tests. You should arrange for samples to be scanned and OCR'd by competing companies and then compare the results. For practical reasons (because it is expensive or infeasible to ship valuable source materials around), the scanning and OCR stages may be contracted out separately. Once scanned, images can be transmitted electronically to potential OCR vendors for evaluation. You should probably obtain several different scanned samples—at different resolutions, different numbers of gray levels, from different sources, such as microfilm and paper—to give OCR vendors a range of different conditions. You should select sample images that span the range of challenges that your material presents.

Quality control is clearly a central concern in any image digitization project. An obvious quality-control approach is to load the images into your system as soon as they arrive from the vendor and to check them for acceptable clarity and skew. Images that are rejected are returned to the vendor for rescanning. However, this strategy is time-consuming and may not provide sufficiently timely feedback to allow the vendor to correct systematic problems. It may be more effective to decouple yourself from the vendor by batching the work. Quality can then be controlled on a batch-by-batch basis, where you review a statistically determined sample of the images and accept or reject whole batches.

Because it's labor-intensive, OCR work is often outsourced to developing countries like India, the Philippines, and Romania. Ten years ago, one of the authors visited an OCR shop in a small two-room unit on the ground floor of a high-rise building in a country town in Romania. It contained about a dozen terminals, and every day from 7:00 am through 10:30 pm the terminals were occupied by operators who were clearly working with intense concentration. There were two shifts a day, with about a dozen people in each shift and two supervisors—25 employees in all.

Most of the workers were university students who were delighted to have this kind of employment—it compared well with the alternatives available in their town. Pay was by results, not by the hour—and this was quite evident as soon as you walked into the shop and saw how hard people worked. They regarded their shift at the terminal as an opportunity to earn money, and they made the most of it.

This firm uses two different commercial OCR programs. One is better for processing good copy, has a nicer user interface, and makes it easy to create and modify custom dictionaries. The other is preferred for tables and forms; it has a larger character set with many unusual alphabets (e.g., Cyrillic). The firm does not necessarily use the latest version of these programs; sometimes earlier versions have special advantages.

The principal output formats are Microsoft Word and HTML. Again, the latest release of Word is not necessarily the one that is used. A standalone program is used for converting Word documents to HTML because it greatly outperforms Word's built-in facility. The people in the firm are expert at decompiling software and patching it. For example, they were able to fix some errors in the conversion program that affected how nonstandard character sets are handled. Most HTML is edited by hand, although they use a WYSIWYG (What You See Is What You Get) HTML editor for some of the work.

A large part of the work involves writing scripts or macros to perform tasks semiautomatically. Extensive use is made of Visual Basic for Applications (VBA). Although Photoshop is used for image work, they also employ a scriptable image processor for repetitive operations. MySQL, an open-source SQL implementation, is used for forms databases. Java is used for animation and for implementing Web-based questionnaires.

These people have a wealth of detailed knowledge about the operation of different versions of the software packages they use, and they constantly review and reassess the situation as new releases emerge. But perhaps their chief asset is their set of in-house procedures for dividing up work, monitoring its progress, and checking the quality of the result. They claim an accuracy of around 99.99 percent for characters, or 99.95 percent for words—an error rate of 1 word in 2,000. This is achieved by processing every document twice, with different operators, and comparing the result. In 1999, their throughput was around 50,000 pages/month, although the firm's capability is flexible and can be expanded rapidly on demand. Basic charges for ordinary work are around $1 per page (give or take a factor of two), but vary greatly depending on the difficulty of the job.

The New Zealand Digital Library undertook a project to put a collection of historical New Zealand Māori newspapers on the Web, in fully indexed and searchable form. There were about 20,000 original images, most of them double-page spreads. Figure 4.4 shows a sample image, an enlarged version of the beginning, and some of the text captured using OCR. The particular image shown was difficult to work with because some areas are smudged by water-staining. Fortunately, not all the images were so poor. As you can see by attempting to decipher it yourself, high accuracy requires a good knowledge of the language in which the document is written.

The first task was to scan the images into digital form. Gathering together paper copies of the newspapers would have been a massive undertaking, since the collection comprises 40 different newspaper titles that are held in a number of libraries and collections scattered throughout the country. Fortunately, New Zealand's national archive library had previously produced a microfiche containing all the newspapers for the purposes of historical research. The library provided us with access not just to the microfiche result, but also to the original 35-mm film master from which it had been produced. This simultaneously reduced the cost of scanning and eliminated one generation of reproduction. The photographic images were of excellent quality because they had been produced specifically to provide microfiche access to the newspapers.

Once the image source has been settled on, the quality of scanning depends on the scanning resolution and the number of gray levels or colors. These factors also determine how much storage is required for the information. After some testing, it was determined that a resolution of approximately 300 dpi on the original printed newspaper was adequate for the OCR process. Higher resolutions yielded no noticeable improvement in recognition accuracy. OCR results from a good black-and-white image were found to be as accurate as those from a grayscale one. Adapting the threshold to each image, or each batch of images, produced a black-and-white image of sufficient quality for the OCR work. However, grayscale images were often more satisfactory and pleasing for the human reader.

Following these tests, the entire collection was scanned by a commercial organization. Because the images were supplied on 35-mm film, the scanning could be automated and proceeded reasonably quickly. Both black-and-white and grayscale images were generated at the same time to save costs, although it was still not clear whether both forms would be used. The black-and-white images for the entire collection were returned on eight CD-ROMs; the grayscale images occupied 90 CD-ROMs.

Once the images had been scanned, the OCR process began. First attempts used Omnipage, a widely used proprietary OCR package. But a problem quickly arose: the Omnipage software is language-based and insists on utilizing one of its known languages to assist the recognition process. Because the source material was in the Māori language, additional errors were introduced when the text was automatically “corrected” to more closely resemble English. Although other language versions of the software were available, Māori was not among them, and it proved impossible to disable the language-dependent correction mechanism. In previous versions of Omnipage one can subvert the language-dependent correction by simply deleting the dictionary file (and the Romanian organization described above used an obsolete version for precisely this reason.) The result was that recognition accuracies of not much more than 95 percent were achieved at the character level. This meant a high incidence of word errors in a single newspaper page, and manual correction of the Māori text proved extremely time-consuming.

A number of alternative software packages and services were considered. For example, a U.S. firm offered an effective software package for around $10,000 and demonstrated its use on some sample pages with impressive results. The same firm offers a bureau service and was prepared to undertake the basic OCR for only $0.16 per page (plus a $500 setup fee). Unfortunately, this did not include verification, which had been identified as the most critical and time-consuming part of the process—partly because of the Māori language material.

Eventually, we located an inexpensive software package that had high accuracy and allowed for the provision of a tailor-made language dictionary. It was decided that the OCR process would be done in house, and this proved to be an excellent decision; however, it is heavily conditioned on the unusual language in which the collection is written and the local availability of fluent Māori speakers.

A parallel task to OCR was to segment the double-page spreads into single pages for the purposes of display, in some cases correcting for skew and page-border artifacts. Software was produced for segmentation and skew detection, and a semiautomated procedure was used to display segmented and deskewed pages for approval by a human operator. The result of these labors, turned in to a digital library, is described in Section 8.1.

Web culture has advanced at an extraordinary pace, creating a melee of incremental—and at times conflicting—additions and revisions to HTML, XML, and related standards. Figure 4.5 summarizes the main developments.

Although it has been retrospectively fitted with XML descriptions, HTML was created before XML was conceived and drew on the more general expressive capabilities of SGML. It was also forged in the heat of the browser wars, in which Web browsers sprouted a proliferation of innovative nonstandard features that vendors thought would make their products more appealing. As a result, browsers became forgiving: they process files that flagrantly violate SGML syntax. One example is tag scope overlap—writing < i> one < b> two </ i> three </ b> to produce one twothree—despite SGML's requirement that tags be strictly nested. During subsequent attempts at standardization, more tags were added that control typeface and layout, features deliberately excluded from HTML's original design.

The notion of style sheets was introduced to resolve the conflict between presentation and structure by moving formatting and layout specifications to a separate file. Style sheets purify the HTML markup to reflect, once again, nothing but document structure. Different documents can share a uniform appearance by adopting the same style sheet. Equally, different style sheets can be associated with the same document, for instance defining one for on-screen viewing and another for printing Style sheets can specify a sequence—a cascade—of inherited stylistic properties and are dubbed cascading style sheets.

The first specification of cascading style sheets was in 1996, and this was quickly followed by an expanded backward-compatible version two years later. Style sheets can be adapted to different media by including formatting commands that are grouped together and associated with a given medium—screen, print, projector, handheld device, and so on. Guided by the user (or otherwise), applications that process the document use the relevant set of style commands. A Web browser might choose screen for online display but switch to print when rendering the document in PostScript.

Modern versions of HTML promote the use of style sheets. Moreover, they encourage them by officially deprecating formatting tags and other elements that affect presentation rather than structure. This is accomplished through three subcategories to the standard. Strict HTML expresses layout exclusively through style sheets: frameset commands and all deprecated tags and elements listed in the standard are excluded. In transitional HTML, style sheets are the principal way of specifying layout, but to provide compatibility with older browsers deprecated commands are permitted, although framesets are prohibited. Frameset HTML permits frameset commands and deprecated elements. Modern HTML files declare their subcategory at the start of the document. The format also adds improved support for multidirectional text (not just left to right) and enhancements for improved access by people with disabilities.

An HTML subset called XHTML has been defined that obeys the stricter syntactic rules imposed by the XML metalanguage. For instance, tags in XML are case sensitive, so XHTML tags and attributes are defined to be lowercase. Attributes within a tag must be enclosed in quotes. Each opening tag must be balanced by a corresponding closing one (there are also single tags that combine opening and closing, with their own special syntax).

The power and flexibility of XML are further increased by related standards. Three are given in Figure 4.5 (there are many others). The extensible stylesheet language XSL described in Section 4.4 represents a more sophisticated approach than cascading style sheets: it can also transform data. The XML linking language XLink provides a more powerful method for connecting resources than HTML hyperlinks: it has bidirectional links, can link more than two entities, and associates metadata with links. Finally, XML Schema provides a rich mechanism for combining components and controlling the overall structure, attributes, and data types used in a document.

From a technical standpoint, it is easier to work with XML and its siblings than HTML because they conform to a strictly defined syntax and are therefore easier to parse. In reality, however, digital libraries have to handle legacy material gracefully. Today's browsers cope remarkably well with the wide range of HTML files: they take backward compatibility to truly impressive levels. To help promote standardization, an open source software utility called HTML Tidy has been developed that converts older formats. The process is largely automatic, but human intervention may be required if files deviate radically from recognized norms.

Modern markup languages use words enclosed in angle brackets as tags to annotate text. For example, < title> A really exciting story</ title> defines the title element of an HTML document. In HTML, tag names are case insensitive—< Title> is the same as < title>. For each tag, the language defines a “closing” version, which gives the tag name preceded by a slash character (/). However, closing tags can be omitted in certain situations—a practice that some decry as impure while others endorse as legitimate shorthand. For example, < p> is used to mark up paragraphs, and subsequent < p>s are assumed to automatically end the previous paragraph—no intervening </ p> is necessary. The shortcut is possible because nesting a paragraph within a paragraph—the only other plausible interpretation on encountering the second < p>—is invalid in HTML.

Opening tags can include a list of qualifiers known as attributes. These have the form name="value". For example, < img src="gsdl.gif" width="537" height="17"> specifies an image with source file name gsdl.gif and dimensions 537 × 17 pixels.

Because the language uses characters such as <, >, and " as special markers, a way is needed to display these characters literally. In HTML these characters are represented as special forms called entities and given names like & lt; for “less than” (<) and & gt; for “greater than” (>). This convention makes ampersand (&) into a special character, which is displayed by & amp; when it appears literally in documents. The semicolon needs no such treatment because its literal use and its use as a terminator are syntactically distinct. The same kind of special form can be used to specify Unicode characters beyond the ASCII range, such as & egrave; for è.

Figure 4.6 shows a sample page that illustrates several parts of HTML, along with a snapshot of how it is rendered by a Web browser. It contains “typical” code that you find on the Web, rather than exemplary HTML. Some attributes miss out double quotes (such as align and valign used in some of the table elements), and not all the elements stipulate all the attributes they should (e.g., two of the < img> tags are missing their alt attribute through which an alternative text description is given). The example would not even pass the test for transitional HTML, let alone strict HTML; however, as Figure 4.6b shows, the Web browser renders it just fine.

HTML documents are divided into a header and a body. The header gives global information: the title of the document, the character encoding scheme, any metadata. The < meta> tag is used in Figure 4.6a to acknowledge the New Zealand Digital Library Project as the document's creator. Creator imitates the Dublin Core metadata element (see Section 6.2) that is used to represent the name of the entity responsible for generating a document, be it a person, organization, or software application; however, there is no requirement in HTML to conform to such standards. Following the header is a comment and a command that sets the background to a Polynesian motif.

This particular page is laid out as two tables. The first controls the main layout. The second, nested within it, lays out the poem and the image of a greenstone pendant. The tags < tr> and < td> are used to mark table rows and cells, respectively. The list item < li> near the end illustrates various special characters. Most take the & …; form, but the last two ( ; and #) do not need to be escaped because their normal meaning is syntactically unambiguous. To generate the letter a with a line above (called a macron and used in the Māori language) the appropriate Unicode value is given in decimal (#257), demonstrating one way of specifying non-ASCII characters. The example illustrates several other features, including images specified by the < img> tag, paragraphs beginning with < p>, italicized words given by < i>, and a bulleted list introduced by < ul> (for “unordered list”), along with a < li> tag for each list item (just one in this case).

Hyperlinks are an important feature of HTML. In the example, the tag pair < a> … </ a> near the end defines a link anchor element. The document to link to—in this case, another page on the Web—is specified as an attribute. Hyperlinks can reference PDF documents, audio and video material, and many other formats—such as the Virtual Reality Modeling Language, VRML, which specifies a navigable virtual reality experience. Browsers display the anchor text—the text appearing between the start and end hyperlink tag—differently to emphasize the presence of a link. When the hyperlink is clicked, the browser loads the new document.

HTML was originally encoded in ASCII for transmission over byte-oriented protocols. Other encoding schemes are supported by setting the charset attribute in the header element to the appropriate encoding name. In Figure 4.6a, line 5 sets it explicitly to UTF-8, which, as mentioned in Section 4.1, is a representation scheme for Unicode. In fact UTF-8 (which is backward-compatible with ASCII) is now the default, and the behavior would be the same if the attribute were omitted.

HTML has many more features. For example, locally defined link anchors permit navigation within a single document. Fonts, colors, and page backgrounds can be specified explicitly. Forms can be created that collect data from the user—such as text data, fielded data, and selections from lists of items.

A mechanism called frames allows an HTML document to be tiled into smaller, independent segments, each an HTML page in its own right. A set of frames, called a frameset, can be displayed simultaneously. This is often used to add a navigation bar to every page of a Web site, along the top or down the side of the browser pane. When a link in the navigation bar is clicked, a new page is loaded into the main display frame, and the bar remains in place. Clicking on a link in the main display frame also loads the new page into the main frame.

Frames were introduced by one vendor during the browser wars and were soon supported by other browsers too. However, they have serious drawbacks. For instance, now that a browser can display more than one HTML document at a time, what happens when you create a bookmark? People often click around a site to reach an interesting document, then bookmark it in the usual way—only to find that the bookmark returns not to the intended page but to the point where the site splits into frames instead. This can be very frustrating.

Many of the effects for which frames were invented—such as persistent navigation bars—can also be accomplished by the newer and more principled mechanism of style sheets, avoiding the problems of frames; hence the three demarcated forms of HTML in more recent specifications of the standard: frameset, transitional, and strict, increasing in conformity to XML. We describe style sheets in Section 4.4.

As the lingua franca for the Web, HTML underpins virtually all digital library interfaces. Moreover, digital library source documents are often presented in HTML. This eliminates most of the difficulties associated with the plain text representation introduced earlier. For example, the HTML header disambiguates the character set, while the < br> and < p> tags disambiguate line and paragraph breaks.

To extract text from HTML documents for indexing purposes, the obvious strategy of parsing them according to a well-defined grammar quickly runs into difficulty. The permissive nature of Web browsers encourages authors to depart from the defined standard. A better way to identify and remove tags is to write them in the form of “regular expressions” (a scheme described in the next section), which generally achieves greater success for less effort, in this particular circumstance. An alternative is to use the very application that caused the complication in the first place: Web browsers. A plain text browser called lynx provides a fast and reliable method of extracting text from HTML documents—you give it a command-line argument ( dump) and a URL, and it dumps out the contents of that URL in the form of plain text.

As the example in Figure 4.6 illustrates, HTML allows metadata to be specified explicitly using < meta> tags. However, this mechanism is rather limited. For one thing, you might hesitate before tampering with source documents by inserting new metadata (perhaps determined separately, perhaps mined from the document content) in this way. When developing a digital library you need to consider whether it is wise (or even ethical, as discussed in Section 1.5) to add new information that cannot be disentangled from that present in the source document. Users might legitimately object if you serve up an altered version in place of the original.

Figure 4.7 shows a formatted list of information about United Nations agencies encoded in XML. For each agency, the file records its full name, an optional abbreviation, and the URL of a picture of its headquarters. Included with the name is the address of the headquarters, stored as an attribute.

The file contains three broad sections, separated by comments in the form <!-- . . . -->. Line 1 is a header: it uses the special notation <? . . . ?> to denote an application-processing instruction. This syntax originates in SGML, which uses it to embed information for specific application programs that process the document. Here it is used to declare the version of XML, the character encoding (UTF-8), and whether or not external files are used. Lines 5 to 19 dictate the syntactic structure in which the remainder of the file is expressed, in the form of a Document Type Definition (DTD). Lines 21 to 44 provide the content of the document.

The style of the content section is reminiscent of HTML. The tag specifications have the same syntactic conventions, and many tags are identical—examples are < Head>, < Title>, and < Body>. However, in lines 27 to 40 the markup creates structures that HTML cannot represent.

Because it is a metalanguage, XML gives document designers a great deal of freedom. In Figure 4.7 the main document structure resembles HTML, but this does not have to be the case. Different element names could be chosen, and different ways could be used to express the information. For example, Figure 4.7 gives the headquarters address as the hq attribute of the < Name> element. Alternatively, a new element could have been defined to contain this information. It could be constrained to appear immediately following the < Name> element, or left optional, or sited anywhere within the < Agency> element.

Structural decisions are recorded in the DTD (lines 5–19). DTD tags use the special syntax <! . . . > and express keywords in block capitals. For example, ELEMENT and ATTLIST are used to define elements and element attributes. Our document designer decided to capitalize the initial letter of all document elements and leave attributes in lowercase. This improves the legibility of Figure 4.7 considerably.

Line 5 starts the DTD, and the square bracket syntax [. . .] indicates that the DTD will appear in-line. (It must, for line 1 declares that the file stands alone.) Alternatively, the DTD could be placed in an external file, referred to by a URL—which is the usual practice.

New elements are introduced in lines 6 to 11 by the keyword ELEMENT, followed by the new tag name and a description of what the element may contain. A leaf is an element that comprises plain text, with no markup. This is accomplished through parsed character data ( #PCDATA ), in which special characters may be included. For example, when the < Title> tag defined on line 10 is used, markup characters may appear in the title's text, encoded in the familiar HTML way—& lt; & amp; and so on. (This convention originated in SGML.)

Lines 6 to 9 describe nonleaf structures. These are defined in a form known as a regular expression. Here a comma signifies an ordered sequence: line 6 declares that the top-level element < NGODoc> contains a < Head> element followed by a < Body> element. A vertical bar (|) represents a choice of one element from a sequence of named elements, and an asterisk (*) indicates zero or more occurrences. Thus < Body> (line 8) is a mixture of parsed character data and < Agency> elements where it is permissible for nothing at all to appear. A plus sign (+) means one or more occurrences, and a question mark (?) signifies either nothing or just one occurrence. Line 9 includes all four symbols |, *, +, and ?: it declares that < Agency> must include a name element, but that < Abbrev> is optional and there can be zero or more occurrences of < Photo> (the example is contrived: there are more concise ways of expressing the same thing). The inner pair of brackets bind these last two tags together, adding the extra stipulation that there must be at least one occurrence of the < Abbrev> and < Photo> specifications.

Attributes also give a set of possible values, but here there is no nesting. Lines 12 and 13 show an example. The attribute is signaled by the keyword ATTLIST, followed by the element to which it applies ( Name), the attribute's name ( hq), its type ( character data), and any appearance restrictions (this one is optional). Lines 16 to 18 show another example, which introduces two attributes of the element Photo. Line 17 states that the src attribute is required, while line 18 provides a default value (namely “A photo”) for the desc attribute.

In addition to & lt; and & amp; XML incorporates definitions for & gt; & apos; and & quot;. These are called entities, and new ones can be added in the DTD using the syntax ENTITY name "value". For instance, although XML does not have a definition for à as HTML does, one can be defined by <!ENTITY agrave "&#224;">, which relies on the Unicode standard for the numeric value. Entities are not restricted to single characters, but can be used for any excerpt of text (even if it is marked up). For example, <!ENTITY howto "How to Build a Digital Library"> is a shorthand way of encoding the title of this book.

If several elements shared exactly the same attributes, it would be tedious (and error-prone) to repeat the definitions in each element. This can be handled using a special type of entity known as a parameter entity. To illustrate it, Figure 4.8 shows a modified and slightly restructured version of the DTD for the document in Figure 4.7 that defines attributes ident and style under the name sharedattrib (lines 3–5), which is then used to bestow these attributes on the < Title>, < Abbrev>, and < Name> elements (lines 11–14). Parameter entities are signaled using the percent symbol (%) and provide a form of shorthand for use within a DTD.

Declaring the shared attribute style as NMTOKEN (line 4) restricts this attribute's characters to alphanumeric characters plus period (.), colon (:), hyphen (-), and underscore (_), where the first character must be a letter. Its twin ident is defined as ID (line 5), which is the same as NMTOKEN with the additional constraint that no two such attributes in the document can have the same value. ID therefore provides a mechanism for uniquely identifying elements, which in fact HTML enforces for an attribute with the particular name id. In XML, uniqueness can be bestowed on any attribute, whatever its name—such as ident.

DTDs also support enumerated types, although none are present in the example. It can also include lists of tokens separated by white space (NMTOKENS) and attributes that are references to ID attributes (IDREF).

A document that conforms to XML syntax but does not supply a DTD is said to be well formed. One that conforms to XML syntax and does supply a DTD is said to be valid—provided that the content does indeed abide by the syntactic constraints defined in the DTD. DTDs can be stored externally, replacing the bracketed section in Figure 4.7 lines 5–19 by a URL. This allows documents with the same structure to be shared within or between organizations.

XML allows you to define new languages, and makes it easy to develop parsers for them. Generic parsers are available that are capable of parsing any XML file, and—if a DTD is present—also check that the file is valid. However, merely parsing a document is of limited utility. The result of a parser is just a yes/no indication of whether the document conforms to the general rules of XML (and to the more specific DTD). Far more useful would be a way of specifying what the parser should do with the data it is processing. This is arranged by having it build a parse tree and provide a programming interface—commonly called an API or application program interface—that lets the user traverse the tree and retrieve the data it contains.

The result of parsing any XML file is a root node whose descendants reflect both textual content and nested tags. At each tag's node are stored the values of the tag's attributes. There is a cross-platform and cross-language API called the document object model (DOM) that allows you to write programs that access and modify the document's content, structure, and style.

XML is a powerful tool. It allows file formats within an organization—or a digital library—to be rationalized and shared. Furthermore, organizations can provide an explanation of the structures used in the form of a published machine-readable document. By formulating appropriate DTDs, for instance, different organizations can develop comprehensive formats for sharing information.

A notable example is the Text Encoding Initiative (TEI), founded in 1987, which developed a set of DTDs for representing scholarly texts in the humanities and social sciences. SGML was the implementation backbone, but the work has since been reconciled with XML. These DTDs are widely used by universities, museums, and commercial organizations to represent museum and archival information, classical and medieval works, dictionaries and lexicographies, religious tracts, legal documents, and many other forms of writing.

Examples are legion. The Oxford Text Archive is a nonprofit group that has provided long-term storage and maintenance of electronic texts for scholars over the last quarter-century. Perseus is a pioneering digital library project, dating from 1985, which focuses upon the ancient Greek world. Der Junge Goethe in Seiner Zeit is a collection of early works—poems, essays, legal writings, and letters—by the great German writer Johann von Goethe (1749–1832). The Japanese Text Initiative is a collaborative project that makes available a steadily increasing set of Japanese literature, accompanied by English, French, and German translations.

Various related standards increase XML's power and expand its applicability. Used on its own, XML provides a way of expressing a document's structural information, and/or metadata. Indeed, whether information is metadata or not is really a matter of perspective. Combined with additional standards, XML goes much further: it supports document restructuring, querying, information extraction, and formatting. The next section expands on the formatting standards, which equip XML with display capabilities comparable with HTML. More details appear in the appendix, entitled More on markup and XML, at the book's Web site: www.nzdl.org/howto.

Figure 4.9 shows what Figure 4.7 looks like when rendered by an XML-capable Web browser. The display is rudimentary; it shows the raw XML, typically color-coded to highlight different features of the language. Depending on the browser used, it might also be possible to open and close elements interactively.

Figure 4.10a gives a style sheet for the same example, and Figure 4.10b shows the result. Improved formatting makes the three individual agency records easier to read; a different font and type size are used to distinguish the title; and the background is set to white. The style sheet is included by adding the line

just after the XML header declaration in Figure 4.7 (the text of Figure 4.10a resides in a file called un_basic.css).

Style sheets specify rules using selector-declaration pairs, such as

The selector, here NGODoc, names an element type in the document. Several rules can apply to a given element—Figure 4.10a includes two for NGODoc. The declaration in braces gives formatting commands for the element—in this case setting the background to white. Declarations consist of property: value pairs, separated by semicolons if necessary.

There is an inheritance mechanism based upon the hierarchical document model that underpins XML. If the style sheet specifies formatting for an element, nested elements—ones beneath it in the document tree—inherit that specification. This makes style sheets concise and perspicuous. It is easy to override inherited behavior: just supply further rules at the appropriate level.

Although inheritance is the norm, some properties are noninheriting. What happens can be informally characterized as “intuitive inheritance” because exceptions to the rule make things behave more naturally. For example, if a background image is specified, it is tiled over the entire page. However, if nested elements inherit the background, they break up the pattern by restarting the image at every hierarchical block and subblock. Thus the background-image property is noninheriting. (You can override the default inheritance behavior by explicitly specifying certain properties to be inheritable or noninheritable.)

Returning to Figure 4.10a, the first rule causes the entire document to be formatted in a block. The second rule augments this element's formatting to set the background to white and the block width to 7.5 inches. The third declares the Title font to be Times, 25 point, boldface. The fourth places the Agency record in a paragraph block with 8-point spacing above and 3-point spacing below, typeset as 16-point Helvetica. The inheritance mechanism ensures that nested elements share this typeface.

In rule five, the selector contains the two element names Head and Body, and both are assigned top, left, and right margins of 6 points, 0.2 inch, and 5 mm, respectively. Normally a style sheet would not mix units in such a haphazard way. It is done so here to illustrate that CSS supports different units of measurement. Referring to the DTD that begins Figure 4.7, the Head specification applies to the document's Title, and the Body applies to the Agency node. (Since the two specifications are the same, this effect could have been achieved more concisely by setting these properties in the NGODoc node.) Rule six adds italics to Abbrev, which already inherits 16-point Helvetica from Agency.

The last two rules use a construct known as pseudo-elements. The : before and : after qualifications perform the operations before and after the Abbrev element is processed—in this case placing parentheses around the abbreviation. Other pseudo-elements give access to the first character and first line of a block. The related construct pseudo-classes can distinguish whether a link has been visited or not, and supports interactive responses to events, such as the cursor hovering over a location.

In general, the ordering of rules in a style sheet is immaterial because every rule that matches any selector is applied. However, it is possible for rules to be contradictory—for example, the background color may be set to both red and blue. The CSS specification includes an algorithm that resolves ambiguity based upon ordering and precedence values.

Style sheets can be used in HTML documents by inserting a < link> tag

into the document's head. CSS instructions can also be embedded directly into the HTML by enclosing them within < style type="text/css"> … </ style> tags.

XSL, the extensible stylesheet language for XML, transcends CSS by allowing the stylesheet designer to transform documents radically. Parts can be duplicated, tables of contents can be created automatically, lists can be sorted. A price is paid for this expressive power—complexity.

The XSL specification is divided into three parts: formatting objects (FO), XSL transformations (XSLT), and XPath (a way of selecting parts of a document). Formatting objects map closely to CSS instructions and use the same property names wherever possible. XSL transformations manipulate the document tree, while XPath selects parts to transform. We expand on these later in this section.

CSS can be combined with facilities such as Web-page scripting and the document object model mentioned in Section 4.3 (under “Parsing XML”) to provide comparable functionality to XSL—this combination is sometimes dubbed dynamic HTML. Experts fiercely debate which is the better approach. We think you should know about both, since the wider context in which you work often dictates the path you must tread. There is one key difference, however, between the two approaches. Because XSL is designed to work with XML, it cannot be used with all forms of HTML—because not all forms are XML compliant. CSS operates in either setting: HTML, for which it was designed, and XML, because there is no restriction in the tag names that CSS can provide rules for.

We introduce formatting in XSL by working through the examples used to illustrate CSS. However, XSL greatly extends CSS's functionality. For example, it includes a model for pagination and layout that extends the page-by-page structure of paper documents to provide an equivalent to the “frames” used in Web pages. Its terminology is internationalized. For example, padding-left becomes padding-start to make more sense when dealing with languages that are written right to left. Similar terms are used to control the space above, below, and at the end of text, although the old names are recognized for backward compatibility.

Figure 4.14 shows an XSL file for the initial version of the United Nations example. The XML syntax is far more verbose than its CSS counterpart in Figure 4.10a. Beyond the initial NGODoc declaration, it includes many of the keywords we saw in the earlier version. For example, CSS's font-size: 25pt specification for the Title node now appears between nested tags whose inner and outer elements include the attributes font-size=25pt and match=Title, respectively.

The style sheet is included in Figure 4.7 by adding the line

just after the XML header declaration (the text of Figure 4.14 resides in a file called un_basic.xsl), which is exactly what we did before with CSS. The result is a replica of Figure 4.10b, although both standards are complex and it is not uncommon to encounter small discrepancies.

Figure 4.14 begins with the obligatory XML processing application statement, followed by an < xsl:stylesheet> tag. As usual this is a top-level root element that encloses all the other tags. Its attributes declare two namespaces: one for XSL itself, called xsl; the other for Formatting Objects, called fo. Namespaces are an XML extension that keep sets of elements designed for particular purposes separate—otherwise confusion would occur if both XSL and FO happened to include a tag with the same name (such as block). Once the namespaces have been set up in Figure 4.14, < xsl:block> specifies the XSL block tag while < fo:block> specifies the Formatting Objects tag.

Namespaces also incorporate semantic information. If an application encounters a namespace declaration whose value is http://www.w3c.org/1999/XSL/Format, it interprets subsequent tag names according to a published specification. In the following discussion we focus on a subset of Formatting Object tags typically used in document-related XML style sheets. The full specification is more comprehensive.

Returning to Figure 4.14, the next tag sets the document's output type. XSL style sheets perform transformations: they are used to transform an XML source document into another document. Because our style sheet is designed to format the document using Formatting Object tags, the output is set to xml. Other choices are html—in which case all the fo: scoped tags in the XSL file would need to be replaced with HTML tags—and text.

To perform the transformation, the input document is matched against the style sheet and a new document tree built from the result. First the document's root node is compared with the XSL file's < xsl:template> nodes until one is found whose match attribute corresponds to the node's name. Then the body of the XSL template element is used to construct the tags in the output tree. If apply-templates is encountered, matching continues recursively on that document node's children (or as we shall see later, on some other selected part of the document), and further child nodes in the output tree are built as a result.

In the example, the document's root node matches < xsl:template match="NGODoc">. This adds several fo tags to the output tree—tags that initialize the page layout of the final document. Eventually < xsl:apply-templates> is encountered, which causes the document's children < Head> and < Body> to be processed by the XSL file. When the matching operation has run its course, the document tree that it generates is rendered for viewing.

The fourth template rule specifies its match attribute as Head |  Body to catch Head or Body nodes. Although it achieves the same effect as commas in CSS, this new syntax is part of a more powerful and general standard called XPath. The last template rule also introduces brackets around the abbreviation. The

is again an XPath specification. The “.” is a way of selecting the current position, or “here”—in this context it selects the text of the current node (Abbrev). This usage is adapted from the use of a period (.) in a file name to specify the current directory.

PostScript files comprise a sequence of drawing instructions, including ones that draw particular letters from particular fonts. The instructions are like this: move to the point defined by these x and y coordinates and then draw a straight line to here; using the following x and y coordinates as control points, draw a smooth curve around them with such-and-such a thickness; display a character from this font at this position and in this point size; display the following image data, scaled and rotated by this amount. Instructions are included to specify such things as page size, clipping away all parts of a picture that lie outside a given region, and when to move to the next page.

But PostScript is more than just a file format. It is a high-level programming language that supports diverse data types and operations on them. Variables and predefined operators allow the usual kinds of data manipulation. New operations can be encapsulated as user-defined functions. Data can be stored in files and retrieved. A PostScript document is more accurately referred to as a PostScript program. It is printed or displayed by passing it to a PostScript interpreter, a full programming language interpreter.

Being a programming language, PostScript allows print-quality documents that comprise text and graphical components to be expressed in an exceptionally versatile way. Ultimately, when interpreted, the abstract PostScript description is converted into a matrix of dots or pixels through a process known as rasterization or rendering. The dot structure is imperceptible to the eye—commonly available printers have a resolution of 600 dpi, and publishing houses use 1,200 dpi and above (see Table 4.2). This very book is an example of what can be described using the language.

Modern computers are powerful enough that a PostScript description can be quickly rasterized and displayed on the screen. This adds an important dimension to online document management: computers without the original software used to compose a document can still display the finished product exactly as it was intended to be displayed. Indeed, in the late 1980s one computer manufacturer took the idea to an extreme by developing an operating system (called NeXT) in which the display was controlled entirely from PostScript, and all applications generated their on-screen results in this form.

However, PostScript was not designed for screen displays. As is true for ASCII, limitations often arise when a standard is put to use in situations for which it was not designed. Just as ASCII is being superseded by Unicode, the Portable Document Format (PDF) has been devised as the successor to PostScript for online documents. Today the Apple Macintosh uses PDF throughout, just as the NeXT used PostScript.

PostScript supports two broad categories of fonts: base and composite fonts. Base fonts accommodate alphabets up to 256 characters. Composite fonts extend the character set beyond this point and also permit several glyphs to be combined into a single character—making them suitable for languages with large alphabets, such as Chinese, and with frequent character combinations, such as Korean.

In Figure 4.18b the findfont operator is used to set the font to Helvetica. This searches PostScript's font directory for the named font ( /Helvetica), returning a font dictionary that contains all the information necessary to render characters in that font. Most PostScript products have a built-in font directory with descriptions of 13 standard fonts from the Times, Helvetica, Courier, and Symbol families. Helvetica is an example of a base font format.

The execution of a show command such as (Welcome) show takes place in two steps. For each character, its numeric value (0–255) is used to access an array known as the encoding vector. This provides a name, such as /W (or, for nonalphabetic characters, a name like /hyphen). This name is then used to look up a glyph description in a subsidiary dictionary. A name is one of the basic PostScript types: it is a label that binds itself to an object. The act of executing the glyph object renders the required mark. The font dictionary is a top-level object that binds these operations together.

In addition to the built-in font directory, PostScript lets you provide your own graphical descriptions for the glyphs, which are then embedded in the PostScript file. You can also change the encoding vector.

It is useful to be able to extract plain text from PostScript files. To build a full-text index for a digital library, the raw text needs to be available. An approximation to the formatting information may be useful too—perhaps to display HTML versions of documents in a Web browser. For this, structural features like paragraph boundaries and font characteristics must be identified from PostScript.

PostScript allows complete flexibility in how documents are described—for example, the characters do not have to be in any particular order. In practice, actual PostScript documents tend to be more constrained. However, the text they contain is often fragmented and inextricably muddled up with other character strings that do not appear in the output. Figure 4.19 shows an example, along with the text extracted from it. Characters to be placed on the page appear in the PostScript file as parenthesized strings. But font names, file names, and other internal information are represented in the same way—examples can be seen in the first few lines of the figure. Also the division of text into words is not immediately apparent. Spaces are implied by the character positions rather than being present explicitly. Text is written out in fragments, and each parenthetical string sometimes represents only part of a word. Deciding which fragments to concatenate is difficult. Although heuristics might be devised to cover common cases, they are unlikely to lead to a robust solution that can deal satisfactorily with the variety of files found in practice.

This is why text extraction based on scanning a PostScript document for strings of text meets with limited success. It also fails to extract any formatting information. Above all, it does not address the fundamental issue that PostScript is a programming language whose output, in principle, cannot be determined merely by scanning the file—for example, in a PostScript document the raw text could be (and often is) compressed, to be decompressed by the interpreter every time the document is displayed. As it happens, this deep-rooted issue leads to a solution that is far more robust than scanning for text, can account for formatting information, and decodes any programmed information.

If a PostScript code fragment is prepended to a document and the document is then run through a standard PostScript interpreter, the placement of text characters can be intercepted, producing text in a file, rather than pixels on a page. The central trick is to redefine PostScript's show operator, which is responsible for placing text on the page. Regardless of how a program is constructed, all printed text passes through this operator (or a variant, as mentioned later). The new code fragment redefines it to write its argument, a text string, to a file instead of rendering it on the screen. Then, when the document is executed, a text file is produced instead of the usual physical pages.

Some early digital libraries were built from PostScript source documents, with contemporary versions shifting to PDF (discussed below) or a combination of the two. PostScript's ability to display print-quality documents using a variety of fonts and graphics on virtually any computer platform is a wonderful feature. Because the files are 7-bit ASCII, they can be distributed electronically using lowest-common-denominator e-mail protocols. And although PostScript predates Unicode, characters from different character sets can be freely mixed because documents can contain many different fonts. Embedding fonts in documents makes them faithfully reproducible even when sent to printers and computer systems that lack the necessary fonts.

The fact that PostScript is a programming language, however, introduces problems that are not normally associated with documents. A document is a program. And programs crash for a variety of obscure reasons, leaving the user with at best an incomplete document and no clear recovery options. Although PostScript is supposed to be portable, in practice people often experience difficulty printing PostScript files—particularly on different computer platforms. When a document crashes, it does not necessarily mean that the file is corrupt. Just as subtle differences occur among compilers for high-level languages like C++, the behavior of PostScript interpreters can differ in unpredictable ways. Life was simpler in the early days, when there was one level of Postscript and a small set of different interpreters. Now, with the proliferation of PostScript support, any laxity in the code an application generates may not surface locally, but instead cause unpredictable problems at a different time on a computer far away.

Trouble often surfaces as a stack overflow or stack underflow error. Overflow means that the available memory has been exceeded on the particular machine that is executing the document. Underflow occurs when an insufficient number of elements are left on the stack to satisfy the operator currently being executed. For example, if the stack contains a single value when the add operator is issued, a stack underflow error occurs. Other complications can be triggered by conflicting definitions of what a “new-line” character means on a given operating system—something we have already encountered with plain text files. Although PostScript classes both the carriage-return and line-feed characters ( CR and LF in Table 4.1) as white space (along with “tab” and “space,” HT and SPAC, respectively), not all interpreters honor this.

PostScript versions of word-processor files are invariably far larger than the native format, particularly when they include uncompressed images. Level 1 does not explicitly provide compressed data formats. However, PostScript is a programming language and so this ability can be programmed in. A document can incorporate compressed data so long as it also includes a decompression routine that is called whenever the compressed data is handled. This keeps image data compact, yet retains Level 1 compatibility. Drawbacks are that every document duplicates the decompression program, and decompression is slow because it is performed by an interpreted program rather than a precompiled one. These are not usually serious. When the document is displayed online, only the current page's images need be decompressed, and when it is printed, decompression is quick compared with the physical printing time. Note that PostScript based digital library repositories commonly include Level 1 legacy documents.

The ideas behind PostScript make it attractive for digital libraries. However, there are caveats. First, it was not designed for online display. Second, if advantage is taken of additions and upgrades, such as those embodied in comments, encapsulated PostScript, and higher levels of PostScript, digital library users must upgrade their viewing software accordingly (or, more likely, some users will encounter mysterious errors when viewing certain documents). Third, extracting text for indexing purposes is not trivial, and the problem is compounded by international character sets and creative typography.

PDF is a page description language that arose out of PostScript and addresses its shortcomings. It has precisely the same imaging model. Page-based, it paints sequences of graphical primitives, modified by transformations and clipping. It has the same graphical shapes—lines, curves, text, and sampled images. Again, text and images receive special attention, as befits their leading role in documents. The concept of current path, stroked or filled, also recurs. PDF is device independent and expressed in ASCII.

There are two major differences between PDF and PostScript. First, PDF is not a full-scale programming language. (In reality, as we have seen, this feature limits PostScript's portability.) Gone are procedures, variables, and control structures. Features like compression and encryption are built in—there is no opportunity to program them. Second, PDF includes new features for interactive display. The overall file structure is imposed, rather than being embodied in document-structuring conventions as with PostScript. This provides random access to pages, hierarchically structured content, and navigation within a document. Also, hyperlinks are supported.

There are many less significant differences. Operators are still postfix—that is, they come after their arguments—but their names are shorter and more cryptic, often only one letter, such as S for stroke and f for fill. To avoid confusion among the different conventions of different operating systems, the nature and use of white space are carefully specified. PDF files include byte offsets to other parts of the file and are always generated by software applications (rather than being written by hand as small PostScript programs occasionally are).

PDF has been through several versions since its introduction in 1993. In 1999, JavaScript support was added for greater interactivity (Version 1.3), and in 2000 (Version 1.5) support for JPEG 2000 was added (see Section 5.3). Adobe has released successive free versions of its Reader application (and associated browser plug-ins) to enable users to access the enhanced features. Although other readers are available, most users view PDF documents in Adobe applications. In 2008, PDF (Version 1.7) became an ISO international standard.

Different subsets of PDF have been defined to target specific user groups. Of particular relevance to digital librarians is the subset aimed at long-term archiving, known as PDF/A. PDF/A documents are intended to be self-contained and static. They require all fonts to be embedded, no use of external resources, no JavaScript actions, and device-independent color spaces. The first archival standard, PDF/A-1, is based on PDF version 1.4. The majority of applications that generate PDF provide options that allow users to save their document in whatever version they require. As with other evolving file formats, there is a trade-off between using the latest new features and ensuring that your documents can be widely read.

PDF is a sophisticated document description language that was developed by Adobe as a successor to PostScript. It addresses various serious deficiencies that had arisen with PostScript, principally lack of portability. While PostScript is a programming language, PDF is a format, and this bestows the advantage of increased robustness in rendering. Also, PostScript has a reputation for verbosity that PDF has avoided (PostScript now incorporates compression, but not all software uses it). Another feature of PDF is that metadata can be included in PDF files using the Extensible Metadata Platform, XMP (see Section 6.3).

PDF incorporates additional features that support online display. Its design draws on expertise that ranges from traditional printing to hypertext and structured document display. It is a complex format that presents challenging programming problems. However, a wide selection of software tools is readily available. There are utilities that convert between PostScript and PDF. Because they share the same imaging model, the documents’ printed forms are equivalent. But PDF is not a full programming language, so when converting PostScript to it, loops and other constructs must be explicitly unwound. In PostScript, PDF's interactive features are lost.

Today, PDF is the format of choice for presenting finished documents online. But PostScript is pervasive. Any application that can print a document can save it as a PostScript file, whereas standard desktop environments sometimes lack software to generate PDF. From a digital library perspective, collections (for example, CiteSeer for Scientific publications) frequently contain a mixture of PostScript and PDF documents. The problems of extracting text for indexing purposes are similar and can be solved in the same way. Some software viewers can display both formats.

Figure 4.22a recasts the Welcome example of Figure 4.18 in minimal RTF form. It renders the same text in the same font and size as the PostScript and PDF versions, although it relies on defaults for such things as margins, line spacing, and foreground and background colors.

RTF uses the backslash () to denote the start of formatting commands. Commands contain letters only, so when a number (positive or negative) occurs, it is interpreted as a command parameter—thus yr2001 invokes the yr command with the value 2001. The command name can also be delimited by a single space, and any symbols that follow—even subsequent spaces—are part of the parameter. For example, { title Welcome example} is a title command with the parameter Welcome example.

Braces {…} group together logical units, which can themselves contain further groups. This allows hierarchical structure and permits the effects of formatting instructions to be lexically scoped. An inheritance mechanism is used. For example, if an instruction is not explicitly specified at the current level of the hierarchy, a value that is specified at a higher level will be used instead.

Line 1 of Figure 4.22a gives an RTF header and specifies the character encoding (ANSI 7-bit ASCII), default font number (0), and a series of fonts that can be used in the document's body. The remaining lines represent the document's content, including some basic metadata. On line 3, in preparation for generating text, pard sets the paragraph mode to its default, while plain initializes the font character properties. Next, f1 makes entry 1 in the font table—which was set to Helvetica in the header—the currently active font. This overrides the default, set up in our example to be font entry 0 (Times Roman). Following this, the command fs28—whose units are measured in half points—sets the character size to 14 points.

Text that appears in the body of an RTF file but is not a command parameter is part of the document content and is rendered accordingly. Thus lines 4 through 8 produce the greeting in several languages. Characters outside the 7-bit ASCII range are accessed using backslash commands. Unicode is specified by u: here we see it used to specify the decimal value 228, which is LATIN SMALL LETTER A WITH DIAERESIS, the fourth letter of Akwäba.

This is a small example. Real documents have headers with more controlling parameters, and the body is far larger. Even so, this example is enough to illustrate that RTF, unlike PostScript, is not intended to be laid out visually. Rather, it is designed to make it easy to write software tools that parse document files quickly and efficiently.

RTF has evolved through many revisions—over the years its specification has grown from 34 pages to over 240. Additions are backward-compatible to avoid disturbing existing files. In Figure 4.22a's opening line, the numeric parameter rtf1 gives the version number, 1. The format has grown rapidly because, as well as keeping up with developments like Unicode in the print world, it must support an ever-expanding set of word-processor features, a trend that continues.

For much of its history the native Microsoft Word format has been proprietary and its details shrouded in mystery. Although Microsoft has published “as is” their internal technical manual for the Word 97 version, the format continued to evolve. Finally, in 2008, Microsoft made the specification publicly available. (Of course, this does not help people with legacy documents.) Native Word is primarily a binary format, and the abstract structures deployed reflect those of RTF. Documents include summary information, font information, style sheets, sections, paragraphs, headers, footers, bookmarks, annotations, footnotes, embedded pictures—the list goes on. The native Word representation provides more functionality than RTF and is therefore more intricate.

A serious complication is that documents can be written to disk in Fast Save mode, which no longer preserves the order of the text. Instead, new edits are appended, and whatever program reads the file must reconstruct its current state. If this feature has been used, the header marks the file type as “complex.”

Office Open XML is a new standard designed by Microsoft to represent, in human-readable XML form, Word and other Microsoft Office documents (spreadsheets, presentations, etc.). It was designed specifically for the features in Microsoft Office and is constrained by the need to be backward-compatible with documents created in the binary format. There has been vigorous discussion of the relative merits of OOXML and the Open Document (ODF) format (described in the next section). ODF was designed as a general office document markup language, unconstrained by the features of existing word processors. It is helpful to keep in mind the fact that these two languages were designed for different purposes and will probably be used in different ways.

Although the next section contains a brief technical account of ODF, we omit a technical description of OOXML. One reason is that these are extremely complex standards—the OOXML specification is more than 6,000 pages long, and ODF's contains 722 pages. Instead, we give a flavor of the debate, which is often heated. Critics of OOXML complain that (for example)

Proponents counter these criticisms by pointing out that naturally some OOXML elements are not supported by other software or other formats. Indeed, a project to translate documents from OOXML to ODF (funded in part by Microsoft) found that not all aspects of Office documents could be faithfully rendered. The problem basically stems from the fact that its design requirements force OOXML to capture all features of Microsoft Office, no matter how idiosyncratic or arcane they appear to others.

On the other side, critics of ODF complain that (for example)

In practice, its proponents say, ODF developers will naturally look to OpenOffice for canonical implementations that clarify features like spreadsheet formulae (which seem to have become a specific bone of contention). The code is there for anyone to view, and the XML output can be trivially inspected—providing a supplement to the standard in the form of an operational implementation. Of course, this is a very different philosophy from Microsoft's.

Although there are certainly differences between the two standards, advocates on both sides usually admit that the differences are not essential—certainly not when it comes to the interoperability and preservation of textual documents. Perhaps the real issue is the potential effect of each standard in the marketplace. ODF may be specified in less detail, but it offers the flexibility to create new products, which encourages competition. OOXML is aimed at reproducing Office documents and makes it easier for other products to work with Office—but does not encourage vendors to replace it.

At any rate, OOXML will be a great improvement over the native Word formats for designers of digital libraries.

The Open Document format can describe word-processor documents, spreadsheets, presentations, drawings, graphics, images, charts, mathematical formulas, and documents that combine elements of any of these. They are stored in files whose extensions contain “.od” followed by a single letter indicating the document type: . odt for text documents, . ods for spreadsheets, . odp for presentation programs, . odg for graphics.

A basic ODF document is an XML file with < document> as its root element. (Open Document files can also take the format of a ZIP compressed archive containing a number of files and directories as described below.) Figure 4.22b shows the Welcome example of Figure 4.18a in minimal ODF form. It renders the same text as the PostScript, PDF, and RTF versions, although it uses the default font and size. After the obligatory XML processing application statement, the document is defined by its root element, < office:document>, in the office namespace. This begins with four namespace definitions. In practice, ODF files usually define more namespaces—including ones for Formatting Objects (called fo) used in Section 4.4—but these four are enough to make this rudimentary example work. The namespaces that begin with urn are Uniform Resource Names (see Section 7.3).

Metadata can be stored along with documents, either with a set of metadata elements that are pre-defined in Open Document or using any user-defined metadata set. We have illustrated this by including two metadata elements specified in the Dublin Core standard (see Section 6.2). The namespace beginning with http:// is for the Dublin Core standard, and is only necessary because the example uses it to specify some metadata.

Following the metadata is the text of the document, nested inside the appropriate office tags. The < text:p> tag specifies a paragraph. As you can see, Unicode characters can be included using the ordinary # notation of HTML and XML.

In order to make the text appear in Helvetica font as it does in Figure 4.18a, the < text:p> statement near the end of Figure 4.22b needs to be augmented with a style-name attribute to read

To make this work, the Normal text style must be explicitly defined using a statement like

In reality the specifications are slightly more convoluted and verbose, which is why we have not included the details here. One cardinal advantage of XML-style document specifications over the others discussed previously is that it is very easy to create examples and study them to see what is going on.

LaTeX—pronounced la-tech or lay-tech—takes a completely different approach to document representation. Word processors present users with a “what you see is what you get” interface that is specifically intended to hide the gory details of internal representation. In contrast, LaTeX documents are expressed in plain ASCII text and contain typed formatting commands: they explicitly and intentionally give the user direct access to all the internal representation details. Any text editor on any platform can be used to compose a LaTeX document. To view the formatted document, or to generate hard copy, the LaTeX program converts it to a page description language—generally PostScript, but PDF and HTML are possible too.

LaTeX is versatile, flexible, and powerful. It can generate documents of exceptionally high typographical quality. The downside, however, is an esoteric syntax that many people find unsettling and hard to learn. It is particularly good for mathematical typesetting and has been enthusiastically adopted by members of the academic, scientific, and technical communities. It is a nonproprietary system, and excellent implementations are freely available.

Figure 4.24 shows a simple example. Commands in the LaTeX source (Figure 4.24a) are prefixed by the backslash character, . All documents have the same overall structure. They open with documentclass, which specifies the document's principal characteristics (article, report, book, etc.) and gives options, such as paper size, base font size, and whether to print single-sided or back-to-back. Then follows a preamble that gives an opportunity to set up global features before the document content begins. Here “packages” of code can be included. For example, usepackage{ epsfig} allows Encapsulated PostScript files, generally containing the artwork for figures, to be included.

The document content lies between begin{ document} and end{ document} commands. This begin … end structure is used to encapsulate many structural items: tables, figures, lists, bibliography, abstract. The list is endless, because LaTeX allows users to define their own commands. Furthermore, you can wrap up useful features and publish them on Internet sites so that others can download them and access them through usepackage.

As a document is written, most text is entered normally. Blank lines are used to separate paragraphs. A few characters carry special meaning and must therefore be “escaped” by a preceding backslash whenever they occur in the text; Figure 4.24 contains examples. Structural commands include section, which generates an automatically numbered section heading ( section* omits the numbering, while subsection, subsubsection, … are used for nested headings). Formatting commands include emph, which uses italics to emphasize text, and , which superimposes an umlaut on the character that follows. There are hundreds more.

The last part of Figure 4.24a specifies a mathematical expression. The begin{ displaymath} and end{ displaymath} commands switch to a mode that is tuned to represent formulas, which activates additional commands specially tailored to this purpose. LaTeX contains many shortcuts—for example, math mode can alternatively be entered by using dollar signs as delimiters.

We have mentioned spreadsheets and presentation files (such as PowerPoint) when discussing Office Open XML and the Open Document format. Both spreadsheets and presentation files have traditionally been encoded in proprietary binary file formats, like native Word documents. They may be presented to the user either in their native form or as PDF image files (or both). Of course, this presentation loses much information, notably the dynamic functionality of a spreadsheet involving formulas and the dynamic aspects of a presentation.

In order to index such files, the text can be extracted using the same procedure as for native-format text documents: use a Save As option to generate a more text-friendly form, such as ASCII (using the CSV or comma-separated values format) or XML for spreadsheets, and HTML or PDF for presentations. In future, open XML-based formats, such as OOXML or ODF (which, as we discuss above, apply to these files as well as to textual documents), will make life much easier.

E-mail documents are also candidates for inclusion in digital libraries. Early in the history of international computer networks, there were multiple e-mail clients having various incompatible formats. Seeking interoperability, the U.S. Department of Defense funded efforts to create standards. The result is a set of international standards for e-mail and e-mail extensions called Multipurpose Internet Mail Extensions (MIME). This is the de facto standard on the Internet.

However, corporate e-mail systems often use their own internal format and communicate with servers using a vendor-specific, proprietary protocol. The servers act as gateways for sending and receiving messages over the Internet, which involves undertaking any necessary reformatting. For mail sent and received within a single company, the entire transaction may take place within the corporate system.

Mail is not usually sent directly to a digital library but is imported from wherever it happens to be stored. This can be the user's e-mail client, or their server, or both places. There are two common standard formats for mailboxes ( Maildir and mbox), but several prominent clients use their own proprietary format and conversion software is needed to transfer mail between them—or to ingest it into digital libraries.

Internet e-mail messages have a header and body, separated by a blank line. The former contains metadata and is structured into fields, such as sender, receiver, date, title, and other information. It also includes the clock time and time zone, which together define the actual time the message was sent. The body contains the message content in the form of unstructured text, and sometimes ends with a signature block.

E-mails often contain attachments, which are files that are sent along with the message, encoded as part of the message to which they are attached. In the Internet MIME format, messages and their attachments are sent as a single multipart message, using an encoding scheme (called “base64”) for non-text attachments that represents binary information as printable ASCII.

There are many problems with e-mail as it used today. For example, a standard way to quote text is to start each line with the “>” character, possibly followed by a space. Unfortunately e-mail readers usually wrap lines to fit the screen size, or to some predetermined maximum length. Quoting makes the lines overflow. Figure 4.25 shows a message that has been quoted several times. The mailer has tried to wrap the lines, but it has put only a single quote on the continuation lines, not realizing that the text being wrapped has four levels of quotes. Messages become unintelligible after a few cycles of such mutilation.