A retrieval model can only rank documents by what the index recorded about them, and the index records only what text processing produced. Every later topic in the course depends on decisions made here. These include how the bytes of a file are decoded, where one token ends and the next begins, which words are discarded, which variants are treated as the same term, and how the resulting terms are stored. The architecture article in Foundations showed this pipeline on four sentences. This topic examines each stage properly.
The stages fall into two groups. Text processing turns a file into a sequence of terms. It decodes the bytes into characters and decides what counts as a document. It then splits the characters into tokens, removes or keeps very common words, and normalizes tokens into the equivalence classes that become index terms. Its errors are usually silent: a mis-decoded character or an overly aggressive stemmer does not raise an error, it just causes queries to miss relevant documents or match wrong ones. Indexing organizes the terms into an inverted index, the data structure behind nearly every search engine, and makes that structure buildable and storable at scale. Two statistical regularities of language, Zipf's law and Heaps' law, connect the two groups. They explain why a few words dominate every collection, why the vocabulary keeps growing, and why compression works.
Throughout the topic the central trade-off is the one introduced in What information retrieval is. Every normalization that helps a query match more relevant documents also risks matching irrelevant ones.
Articles
From bytes to text
- From bytes to documents: character encodings and how decoding fails, format identification and text extraction, language identification, and choosing the unit that counts as a document.
Tokens and terms
- Tokenization: words, tokens, types, and terms; hyphens, apostrophes, numbers, and names; languages without spaces and with long compounds; and subword tokenization.
- Term statistics: Zipf's law and Heaps' law: how term frequencies are distributed, how vocabulary grows with collection size, both laws fitted to the Reuters-21578 news collection, why Heaps' law follows from Zipf's, and what both laws imply for indexing.
- Stop words: how stop lists are built, what removing common words gains and costs, and why web search largely abandoned them.
- Token normalization: equivalence classes, case folding, accents and Unicode normalization, and asymmetric expansion.
- Stemming and lemmatization: reducing words to shared stems or dictionary forms, the main stemming algorithms, and what experiments show about their effect on retrieval.
- The Porter stemmer: the measure of a stem, the five steps of rules, and worked examples of the algorithm's successes and failures.
- Spelling correction and phonetic matching: edit distance and its dynamic-programming table (with an interactive demo), k-gram indexes on a real dictionary, the noisy channel model worked through, and Soundex.
The inverted index
- The inverted index: from the term-document incidence matrix to dictionaries and postings lists, building an index by sorting, dictionary lookup, and what each postings entry can store.
- Index construction: building indexes larger than memory with blocked sort-based and single-pass in-memory indexing, each traced on a small example, distributed indexing, and keeping an index up to date, with the merge costs simulated on a real collection.
- Index compression: dictionary compression, gap encoding, variable byte and Elias gamma codes worked bit by bit on real postings lists, sizes measured on a whole collection, and why compression makes search faster as well as smaller.
Building one
- Building an indexing pipeline: the decisions in a working indexer, illustrated with my course homework and measured on a news collection, and what I would change.
Related topics
- Boolean retrieval processes queries against the inverted index built here, including postings intersection, skip pointers, and positional indexes for phrase queries.
- The vector space model uses the term and document frequencies stored in the index to weight terms.
- The architecture of a search engine places these stages in the whole system.
Course materials
My indexer for the course is HW01 on GitHub. It tokenizes and stems a document collection, builds an inverted index, and reports its memory use.
References
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 2–5. Cambridge University Press.
- Croft, W. B., Metzler, D., and Strohman, T. (2010). Search Engines: Information Retrieval in Practice, chapters 3–5. Addison-Wesley.
- Zobel, J., and Moffat, A. (2006). Inverted files for text search engines. ACM Computing Surveys, 38(2), article 6.