Dealing with Human Language

edit

“I know all those words, but that sentence makes no sense to me.”

-- Matt Groening

Full-text search is a battle between precision—returning as few irrelevant documents as possible—​and recall—returning as many relevant documents as possible. While matching only the exact words that the user has queried would be precise, it is not enough. We would miss out on many documents that the user would consider to be relevant. Instead, we need to spread the net wider, to also search for words that are not exactly the same as the original but are related.

Wouldn’t you expect a search for “quick brown fox” to match a document containing “fast brown foxes,” “Johnny Walker” to match “Johnnie Walker,” or “Arnolt Schwarzenneger” to match “Arnold Schwarzenegger”?

If documents exist that do contain exactly what the user has queried, those documents should appear at the top of the result set, but weaker matches can be included further down the list. If no documents match exactly, at least we can show the user potential matches; they may even be what the user originally intended!

There are several lines of attack:

  • Remove diacritics like ´, ^, and ¨ so that a search for rôle will also match role, and vice versa. See Normalizing Tokens.
  • Remove the distinction between singular and plural—fox versus foxes—or between tenses—jumping versus jumped versus jumps—by stemming each word to its root form. See Reducing Words to Their Root Form.
  • Remove commonly used words or stopwords like the, and, and or to improve search performance. See Stopwords: Performance Versus Precision.
  • Including synonyms so that a query for quick could also match fast, or UK could match United Kingdom. See Synonyms.
  • Check for misspellings or alternate spellings, or match on homophones—words that sound the same, like their versus there, meat versus meet versus mete. See Typoes and Mispelings.

Before we can manipulate individual words, we need to divide text into words, which means that we need to know what constitutes a word. We will tackle this in Identifying Words.

But first, let’s take a look at how to get started quickly and easily.