From Bytes to Documents

The word résumé is six characters long. Stored as UTF-8, it occupies eight bytes, because each é needs two:

r     é        s     u     m     é
114   195 169  115   117   109   195 169

A program that reads those eight bytes but assumes they are in Windows-1252, the default encoding of many older Windows applications, will decode each of the two-byte sequences as two separate characters and produce résumé. Nothing fails. The indexer receives a valid string, tokenizes it, and stores fragments such as rã and sumã. Every query for résumé or resume will miss the document. Errors at this stage are invisible in the output and stay in the index until the document is decoded again from its original bytes, which is why the first step of text processing, turning bytes into a sequence of characters and deciding what those characters belong to, needs explicit checks.

This stage is sometimes called document delineation. It has four parts: decoding the character encoding, identifying the file format and extracting its text, identifying the language, and choosing the unit that will count as one document (Manning, Raghavan, and Schütze, 2008, §2.1).

Characters and encodings

A computer stores text as numbers. A character encoding is the rule that maps between them.

ASCII, standardized in the 1960s, assigns the numbers 0 to 127 to unaccented Latin letters, digits, punctuation, and control characters. It fits in seven bits and covers English, but not é, ß, ж, or 中. To cover other languages, many single-byte code pages used the remaining 128 values of an eight-bit byte for additional characters. ISO 8859-1 (Latin-1) and Windows-1252 cover Western European languages, while other code pages cover Cyrillic, Greek, and so on. A byte value such as 233 therefore means é in Latin-1 and something else entirely in a Cyrillic code page. The byte alone does not say which.

Unicode resolves this by assigning every character in every writing system a single number, its code point, written as U+ followed by hexadecimal digits: é is U+00E9, € is U+20AC, 中 is U+4E2D. A character as a reader perceives it can also be a sequence of code points: é can be stored either as U+00E9 or as e followed by U+0301, a combining acute accent, a difference that normalization must reconcile. Unicode defines what the characters are. Several encoding forms then define how code points become bytes:

UTF-8, designed by Ken Thompson and Rob Pike in 1992 (Pike and Thompson, 1993; Yergeau, 2003), uses one to four bytes per character. Its design has several properties that matter for text processing. Every ASCII file is already valid UTF-8, so existing English text needed no conversion. The first byte of each character announces how many bytes follow, and the following bytes always have the form 10xxxxxx, which can never be mistaken for a first byte, so a program can find character boundaries starting from any point in a stream. And byte sequences that are invalid UTF-8 are easy to detect, which makes UTF-8 one of the few encodings that can be partly recognized from the bytes alone. It has become the dominant encoding on the web and the usual internal representation in text processing systems. UTF-16, used internally by Windows, Java, and JavaScript, uses two bytes for most characters and four for the rest.

How UTF-8 packs a code point

The properties above follow directly from the bit layout that RFC 3629 specifies (Yergeau, 2003, §3). A code point is written in binary, and its bits are poured into the x positions of one of four patterns, chosen by how many bits the code point needs:

Take é, U+00E9. In binary, hexadecimal E9 is 11101001, eight bits, too many for the one-byte pattern, so the two-byte pattern is used. Its eleven payload positions take the code point padded on the left to eleven bits, 00011101001. The first five bits, 00011, fill the first byte and the remaining six, 101001, fill the second:

The euro sign U+20AC needs fourteen bits, more than the two-byte pattern's eleven, so it takes the three-byte pattern. Padded on the left to that pattern's sixteen payload positions it is 0010 0000 1010 1100, split four, six, and six: 0010, 000010, 101100. The bytes are 1110 0010 (E2), 10 000010 (82), and 10 101100 (AC), as in the table above. Reading in the other direction, a decoder that sees a byte beginning 1110 knows that exactly two continuation bytes beginning 10 must follow. That is what makes damage detectable.

Detecting the encoding

The decoder must know the encoding before it can produce characters, and documents do not always say. The evidence, roughly in order of reliability, is the following, although each format defines its own precedence rules:

1. Byte order marks: a few bytes at the start of some files that identify UTF-8, UTF-16, or UTF-32. Browsers following the HTML standard let a byte order mark override any declaration.
2. Declared encodings: the charset parameter of an HTTP Content-Type header, a <meta charset> tag in HTML, or the encoding declaration of an XML file. Declarations are sometimes wrong, for instance when a file was converted and its header was not.
3. Validity: a file that is not valid UTF-8 is certainly not UTF-8.
4. Statistical detection: the distribution of byte values and byte pairs differs characteristically among encodings and languages. Detectors such as the one built for the Mozilla browser compare a document's byte statistics with profiles of known encodings (Li and Momoi, 2001).

