Building an Indexing Pipeline

The first assignment in the course was to build an inverted index over a directory of text documents. It had to remove stop words, stem terms, report the most frequent terms and the index's memory use, and save the index for later use. My solution, HW01 in the information-retrieval repository, does all of that in about 600 lines of Python using NLTK, including a parser for Boolean queries. It works, and on the assignment's collection it produces sensible results. Reading it again after writing the rest of this topic shows how many of the decisions discussed in the earlier articles are made in a few lines of an ordinary indexer, often without being noticed as decisions at all.

This article walks through the pipeline stage by stage. For each stage it describes what the code does, which concept from the topic it embodies, and what I would change. The aim is not to criticize a homework assignment, which met its requirements, but to show where the theory of this topic meets real code.

Reading files

The indexer lists the files in a directory, keeps those ending in .txt, and reads each one:

with open(filepath, 'r', encoding='utf-8', errors='ignore') as f:
    text = f.read()

Specifying UTF-8 is right for most modern text. The errors='ignore' argument is the risky part. It tells Python to drop any bytes that are not valid UTF-8, without reporting them. A file saved in Latin-1 containing résumé would be read as rsum, the silent deletion described in from bytes to documents. The program never fails, and the corrupted terms simply enter the index. The bytes are easy to inspect: Latin-1 stores é as the single byte 0xE9, which can never stand alone in valid UTF-8. Decoding r\xe9sum\xe9 with errors='ignore' yields rsum. With errors='replace' it yields r�sum�, in which the two replacement characters, U+FFFD, mark exactly where the damage is.

To make the rest of this article concrete, the measurements below run HW01's choices over a larger collection than the assignment's: Reuters-21578 (Lewis, 1997), 10,788 news stories, which the term statistics and index compression articles also use. The scripts apply the same NLTK tokenizer, filter, and stemmer, without stop-word removal.

What I would change: decode with errors='replace', count the replacement characters in each file, and report files with many of them. Those are almost certainly in another encoding and can be re-read with the right one. Choosing documents by extension is also fragile. The course project's later requirement to handle several formats calls for a dispatcher that identifies each file's format and passes it to an appropriate text extractor.

Assigning document identifiers

Each file receives an integer docID in the order the directory listing returns it. Directory listing order is not guaranteed and differs between operating systems and file systems, so the same collection can produce different docIDs on different machines. Results then look different even when nothing else has changed.

There is also an inconsistency between the two build modes. The single-process build skips empty files. The parallel build, which divides the files among worker processes, does not check for empty files, so they receive docIDs there. The same directory can therefore produce different document counts depending on which mode runs, which in turn changes any statistic that depends on the number of documents, such as inverse document frequency.

What I would change: sort the filenames before assigning docIDs, and put the rules for skipping a file in one function that both build modes call.

Tokenizing and filtering

The core of the indexer is one list comprehension:

tokens = [self.stemmer.stem(word.lower())
          for word in nltk.word_tokenize(text)
          if word.isalpha() and word.lower() not in self.stopwords]

This line performs tokenization, case folding, stop-word removal, and stemming, in the order recommended in the stop words article.

The isalpha() filter has a larger effect than it appears to. It keeps only tokens made entirely of letters. Applied to the example sentence from the tokenization article,

O'Neill's state-of-the-art C++ library wasn't released until 3/20/91 (see www.example.com).

NLTK's tokenizer produces fifteen tokens, and isalpha() keeps five of them: library, was, released, until, and see. O'Neill, state-of-the-art, C++, the date, and the web address are all discarded, along with the punctuation the filter was meant to remove. On Reuters-21578 the tokenizer produces 1,549,426 tokens. The filter keeps the 82.4 percent that are purely alphabetic and removes 9.9 percent that are pure punctuation, as intended. It also removes another 7.7 percent, 119,961 tokens, that contain letters or digits. Seven in ten of those are numbers, which in a financial newswire carry much of the content: prices, quantities, and dates. The most common of the rest are the possessive 's, which NLTK splits off as a token of its own, and the abbreviation U.S., which occurs 4,919 times and is unsearchable after filtering. For the assignment's documents, this was a reasonable way to keep the vocabulary clean. For a general collection, it makes names with apostrophes, hyphenated terms, every number, and every technical identifier unsearchable.

What I would change: replace the filter with explicit rules. Drop pure punctuation, keep tokens that contain letters or digits, and decide deliberately what to do with apostrophes and hyphens, for example by indexing both the joined form and its parts. The query side must apply exactly the same rules, which leads to the next point.

Stemming consistently

The stemmer is NLTK's PorterStemmer() with no arguments. By default, that class applies NLTK's extensions to the original Porter algorithm, and it gives different stems from the original for words such as dying, skies, news, and ice (see the Porter stemmer). That is fine, provided queries are stemmed in exactly the same way. In HW01 the query parser takes the index's stop list but creates its own PorterStemmer() with the same default settings, and repeats the tokenizing and filtering rules in its own code. Rereading it for this article turned up a bug the duplication made easy to miss: the parser stems each query term twice, once when it tokenizes the query and again when it looks the term up. The Porter stemmer is not idempotent. Stemming a stem can shorten it further: university becomes univers, and univers becomes univ. A query for university therefore looks up univ, which is not in the index, and silently matches nothing. Decisively goes from decis to deci in the same way. Most words survive a second stemming unchanged, which is why the bug passed testing.

