In the field of Information Retrieval, there is an important and fundamental method called the inverted index, which is widely used in full-text search. Back in my ignorant days, I once “invented” an awesome method and called it “mapping”; it actually worked pretty well on small datasets, and I was rather pleased with myself. Later, after I learned about inverted indexes, I truly understood the truth of the phrase: “You think your idea is awesome, but really you’ve just read too few papers”...

The concept of an inverted index is simple. If we have a set of int/float data to store, we not only store an “id -> val” map, but also a “value -> id list” map. When we need to find all records whose value equals some specific value—say, 1024—we simply use 1024 as the key in the “value -> id list” map and easily get back an id list, without having to traverse the “id -> value” map. When the data volume is large, this space-for-time tradeoff is very effective.

But in practice, we don’t usually just search for a number. Often we store a passage of text somewhere, and when querying we type a few words and expect complete results. This requires some additional processing.

A few days ago, a classmate whose name I’ll omit here—Wei Huang—suddenly asked about inverted indexes. I said the concept is easy, and I’d give him a toy-level demo in Python. But a real implementation has to consider many things, such as persistence and thread synchronization, and it’s only a preliminary result; relying on it alone obviously won’t cut it. After about half an hour of tinkering, I wrote some code that actually worked, then told him, “That’s roughly the idea; if you really want to build it, it’d look something like this.”

Python can be a real pain to manage, and its performance is nothing to brag about, but it has one advantage: a few hundred lines of code can be written with just vi, and watching debug output in the terminal is decent enough. Compared to C++’s verbose error messages, Python is a good choice for rushing out a demo. So I used Python for that demo, building an index from the titles of Jiawei Han’s 650+ papers (of course, the input is stored in data.txt; if you don’t like it, you can replace the content yourself—one line per record, very crude). Letting people query the content is very rudimentary, but it should be enough to explain questions like “how to build an index.” If you’re interested, you can check out this toy repo here.

[github_widget repo="yuikns/hello-tfidf"]

Querying a string is essentially no different from querying an int/float: you build another map where the key is the original value and the value is an id list, and so on. But since few people can write the full target content directly into the query, when building an inverted index we first split the string into small terms and index those terms. When someone queries, we also split the query into terms, query each one separately, and merge the results.

Now there’s a problem. Given a term, querying the original docs often yields a set of results—and the number can be large. Unlike an int inversion, where searching for docs with value 1024 is a simple yes-or-no boolean, string search is different. For example, if you search for “data mining,” a string that repeatedly mentions “data mining” is probably more relevant than one that only mentions it once. And if we use “is” as a term, it appears in all kinds of texts and may not be a meaningful term. To address this, [wiki lang='zh']TF-IDF[wiki] is a very common method. So we need not only the list of relevant doc ids for a given term, but also to rank those doc ids by importance. By the way, TF-IDF is just an assumption; we find that it works well empirically, but why it works, there doesn’t seem to be any solid proof yet...

TF-IDF needs four parameters:

  • How many times does this term appear in the current doc?
  • How many terms are there in total in this doc?
  • How many docs are in the database?
  • How many docs in the database contain this term?

Then you plug the values into the formula to get the TF-IDF score of a term in a doc. The higher the score, the more relevant it is.

Once you know the principle, implementation is simple. First, construct a class to hold the relevant data (this is for simplicity; in a real application, keeping all this in memory wouldn’t be very reliable):

Python
class Index :
  # a unique doc id && all document size
  max_doc_id = 0 
  doc = {}
  # key : doc id , value : all term size&times
  doc_meta = {}
  index = {}

Among them:

  • doc stores the id -> content mapping; doc_meta is used to answer “how many terms are in this doc?”
  • index is a two-level dict: the key is a term, and the value is a dict of id -> “how many times this term appears in the current doc.”
  • max_doc_id is used in two ways. First, when adding a doc, it serves as the current doc id (and then max_doc_id++). Second, when querying, its value happens to answer “how many docs are in the database?”

Thus three of the four questions are answered. The only one left is “how many docs in the database contain this term?”, which is easy: it’s just the size of index[term].

With the data structure ready, we just follow the recipe.

The process of building the index is straightforward.

Python
def build_index(idx):
  print("Building Index .. ")
  f = open('data/data.txt', 'r')
  for line in f:
    idx.doc[idx.max_doc_id] = line.strip()  # store doc
    tokens = analysis(line)
    term_sz = 0
    for k, v in tokens.items():
      idx_term = {}
      if k in idx.index :
        idx_term = idx.index[k]
      else :
        idx_term = {}
      idx_term[idx.max_doc_id] = v
      idx.index[k] = idx_term
      term_sz += v
    idx.doc_meta[idx.max_doc_id] = term_sz
    idx.max_doc_id = idx.max_doc_id + 1
  f.close()

Read the docs line by line. For each doc, first save it into Index.doc, then tokenize the content to get each term and its occurrence count (this is the job of analyzer). Then store everything according to the data structure.

Querying is the same: first analyze, query each term separately, merge the resulting scores (for example, I simply sum the scores for the same doc id), then sort them, and you have a preliminary query result.

It should be noted that although we’ve gone through the motions of assembling a bunch of docs and TF-IDF scores, it’s still only a preliminary result; it’s just a good start. More processing is needed to make the results what people actually want.

Update: Later, I also implemented an index in C++ using leveldb for storage. If you’re interested, please see this post.

Update: Added the BM25 algorithm. How to combine multiple TF-IDF query results? This is a common solution.