When decoding fails

Decoding errors take three common forms:

• Mojibake: valid text decoded with the wrong encoding, as in résumé. It produces plausible-looking garbage and passes every validity check.
• Replacement characters: a decoder that meets an invalid byte sequence can substitute U+FFFD, the replacement character (displayed as �). The text survives, but the affected words no longer match anything.
• Silent deletion: a decoder told to ignore errors drops the invalid bytes. résumé read as UTF-8 with errors ignored, from a file actually in Latin-1, becomes rsum.

All three can be produced, and their mechanics seen exactly, from the two byte sequences that encode résumé. In UTF-8 it is the eight bytes shown at the top of this article. In Latin-1 it is six bytes, 72 E9 73 75 6D E9, with é as the single byte E9. The table shows each failure and the tokens an indexer would then extract, using a tokenizer that lowercases and keeps runs of letters and digits:

The mojibake arises byte by byte. Windows-1252 maps every byte to a character, so the UTF-8 pair C3 A9 becomes two characters, à (C3) and © (A9), and the © then acts as a token boundary. The other two failures come from the validity rule. The Latin-1 byte E9 is 11101001, which in UTF-8 announces a three-byte character, but the next byte, 73 (01110011, the letter s), does not begin with 10. The decoder must reject the sequence and either substitute U+FFFD or drop the byte. The errors also compound. Text that has been mis-decoded once and saved again as UTF-8 can be mis-decoded a second time, and résumé becomes résumé. Each round makes the damage harder to reverse.

All three corrupt index terms without raising an error. A robust indexer records how each document was decoded, counts decoding errors, and reports documents with many of them, since a sudden rise usually means a misidentified encoding rather than damaged files. The pipeline article shows how a reasonable default in my own course code produced the third kind of failure.

Formats and text extraction

Before text can be tokenized it has to be extracted from the file format that contains it, and formats differ greatly in how much work that takes. The order of extraction and decoding depends on the format: an HTML file is decoded into characters before its markup is parsed, while a PDF stores text in its own internal encodings that only the extractor can interpret.

Identifying the format usually relies on a declared type (a file extension or a MIME type such as application/pdf) checked against the file's magic number, the signature in its first bytes. PDF files begin with %PDF-. Word, Excel, and PowerPoint files in their modern formats are ZIP archives, beginning with the bytes PK, that contain XML documents. Extensions are easily wrong. The signature is much harder to fake by accident, though it can be ambiguous (PK identifies only a ZIP archive, not which format is inside), so careful systems check both.

Extracting text raises different problems in each format:

• HTML mixes content with markup, scripts, styles, and boilerplate: navigation menus, footers, advertisements, and links repeated on every page of a site. Indexing boilerplate makes every page of a site match the words in its menu. Boilerplate detection classifies blocks of a page as content or not using shallow features such as text density and link density (Kohlschütter, Fankhauser, and Nejdl, 2010). HTML structure is also useful evidence: titles, headings, and the anchor text of links can be indexed as separate fields and weighted more heavily in ranking. Markup languages also escape some characters as entities, such as < for < and & for &, which must be decoded back into characters before tokenization.
• PDF describes where glyphs appear on a page, not the order in which they should be read. Unless the file is tagged with its logical structure, extractors must reconstruct reading order. In a two-column paper, reading straight across the page interleaves the two columns line by line. Extractors must also rejoin words hyphenated across line breaks, drop running headers, footers, and page numbers, and map ligature glyphs such as fi back to their letters. A scanned PDF contains only images of pages and needs optical character recognition, which introduces its own errors.
• Office documents are structured XML inside an archive, so their text is easier to extract, but embedded objects such as charts, images, and other documents need their own handling.

Undecoded entities give a concrete example of an extraction error that reaches the index. The Reuters-21578 newswire collection, as distributed with the NLTK toolkit and used for experiments throughout this wiki, still contains the SGML entity < wherever the original stories marked a company name with an angle bracket:

NATIONAL AMUSEMENTS AGAIN UPS VIACOM <VIA> BID
  Viacom International Inc said <National
  Amusements Inc> has again raised the value of its offer for