Reuters-21578 shows how often they do not. Of the collection's 27,959 distinct lowercase words, 1,060 (3.8 percent) have a stem that changes when stemmed again, and these words account for 2.0 percent of all word occurrences. For 792 of them the doubly stemmed form is not a term in the index at all, so a query silently matches nothing. The other 268 are worse in a different way, because the second stem is another word's stem. Examples of both kinds:

Increase is the most frequent affected word in the collection, and a query for it finds only the few stories in which the wire misspelled it. Querying japanese returns the stories that mention Japan, which look plausible and hide the error. In later assignments, as designing a modular search engine describes, query processing reached into the index's private preprocessing method to achieve the same guarantee.

What I would change: make the analyzer, the combination of tokenizer, filter, stop list, and stemmer, a separate object that is saved with the index, so that any program that loads the index also loads the exact analysis that built it. Queries then pass through that one analyzer exactly once.

Representing postings

The index itself is a Python dictionary mapping each term to a set of docIDs:

for term in set(tokens):
    self.index[term].add(doc_id)

Sets were a natural choice for the assignment. Python intersects them directly, which made the Boolean queries of the next assignment easy to implement. The representation has three consequences that the rest of the course makes visible:

• No order. Sets are unordered, so the sorted-list merge algorithm described in intersecting postings lists, and the gap encoding that depends on sorted lists, cannot be applied without sorting first.
• No term frequencies. A set records only whether a term occurs in a document, not how often. The separate term_frequency counter records each term's collection frequency, which is enough to list the most frequent terms, but not the within-document frequencies that TF-IDF and BM25 need. When the vector space assignment arrived, the index had to be rebuilt to store frequencies. This was a direct instance of the principle from the architecture article that a ranking function can only use what the index stored.
• Memory. Every Python object carries overhead. On a 64-bit build of CPython, a small integer occupies 28 bytes, an empty dictionary 64, and a set containing a single integer 216. Most terms occur in only one or two documents, as Zipf's law predicts, so most of the index consists of tiny sets. A docID that would take 4 bytes as a raw integer, or one byte as a variable byte code, costs on the order of a hundred bytes in this representation.

What I would change: store each postings list as a sorted array of integers with a parallel array of term frequencies, using Python's array module or NumPy, and convert to gaps with variable byte encoding when saving.

Measuring memory

The assignment required reporting the index's memory use. The code walks the index recursively, summing sys.getsizeof over every dictionary, set, and integer, and also reports the size of the index when serialized with pickle, labeled "Pickled (Compressed) Size".

The recursive measurement is the right approach for Python, since getsizeof alone reports only the outer container. The label is not quite right, though. Pickle is a serialization format, not a compression method. The pickled index is smaller than the in-memory one mainly because it omits Python's per-object overhead, and also because pickle writes each small integer with a one-byte opcode followed by one or two bytes of value, a crude variable-length code of its own. Compressing it, with a general-purpose compressor such as gzip or with the integer codes of index compression, would shrink it much further. The comparison between in-memory size, serialized size, and compressed size is itself instructive, and worth reporting as separate numbers. For the Reuters-21578 index built HW01's way, with 20,540 terms and 666,541 postings (sizes in megabytes, millions of bytes, rounded to two decimals):

The in-memory form is about sixty times the size of the variable-byte postings. Most of that is the fixed cost of a Python set for every term: 45.8 percent of the terms occur in only one story, and each of those pays more than two hundred bytes for a container holding a single docID. The last two rows count only the postings, not the dictionary of terms, so they understate a complete index somewhat; the 20,540 terms themselves add 124,199 characters, about 0.12 MB as a single string.

Saving and loading

The index is saved with pickle and can be exported to JSON for inspection. Pickle is convenient but has two drawbacks for anything beyond a course project. It is specific to Python, and loading a pickle file can execute arbitrary code, so a pickled index should never be loaded from an untrusted source. A simple documented format, such as a dictionary file and a postings file of encoded integers, avoids both problems and is the form that the index construction algorithms naturally produce.

Building in parallel

The parallel mode divides the files into chunks, gives each chunk to a worker process with a starting docID, and merges the workers' partial indexes. It resembles the parsing phase of the distributed indexing described in index construction: workers parse their portions of the collection independently. Unlike MapReduce indexing, which partitions the work by term range and inverts each range in parallel, HW01 divides the work by document and merges all the partial indexes in a single process. Because each chunk receives a contiguous range of docIDs, the merged postings could be kept in docID order if they were stored as sorted lists rather than sets. For a collection of a few thousand short files, the overhead of starting processes and transferring partial indexes between them can outweigh the gain. The benefit appears as collections grow, which is why the later assignments chose between sequential and parallel builds automatically based on the number of documents.

Summary of changes

None of these changes was needed to complete the assignment. Each becomes necessary once a collection outgrows a homework directory, and each corresponds to a principle from earlier in this topic. The indexer then becomes the foundation for the Boolean retrieval assignment that follows.

References

• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 1–2. Cambridge University Press.
• Python Software Foundation. The Python Standard Library: pickle, array, and sys.getsizeof. https://docs.python.org/3/library/
• Bird, S., Klein, E., and Loper, E. (2009). Natural Language Processing with Python. O'Reilly Media.
• Lewis, D. D. (1997). Reuters-21578 text categorization test collection, distribution 1.0.