Stemming and Lemmatization

A user searching for tartan sweaters is probably happy with a document about a tartan sweater. A user searching for connection pooling would accept documents about connections and connecting. But the Porter stemmer reduces operate, operating, operates, operation, operative, operatives, and operational all to oper. A search for operational research will then match documents about operating systems that also mention research (Manning, Raghavan, and Schütze, 2008, §2.2.4). Reducing words to a common form is mainly a recall device that can cost precision, and the cost varies with how aggressively the reduction is done.

This article covers the two main approaches, stemming and lemmatization, the best-known stemming algorithms, the errors they make, and what experiments have found about whether they help. The most widely used algorithm, the Porter stemmer, has its own article.

Inflection and derivation

Word forms vary in two ways.

Inflectional morphology changes a word's grammatical form without changing its basic meaning or part of speech: cat and cats, walk and walked, good and better. Merging inflected forms is usually what a searcher wants, although the exact form can matter in phrase and exact-match queries.

Derivational morphology forms new words, often of a different part of speech: connect, connection, connective; organ, organize, organization. Derived words are related, but their meanings can drift far apart. Organization has little to do with organ, and university little to do with universe. Merging derived forms helps some queries and hurts others.

Stemming and lemmatization

Stemming reduces words by heuristic rules, usually by stripping suffixes, without consulting a dictionary or analyzing the word's grammar. The result is a stem, which need not be a word: ponies becomes poni, and argued becomes argu. Stemmers usually remove derivational suffixes as well as inflectional ones.

Lemmatization reduces words to their dictionary form, the lemma, using a vocabulary and a morphological analysis of the word. It typically handles inflection only. Manning, Raghavan, and Schütze give examples: am, are, and is all lemmatize to be, and car, cars, car's, and cars' all lemmatize to car. A lemmatizer depends on the part of speech: saw is the lemma saw as a noun and see as a verb, and meeting is a noun in the meeting ran late and a form of meet in we are meeting. Resolving such cases needs part-of-speech information, which requires analyzing the sentence, not just the word.

A real lemmatizer shows both the power and the dependence on part of speech. NLTK's interface to the WordNet lexical database takes a word and a part of speech and returns the lemma; the Porter stemmer takes only the word:

With the right part of speech, the lemmatizer handles exactly the irregular forms that defeat a stemmer: are to be, better to good, corpora to corpus, ran to run. With the wrong one it does nothing, so are treated as a noun stays are. The last row shows that even the part of speech is not always enough. Saw as a verb can be the past tense of see or the present tense of saw (to cut wood), WordNet lists both saw and see as possible verb lemmas, and NLTK's lemmatizer, which returns the shortest candidate without looking at the context, returns the first of the two equally short ones, saw. Only the sentence (I saw her or they saw the logs) decides.

The usual trade-offs follow. Stemmers are fast, need no dictionary, and handle unknown words, but they make errors and produce stems that are not words. Lemmatizers produce real words and typically make fewer conflation errors, but need a lexicon, often need context to choose a part of speech, are usually slower, and merge fewer forms. For retrieval, where stems never need to be shown to anyone, stemming has been the usual choice.

The main stemmers

Lovins (1968) produced the first published stemmer. It removes the longest ending it recognizes in a single pass, then applies rules to fix spelling at the boundary, so that absorption and absorbing can both reach the same stem. Porter (1980) used a smaller set of suffixes, applied in five sequential steps, with conditions based on a measure of the stem's length. Its simplicity, published definition, and freely available code made it the standard for English. Paice/Husk, also called the Lancaster stemmer (Paice, 1990), applies rules iteratively and conflates far more aggressively. Krovetz (1993) took the opposite approach. It checks a dictionary before and after each reduction, removing an ending only if the result is a known word, which yields real words and fewer conflations. Snowball (Porter, 2001) is a small programming language for writing stemmers, in which stemmers for dozens of languages have been written. Its English stemmer, often called Porter2, is a revised algorithm, not a reimplementation of the 1980 rules.