The entity occurs 8,694 times in 6,067 of the 10,788 stories. A tokenizer that keeps runs of letters turns every occurrence into the term lt, which becomes the sixteenth most frequent term in the collection and appears in 56 percent of the documents, more than most genuine words (see the frequency chart in stop words). It does no visible harm to a reader of the text, and it would go unnoticed in an index unless someone looked at the most frequent terms, which is one of the cheapest checks an indexer can run. The numbers were computed by the script tools/experiments/textproc/delineation.py.

Extraction should also collect metadata: title, author, creation date, and language where the format records them. Metadata supports fielded search and filtering, but embedded fields are often missing, stale, or inherited from a template (a report whose author is whoever created the template), so they need checking before they are trusted. General-purpose toolkits such as Apache Tika bundle format detection and extraction for hundreds of formats behind one interface.

Language identification

Most later stages are language-specific. A stop-word list, a stemmer, and a tokenizer for German are wrong for Finnish, and applying an English stemmer to French produces nonsense stems. The language of each document, and sometimes of each passage, must therefore be identified before those stages run.

Language identification is a classification problem, and short sequences of characters are strong evidence for it. Cavnar and Trenkle (1994) built a profile of each language from its most frequent character n-grams, typically sequences of one to five characters, and classified a document by comparing its own n-gram profile with each language's. Sequences such as th, ing, and the are characteristic of English, sch and ung of German, ção of Portuguese. The method needs no dictionary and tolerates misspellings. Later identifiers replaced the profile comparison with statistical or neural classifiers, but most still use character or byte n-grams as their features. Scripts give an even simpler first cut: text in Cyrillic, Greek, Hangul, or Devanagari can be narrowed down from the Unicode code-point ranges alone.

The method worked through

Cavnar and Trenkle's procedure is simple enough to follow by hand (1994, §3.1 and §3.2).

N-grams. The text is split into tokens consisting only of letters and apostrophes. Each token is padded with a blank in front and blanks behind, written here as _, and every n-gram of one to five characters is taken from it. For the word text this gives the letters themselves and

bigrams     _t  te  ex  xt  t_
trigrams    _te tex ext xt_ t__
4-grams     _tex text ext_ xt__ t___
5-grams     _text text_ ext__ xt___ t____

The padding makes the beginnings and endings of words visible: _t records a word starting with t, and e_ a word ending in e.

Profiles. All n-grams in a text are counted and sorted by frequency, most frequent first, and only their order is kept. A language's profile is the top of this list for a sample of text in that language. Cavnar and Trenkle observed that the top 300 or so n-grams of a profile are almost always characteristic of the language, and that from about rank 300 onward they begin to describe the subject of the text instead; in their language tests they compared profiles of 100 to 400 n-grams. The reproduction here keeps 300. To reproduce the method, profiles were built here for nine languages from the first half of each language's translation of the Universal Declaration of Human Rights, about 5,000 characters each. The first entries of the English profile are the single letters e t n a o i r s h l, then e_, the end of a word in e. Single letters dominate the top of every profile, and the n-grams that most distinguish languages come a little further down.

The out-of-place distance. A document's own profile is compared with each language profile. For every n-gram in the document's profile, the distance adds how far its rank there is from its rank in the language profile. An n-gram absent from the language profile adds a fixed maximum, here 300, the profile size; the paper leaves the exact value open. The language with the smallest total wins. The sentence Everyone has the right to education. has 152 distinct n-grams. The first eight, compared with the English and German profiles (ranks counted from 0):

Summed over all 152 n-grams, the distance is 20,332 to English and 33,797 to German. Most of the difference comes from absences: 44 of the sentence's n-grams are missing from the English profile and 103 from the German one, contributing 13,200 and 30,900. French is second-closest at 31,426. The method identifies a language mainly by which of its characteristic letter sequences a text contains, and only secondarily by how often.

Short texts and close relatives

The method has known weaknesses. Accuracy falls sharply on very short texts, such as queries, social media posts, and titles, because they contain few n-grams (Baldwin and Lui, 2010). Closely related languages such as Spanish and Portuguese, or Malay and Indonesian, share many n-grams. And many documents mix languages: an English paper quoting German, an email in Spanish with an English signature, a web page in Hindi with English navigation. Systems that care about such documents identify language per passage rather than per file.

