Art of Codeartofcode
Lesson 3 of 15

19. Search and Inverted Indexes

1
The picture to keep in your head
2
19.1 Why doesn't `LIKE '%word%'` scale?
3
19.2 How do you tokenise and normalise text?
4
19.3 What is an inverted index?
5
19.4 How does ranking work (TF-IDF, BM25 in brief)?
6
19.5 How do prefix search and tries work?
7
19.6 How do you keep the search index in sync with the database?
8
19.7 Where does Elasticsearch fit in the big picture?
9
19.8 How do you shard a search index?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
19. Search and Inverted Indexes

19.2 How do you tokenise and normalise text?

3 min read+10 XP

In the library: Before filing a book, the librarian decides which subjects it covers and writes them in a standard form: "Cooking", not "COOKING!!" or "cooked". Little words like "the" and "of" never get a card; every book has them.

In the system: An analyzer turns text into terms, the units that go into the index. A typical pipeline:

  1. Tokenise: split text into words. "Data-Intensive" becomes "data" and "intensive".
  2. Lowercase: "Databases" and "databases" become the same.
  3. Remove stop words (optional): drop very common words like "the", "of", "and".
  4. Stem or lemmatize: reduce words to a root, so "designing", "designs" and "design" all become "design".

the analyzer turns "The Databases of Kerala!" into database, kerala.

Figure: the same analyzer runs on books when indexing and on queries when searching.

The golden rule: run the same analyzer at index time and at query time. If books are lowercased when indexed but the query "Database" isn't, nothing matches. That's exactly the Level 4 bug.

Other common steps, depending on the product:

  • Synonyms: "DB" → "database", "sneakers" → "shoes".
  • Removing accents: "café" → "cafe".
  • Different languages need different analyzers. Stemming rules for English don't work for Hindi or Tamil, and some languages don't put spaces between words.
  • Typo tolerance: usually done at query time with fuzzy matching (allowing one or two letter edits), not in the analyzer.

Memory code: "Clean the words the same way going in and coming out."