Token Normalization

A document mentions the U.S.A., and a user searches for usa. A résumé says résumé, and the user types resume. One document says Windows, meaning the operating system, and another says windows, meaning the openings in a wall. After tokenization, each of these is a different sequence of characters, and an index that stores characters exactly will match none of the queries to the documents a person would expect.

Token normalization maps tokens that should match onto a single index term. It is where most decisions about what counts as "the same word" are made, apart from the more aggressive reductions of stemming. Each mapping trades precision for recall: merging U.S.A. and usa helps, but merging Windows and windows conflates an operating system with part of a house. This article describes the main kinds of normalization and the two ways of implementing them.

Equivalence classes and asymmetric expansion

Manning, Raghavan, and Schütze (2008, §2.2.3) describe two ways to make different tokens match.

The first creates equivalence classes. A normalization rule, such as "delete periods" or "convert to lowercase", is applied to every token in both documents and queries. All tokens that the rule maps to the same string fall into one class, and the index stores only that string. U.S.A. and USA both become usa, and either form in a query finds both forms in documents. The classes are implicit. Nobody lists them; they follow from the rules. This approach is simple and keeps the index small, but every class is symmetric. If Windows and windows are merged, a search for either finds both.

The second keeps distinctions in the index and expands the query instead. A table records, for each query term, which index terms it should match, and the relation need not be symmetric. Their example:

A user who types the capitalized Windows probably means the operating system, and gets only that. A user who types window or windows gets the plural and singular forms. Asymmetric expansion can express judgments that equivalence classes cannot, but it is more expensive: the index is larger because distinctions are kept, and each query term becomes several postings lists to merge. The cost of expansion is paid on every query, whereas equivalence classing is paid once at indexing time.

A five-document collection makes the difference concrete. The documents are:

1. Windows crashed again
2. clean the windows
3. a window seat
4. WINDOWS update failed
5. the window of opportunity

Under case folding as an equivalence class, the index holds window (documents 3 and 5) and windows (documents 1, 2, and 4). Under asymmetric expansion, the index keeps the case of each token, and the table above decides which terms each query reads:

Expansion gives the query Windows the operating-system story alone, while case folding cannot tell it from the query windows. Expansion also lets window reach the plural in document 2, which plain case folding does not, since singular and plural are different strings. But expansion misses document 4, whose all-capital WINDOWS appears nowhere in the table: an expansion table is only as complete as its entries. (The example is computed by tools/experiments/textproc/normalization.py.)

The two can be combined. Most systems apply a few safe rules, such as Unicode normalization and usually case folding, as equivalence classes, and handle riskier relations such as synonyms by query expansion, so that they can be changed without rebuilding the index.

Case folding

Case folding maps every letter to one case, usually lowercase. It is nearly universal in search, for a practical reason: people type queries in lowercase regardless of how the words are normally written. A user who types ferrari wants documents that say Ferrari.

Case sometimes carries meaning, and folding destroys it:

• General Motors and general motors, Bush and bush, Apple and apple;
• acronyms that coincide with words: MIT and mit (German for with), CAT (the company) and cat, US and us;
• Fed (the Federal Reserve) and fed.

A heuristic alternative lowercases only words whose capitalization is probably due to position, such as words at the start of a sentence or in all-capital headings, and keeps mid-sentence capitals as evidence of a proper noun. Truecasing goes further, using a statistical model to predict each word's correct case from its context (Lita, Ittycheriah, Roukos, and Kambhatla, 2003). In practice, because users rarely capitalize queries, plain lowercasing usually serves them better than preserving case would (Manning, Raghavan, and Schütze, 2008, §2.2.3).

What case folding merges in a real collection

Reuters-21578, a collection of 10,788 newswire stories, shows how much of the variation that case folding removes is harmless and how much is not. Split into tokens by the Unicode word-boundary rules described in tokenization, the collection has 60,203 distinct types. Lowercasing them leaves 49,530, a reduction of 17.7 percent. That reduction comes from 8,232 groups of types that differ only in case, and in 8,031 of those groups every form is one of three shapes, all lowercase, a capital first letter, or all capitals, such as oil, Oil, and OIL. That is the pattern that sentence-initial capitals and Reuters' all-capital headlines produce, so most of what folding merges is variation due to position.

The remaining risk is in words whose capitalized form is a different word. Counting occurrences in the collection:

The headline problem cuts both ways. IT in Reuters is almost always the pronoun in an all-capital headline, not information technology, so folding it is correct. But MAY, which occurs 233 times and nearly always in a headline, could be either the month or the verb, and after folding no later stage can tell. The counts come from tools/experiments/textproc/normalization.py. Merges like May and may are the case for the heuristic of folding only sentence-initial and headline capitals.

Case folding is not as simple as calling a lowercase function, outside the unaccented Latin alphabet. Unicode distinguishes lowercasing from case folding, which is designed for caseless matching. The German ß is already lowercase, so lowercasing Straße leaves it unchanged, but case folding maps it to strasse, so that it matches the capitalized spelling STRASSE. Turkish has both a dotted and a dotless i, each with its own capital. The capital İ (dotted) lowercases to i with a combining dot, two code points, unless the software applies Turkish-specific rules. Default folding also maps the undotted capital I to the dotted i, where Turkish requires the dotless ı. Search systems for such languages need language-aware folding.

The difference is visible at the level of code points. Python's lower() implements Unicode lowercasing and casefold() implements default case folding:

Code points are in hexadecimal without the U+ prefix. Case folding expands ß and also the fi ligature, but neither function turns full-width letters into ordinary ones. That is the job of the compatibility normalization described below, which is why pipelines apply normalization before folding.

Punctuation within tokens