The differences are easy to see on individual words. The following stems were computed with the NLTK implementations of the original Porter algorithm, the Lancaster stemmer, and the Snowball English stemmer:

The Lancaster stemmer reduces most aggressively: generalizations to gen and operational to op are stems so short that many unrelated words reach them. Snowball corrects several known faults of the original Porter algorithm, such as reducing news to new and was to wa. None of them handles irregular forms such as corpora, which only a lemmatizer with a dictionary can map to corpus.

Errors

Stemming makes two kinds of error, which Paice (1994) proposed measuring separately:

• Over-stemming merges words that should be kept apart. The Porter stemmer maps university and universe to univers, general and generous to gener, organization and organ to organ, and news and new to new. Each merged pair lets queries about one retrieve documents about the other.
• Under-stemming fails to merge words that belong together. The Porter stemmer leaves warmer separate from warm, as the architecture article showed, and leaves irregular forms such as ran and run, or better and good, unconnected.

Reducing one error increases the other. A stemmer conservative enough to keep university and universe apart will also miss some legitimate merges. There is no setting that eliminates both.

Measuring conflation on a real vocabulary

The trade-off can be measured by running several methods over the same vocabulary. The vocabulary here is every alphabetic word of two or more letters in Reuters-21578, lowercased: 28,390 distinct words. Besides the stemmers in the table above, the comparison includes Harman's (1991) S stemmer, which only removes plural endings by three rules (-ies to -y, -es to -e, and a final -s dropped, each with a few exceptions), and the WordNet lemmatizer applied without context, trying the noun, verb, and adjective readings in turn:

The classes themselves show what the numbers mean. These are the Reuters words, among those occurring at least three times, that each stemmer puts in the same class as a probe word:

Snowball's revised rules split general from generate and generous, which Porter's merge. Lancaster adds open to the class of operate, an error no query would want. And no stemmer connects ran to run, which the lemmatizer does.

To count both kinds of error, the lemmatizer's output can serve as a rough reference. Two words are a same-lemma pair if the lemmatizer maps them to the same lemma, as with policy and policies or is and are. Among the 8,135 Reuters words that occur at least five times and appear in WordNet, there are 3,766 such pairs. For each stemmer, two quantities are counted: the share of same-lemma pairs that it leaves in different classes, an under-merging rate; and the number of pairs it merges although their lemmas differ. The second count mixes real over-stemming (general and generous) with derivational merges that are often wanted (operate and operation), so it measures aggressiveness rather than error.

The figure shows the shape of the trade-off. Moving from the S stemmer to Porter cuts the under-merging rate from 70.7 percent to 11.0 percent for about 1,920 additional merges. Moving on to Lancaster gains less than one percentage point for more than 4,000 further merges. The pairs that every stemmer leaves apart are the irregular ones, led by forms of be and have and pairs such as rise and rose, which only a lemmatizer can join. (All numbers in this section come from tools/experiments/textproc/stemming.py; the S stemmer follows the rules as Harman lists them in a later report, applying them only to words of three or more letters (Harman, 1992).)

Does stemming help retrieval?

For English, the answer from experiments is that stemming helps somewhat on average, and the average hides large variation between queries.

Harman (1991) compared the Lovins, Porter, and an "S" stemmer that removes only plural endings, on several test collections. None produced a significant improvement in average effectiveness: stemming improved some queries and harmed a comparable number of others. Krovetz (1993) found more consistent gains, particularly for collections of short documents, where a word is less likely to appear in more than one form. Hull (1996), analyzing results query by query, found that stemming of some kind gave small but reliable improvements, that differences among reasonable stemmers were small, and that the effect depended heavily on the query. Manning, Raghavan, and Schütze (2008, §2.2.4) summarize the evidence: stemming increases recall and harms precision, and its overall benefit for English is modest, while for languages with richer morphology, such as Finnish, Hungarian, or Spanish, the benefit is clearer.