The reproduction makes the first two weaknesses measurable. Snippets of whole words, at least a chosen number of characters long, were cut at random positions from the second half of each translation, which the profiles had not seen, and classified among the nine languages. Each run classified 50 snippets per language at each length, and 30 runs with different random seeds give the spread.

At 20 characters, about the length of a typical search query, the median accuracy is 85 percent (interquartile range 84 to 86), rising to 97 percent at 400 characters. Nearly all of the errors are confusions between close relatives. At 20 characters, Malay and Indonesian were mistaken for each other 996 times over the 30 runs, Spanish for Portuguese 234 times, and German for Dutch 71 times. Even full sentences can be close calls. Setiap orang berhak mendapat pendidikan ('everyone has the right to education') is assigned to Malay with a distance of 25,808 against 26,289 for Indonesian, and every word in it is used in both languages. These numbers come from small profiles, so they are lower than those of production identifiers trained on far more text, but the shape is general. Cavnar and Trenkle reported 99.8 percent accuracy on Usenet articles using profiles of 400 n-grams (§4.3), and they found accuracy only slightly lower for articles under 300 bytes. Articles of that size are still long compared with a query. The script that produced the figure, tools/experiments/textproc/delineation.py, also prints the full distance tables.

What counts as a document

The last decision is the document unit: what the index treats as one retrievable item. It is easy to take for granted that one file is one document, but the right unit depends on what people want returned (Manning, Raghavan, and Schütze, 2008, §2.1.2):

• An email may be one document, or its body and each attachment may be separate documents, or the message with all its attachments may be one. A mail archive file containing thousands of messages should certainly not be one document.
• A book as one document makes almost every query match it, somewhere among its hundreds of pages. Chapters, sections, or pages may be better units.
• A presentation exported as one HTML page per slide may need its pages recombined into a single document.
• A web page is usually one document, but a long page of frequently asked questions might be better treated as one document per question.

The choice involves the familiar trade-off. If units are too large, a query matches documents in which its terms appear far apart and unrelated, and precision falls. If units are too small, the terms of a query may be spread across several units, none of which matches the whole query, and recall falls. Passage retrieval offers a middle path. A system can index passages as separate units, or it can keep returning whole documents but score each one using its best-matching passages, so that a long document is credited for the part that actually discusses the query. Callan (1994) found that combining the best passage score with the whole-document score worked better than either alone. Structured formats such as XML make units explicit, since the markup can identify articles, sections, and paragraphs. Current retrieval-augmented generation systems face the same decision under a different name. They split documents into chunks for embedding, and the chunk size affects retrieval quality in the same way.

Whatever the unit, each one receives a document identifier, the number used in postings lists throughout the inverted index. The mapping from identifiers back to files, pages, or messages must be stored alongside the index, so that results can be shown to the user.

Summary

Before tokenization begins, a document has been decoded from bytes, extracted from its format, assigned a language, and cut into the units the index will return. Each of these steps can fail silently, and each failure removes words from the index or adds wrong ones. The next article, on tokenization, takes the decoded character sequence and splits it into tokens. The stemming article ends by following one sentence through every stage, from its bytes to its index terms.

References

• Baldwin, T., and Lui, M. (2010). Language identification: The long and the short of the matter. In Proceedings of NAACL-HLT 2010, 229–237.
• Callan, J. P. (1994). Passage-level evidence in document retrieval. In Proceedings of SIGIR 1994, 302–310.
• Cavnar, W. B., and Trenkle, J. M. (1994). N-gram-based text categorization. In Proceedings of the Third Annual Symposium on Document Analysis and Information Retrieval (SDAIR-94), 161–175.
• Kohlschütter, C., Fankhauser, P., and Nejdl, W. (2010). Boilerplate detection using shallow text features. In Proceedings of WSDM 2010, 441–450.
• Li, S., and Momoi, K. (2001). A composite approach to language/encoding detection. In Proceedings of the 19th International Unicode Conference.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 2.1. Cambridge University Press.
• Pike, R., and Thompson, K. (1993). Hello world or Καλημέρα κόσμε or こんにちは 世界. In Proceedings of the Winter 1993 USENIX Conference, 43–50.
• The Unicode Consortium. The Unicode Standard. https://www.unicode.org/standard/standard.html
• Yergeau, F. (2003). UTF-8, a transformation format of ISO 10646. RFC 3629, Internet Engineering Task Force.