Tokenization decides where tokens end. Normalization decides what to do with punctuation that remains inside them. Common rules delete periods in abbreviations (U.S.A. to usa, Ph.D. to phd) and handle hyphens consistently, for example mapping anti-discriminatory and antidiscriminatory to one form. Each rule has exceptions, such as numbers (3.14), version strings (2.0), and identifiers in which punctuation is significant (C++, .NET), so a system usually applies punctuation rules only to tokens that look like words.

Accents and diacritics

Diacritics are often omitted when people type, especially on keyboards that make them awkward. Removing them in the index lets resume match résumé, naive match naïve, and Universitat match Universität. The standard method uses Unicode decomposition: decompose each character into a base letter and combining marks, then delete the marks. Applied to Universität naïve résumé, it produces Universitat naive resume. Some letters, such as the Danish ø and the Polish ł, have no decomposition and need separate folding rules.

Removing diacritics conflates words that differ only in their marks, and in some languages those differences are lexical. Manning, Raghavan, and Schütze (2008, §2.2.3) note the Spanish peña ('cliff') and pena ('sorrow'). German readers often transliterate umlauts rather than dropping them, writing ae for ä, so Universitaet is as likely a query as Universitat. A good rule depends on how the users of a particular system actually type, which can be measured from query logs.

Unicode normalization

Unicode often provides more than one way to encode what is visibly the same text. é can be stored as the single code point U+00E9 or as the letter e followed by U+0301, a combining acute accent. The string résumé is six code points in the first form and eight in the second. The two look identical on screen, and they do not match as strings.

Unicode normalization forms, defined in Unicode Standard Annex #15, resolve this:

• NFC (canonical composition) converts text to precomposed characters where they exist. It is the usual storage form.
• NFD (canonical decomposition) separates base letters from combining marks. It is the form used for removing diacritics.
• NFKC and NFKD additionally apply compatibility mappings, which merge characters that differ only in presentation. The ligature fi becomes fi, full-width letters and digits common in East Asian text become ordinary ones (ＡＢＣ１ becomes ABC1), and superscript digits become ordinary digits.

The four forms applied to a few strings show what each one does. The numbers are lengths in code points:

The two spellings of résumé differ as strings and become identical under either composed form. The Ångström row shows a quieter case: Unicode has a separate code point, U+212B ANGSTROM SIGN, that is canonically equivalent to the letter Å (U+00C5), so even NFC replaces it. The last three rows change only under the compatibility forms. (Computed with Python's unicodedata module in tools/experiments/textproc/normalization.py.)

Many indexing pipelines apply NFKC, often combined with case folding, as an early normalization step. Compatibility mappings do discard some distinctions, such as a superscript ² in mathematical text, so a system that needs them indexes NFC text instead. Without NFKC, text extracted from PDFs, where ligatures are common, and from East Asian sources, where full-width forms are common, silently fails to match ordinary queries. The delineation article describes where these characters come from.

Other variation

Several further kinds of variation are usually handled by normalization or expansion:

• Spelling variants: British and American spellings (colour, color; organise, organize) can be merged by rules or by a variant table.
• Transliterations: names written in another script have several spellings in the Latin alphabet (Chebyshev, Tchebycheff). These are hard to reduce by rules, and phonetic matching and variant lists are the usual tools.
• Numbers and dates: recognizing March 20, 1991, 3/20/91, and 1991-03-20 as one date, and indexing it in a standard form, requires parsing rather than character substitution, and a locale convention, since 03/04/91 is March 4 in the United States and 3 April in much of Europe. Done reliably, it makes them interchangeable in queries and supports date-range search.
• Synonyms: car and automobile are different words with one meaning. Merging them in the index is rarely wise, since synonymy depends on context. Thesaurus-based query expansion is the usual approach, discussed with query expansion.

Choosing how far to normalize

Every rule in this article increases recall and risks precision, and the right set depends on the collection, the languages, and how users write queries. How much each rule merges also depends on the collection. Applied one after another to the Reuters tokens, the rules shrink the vocabulary as follows:

The two rules that change nothing are a property of this collection, not of the rules: Reuters contains a single non-ASCII character, so it has no accents to remove and no compatibility characters to map. On text extracted from PDFs, or on any collection in a language other than English, the same two steps merge many types. Deleting periods and apostrophes after case folding is the riskiest step in the sequence. It does merge true variants, but it also turns U.S (the tokenizer keeps the inner period and drops the final one; 5,675 occurrences) into us, the same term as the pronoun us (147) and the capitalized US (56), and it turns it's into its. Stemming, the subject of the next article, removes about as much again as case folding did.

Three principles help:

1. Apply equivalence-class rules identically to documents and queries. An equivalence class exists only if both sides are mapped to the same term.
2. Keep irreversible choices conservative. A distinction removed from the index cannot be restored at query time, while query expansion can be revised at any time. Rules that merge things that should rarely be merged, such as case for acronyms or diacritics in languages where they are lexical, are better handled at query time.
3. Measure. Query logs show how people type, and an evaluation collection shows whether a rule helps. The methods of evaluation apply to normalization rules as much as to ranking functions.

The next step, stemming and lemmatization, applies the same idea to word endings, reducing connected, connecting, and connection to one form.

References

• Lita, L. V., Ittycheriah, A., Roukos, S., and Kambhatla, N. (2003). tRuEcasIng. In Proceedings of ACL 2003, 152–159.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 2.2.3. Cambridge University Press.
• The Unicode Consortium. Unicode Standard Annex #15: Unicode Normalization Forms. https://www.unicode.org/reports/tr15/
• The Unicode Consortium. The Unicode Standard, section 5.18, Case Mappings. https://www.unicode.org/standard/standard.html