That last point recurs across studies, although the size of the gain still depends on the collection and the queries. A language that expresses more grammatical information through word endings produces more forms of each word, so a query in its dictionary form misses more documents without stemming. Braschler and Ripplinger (2004) found clear gains from stemming German, and larger gains from splitting compounds (see tokenization).

Two refinements address over-stemming. Corpus-based stemming starts from an aggressive stemmer's equivalence classes and splits each class according to whether its members actually co-occur in the collection, so that university and universe, which rarely appear in the same documents, end up in different classes (Xu and Croft, 1998). Query-time expansion keeps unstemmed terms in the index and expands each query term to its variants, which allows different expansion rules for different queries. This is the asymmetric approach described in token normalization.

Current practice

Search libraries generally offer a choice. Lucene and Elasticsearch provide the Porter and Snowball stemmers, a lighter stemmer based on Krovetz's, and minimal stemmers that remove only plurals. Light stemming, or none, is a common default where precision matters. Neural retrieval models typically do not stem. They see text through subword tokens and can learn from data that running and ran are related, which addresses the same problem by different means, though without a guarantee that every related form is matched. For a classical inverted index over English text, a conservative stemmer such as Porter or Snowball remains a reasonable default, provided documents and queries are analyzed consistently, most simply by applying the same stemmer to both.

The whole pipeline on one sentence

Stemming is the last of the text-processing stages, so this is the place to follow one sentence through all of them, from its bytes to its index terms. The sentence is

The CEO’s résumé listed “state-of-the-art” operational findings.

It was chosen to exercise each stage: a typographic apostrophe and curly quotation marks, two accented letters, a hyphenated phrase, the fi ligature that PDF extraction often produces, function words, and endings for the stemmer. Each row of the table applies one stage to the output of the row before:

The second row is the failure from the delineation article in a fuller form: the two bytes of each é, and the three bytes of each quotation mark and of the ligature, become separate wrong characters, and two bytes that Windows-1252 leaves undefined become replacement characters. With correct decoding, each later stage removes some distinctions. NFKC turns the ligature into fi, so that findings can match at all, and the tokenizer keeps CEO’s whole because it never breaks at an apostrophe between letters, which is why a separate rule must strip the possessive. Case folding, accent removal, and the stop list take the ten tokens down to seven terms. The stemmer then merges operational with every word in its large oper class, the over-stemming described above, while the lemmatizer leaves it alone but turns findings into finding rather than find, since it is a noun. Each of the seven final terms is what the inverted index records for this sentence, and a query reaches the sentence only if its own words pass through the same stages to the same terms. (The rows are computed by tools/experiments/textproc/stemming.py.)

References

• Braschler, M., and Ripplinger, B. (2004). How effective is stemming and decompounding for German text retrieval? Information Retrieval, 7(3–4), 291–316.
• Harman, D. (1991). How effective is suffixing? Journal of the American Society for Information Science, 42(1), 7–15.
• Harman, D. (1992). Automatic indexing. NIST Interagency Report 4873, table 3, "An 'S' stemmer". National Institute of Standards and Technology.
• Hull, D. A. (1996). Stemming algorithms: A case study for detailed evaluation. Journal of the American Society for Information Science, 47(1), 70–84.
• Krovetz, R. (1993). Viewing morphology as an inference process. In Proceedings of SIGIR 1993, 191–202.
• Lovins, J. B. (1968). Development of a stemming algorithm. Mechanical Translation and Computational Linguistics, 11(1–2), 22–31.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 2.2.4. Cambridge University Press.
• Paice, C. D. (1990). Another stemmer. SIGIR Forum, 24(3), 56–61.
• Paice, C. D. (1994). An evaluation method for stemming algorithms. In Proceedings of SIGIR 1994, 42–50.
• Porter, M. F. (1980). An algorithm for suffix stripping. Program, 14(3), 130–137.
• Porter, M. F. (2001). Snowball: A language for stemming algorithms. https://snowballstem.org/texts/introduction.html
• Xu, J., and Croft, W. B. (1998). Corpus-based stemming using cooccurrence of word variants. ACM Transactions on Information Systems, 16(1), 61–81.