The Porter Stemmer

Martin Porter's suffix-stripping algorithm (Porter, 1980) is short enough to print on two pages, and it has been the most widely used English stemmer in retrieval systems for over four decades. Its rules are simple, and their power comes from how they are conditioned. Each rule removes or replaces a suffix only if what remains is long enough, measured in a specific way, to be plausibly a stem. That condition is what lets the algorithm turn replacement into replac while leaving cement alone.

This article presents the algorithm in full, following Porter's paper and using its own examples, then traces several words through it. The stemming and lemmatization article compares Porter's algorithm with other stemmers and summarizes its effect on retrieval.

Consonants, vowels, and the measure

Porter defines a vowel as one of a, e, i, o, u, or a y that follows a consonant. Any other letter is a consonant. So y is a consonant in yes and toy, and a vowel in by and happy.

Write a maximal run of consonants as $C$ and a maximal run of vowels as $V$. Every word then has the form

$$[C](VC)^m[V],$$

an optional initial run of consonants, then $m$ repetitions of a vowel run followed by a consonant run, then an optional final run of vowels. The number $m$ is the measure of the word or stem. Roughly, it counts syllables that end in a consonant, but it is computed from letters alone, not from pronunciation. Porter's examples:

For example, trouble is $C$ (tr) $V$ (ou) $C$ (bl) $V$ (e), which has one $VC$ pair, so $m = 1$.

Computing $m$ by hand takes two passes over the word. First label every letter C or V, using the rule for y. Then count the places where a V is immediately followed by a C. Each such place ends a vowel run and starts a consonant run, so it marks exactly one $VC$ in the form above:

The y rule is visible in the last rows. In happy the final y follows the consonant p, so it is a vowel. In syzygy the first y follows s and is a vowel, the z is a consonant, the second y follows z and is a vowel, and so on alternately. Adding a letter can raise the measure by at most one, which is why troubles has $m = 2$ while trouble has $m = 1$: the final s turns the trailing $V$ into a complete $VC$.

Rules and conditions

Each rule has the form

$$(\text{condition})\ S_1 \rightarrow S_2,$$

meaning: if the word ends in the suffix $S_1$, and the stem, the part of the word before $S_1$, satisfies the condition, replace $S_1$ with $S_2$. $S_2$ is often empty. Conditions combine the measure with four further tests on the stem:

• *S: the stem ends with s (and similarly for other letters);
• *v*: the stem contains a vowel;
• *d: the stem ends with a double consonant, such as -tt or -ss;
• *o: the stem ends consonant-vowel-consonant, where the final consonant is not w, x, or y, as in -wil or -hop.

Within each step, when several rules match, only the one with the longest matching suffix is considered, and if its condition fails, nothing in that step applies. The steps run in sequence, each operating on the output of the one before.

The five steps

The steps below list every rule, with Porter's example for each. Each example shows the effect of that rule alone, not the final stem: relational becomes relate in step 2 and ends as relat after step 5a.

Step 1: plurals and past participles

Step 1a handles plurals:

Step 1b handles -ed and -ing:

The *v* condition is what keeps bled and sing intact: removing the ending would leave bl or s, which contain no vowel. If the second or third rule succeeds, a cleanup rule restores endings that the removal damaged:

Step 1c turns a final y into i if the stem contains a vowel: happy → happi, but sky → sky.

Step 2: double suffixes to single ones

Every rule in step 2 has the condition $m > 0$:

Several examples end in i because step 1c has already turned their final y into i: differently reaches step 2 as differentli.

Step 3: further suffixes

Every rule has the condition $m > 0$:

Step 4: removing suffixes from long stems

Step 4 removes a final suffix when the remaining stem has $m > 1$, which requires at least two $VC$ sequences:

The measure condition is what protects short words. Replacement loses -ement because the remaining stem replac has $m = 2$. Cement keeps it, because the remainder would be c, with $m = 0$. Here the longest-match rule matters as well: -ement is the longest matching suffix, and once its condition fails, the shorter -ment and -ent are not tried.

Step 5: tidying up

Step 5a removes a final e:

Step 5b reduces a final double l: ($m > 1$ and *d and *L) → single letter, so controll → control but roll → roll.

Worked traces

Running whole words through all five steps shows how the steps combine.

generalizations

The final stem is gener. Generous reaches the same stem more quickly: step 1a removes its final s, as it would from any plural, and step 4 removes the remaining -ou from gener ($m = 2$). General and generous are therefore merged, an over-stemming error.

hopefulness

The *o condition keeps the final e, because hop with the e removed would look like a different word.

relational

conditional

Step 2 deliberately turns -tional into -tion rather than removing it, so that step 4 can then treat conditional exactly as it treats condition. Both end as condit. Step 2's other rules follow the same design: they reduce a compound suffix to a simpler one that a later step already knows how to remove.

rating

The cleanup rules of step 1b restore the e that -ing removal destroyed, so that rating and rate meet at rate. The *o condition in step 5a then keeps that e, for the same reason as in hopefulness. Compare hopping, where the cleanup instead removes a doubled consonant: hopp becomes hop, the same stem as hop and hops.

agreed and feed

Because -eed is the longest matching suffix of feed, the rule for -ed is never considered, and feed survives intact rather than becoming fe.

controlling

Step 1b keeps the double l so that falling can become fall rather than fal, and step 5b removes it later only for words long enough ($m > 1$) that the result is still plausible: controll becomes control, while fall stays fall.

All these stems were checked against the NLTK implementation of the original algorithm, and the traces were produced by tools/experiments/textproc/porter_trace.py.

The demo below runs the same algorithm in the browser. It labels each letter of a word C or V, brackets the $VC$ pairs that make up the measure, and lists, for every step, the rule with the longest matching suffix, the stem that rule would leave and that stem's measure, and whether the condition holds. The button feeds the current stem back in, which shows the non-idempotence discussed below.

Strengths and faults

Porter's own evaluation reduced a vocabulary of 10,000 words to 6,370 distinct stems, shrinking the vocabulary by about a third. On the Cranfield 200 test collection, retrieval with its stems was slightly better than with a much more elaborate suffix-removal system, though the difference was small (Porter, 1980). The vocabulary reduction measures conflation, not retrieval effectiveness. It needs no dictionary and runs in one pass per step, and it conflates far less aggressively than iterative stemmers such as Lancaster. Its typical errors, over-stemming derived words such as general and generous and under-stemming irregular forms such as ran and run, are described in stemming and lemmatization. The original algorithm also gives odd results on some short words: news becomes new, was becomes wa, and ice becomes ic.

The algorithm on a real vocabulary

Run over the 28,390 distinct alphabetic words of the Reuters-21578 newswire collection, the algorithm produces 20,906 distinct stems, 73.6 percent of the vocabulary. That is a smaller reduction than in Porter's own test, which kept 63.7 percent (6,370 stems from 10,000 words), probably because a news vocabulary contains many names and abbreviations that carry no suffixes. Just over half the words, 14,669, are changed at all. Of these, 11,177 are changed by a single step, 2,895 by two, 557 by three, and 40 by four. The figure shows how the work divides among the steps:

Most of the algorithm's rules sit in steps 2 and 3, but those steps change few words: the compound suffixes they handle, such as -ization and -fulness, are rare. The bulk of the conflation comes from the plural and -ed/-ing rules of step 1 and from step 4. (These counts come from tools/experiments/textproc/porter_stats.py.)

One further property matters in practice: the algorithm is not idempotent. Applying it to its own output can shorten a stem further, so university becomes univers, and univers becomes univ. The reason is that a stem can end in letters that look like a suffix: univers ends in s, which step 1a removes, leaving univer, which ends in -er, which step 4 removes. This is not rare. Of the 28,390 Reuters words, 1,134 (4.0 percent) have stems that change when stemmed again, among them some of the most frequent words in the collection:

Of those 1,134 words, 1,076 settle after one more pass and 57 after two. The longest chain in the collection belongs to a misspelling, rapeseeed, which becomes rapesee, rapese, rapes, and finally rape. Code that stems a term that has already been stemmed will look up the wrong term, as my first indexer did.

Implementations and variants

Porter later observed that many published implementations of his algorithm contained errors, and he distributed reference implementations to address this. Those reference implementations themselves depart from the published rules in three minor points, inherited from his original BCPL program: they add a step 2 rule LOGI → LOG, replace ABLI → ABLE with BLI → BLE, and leave words of one or two letters alone, apart from removing a final s, as Porter documents on his algorithm page. "The Porter stemmer" can therefore mean the published algorithm or the reference code. Even correct implementations may differ deliberately. NLTK's PorterStemmer, for instance, applies by default a set of extensions to the original algorithm, and an option selects the original. The two modes give different stems for some words:

An index built with one mode and queried with the other will silently fail to match such words. The differences are not confined to curiosities. On the Reuters vocabulary the two modes disagree on 590 words (2.1 percent), and many of them are common: the original algorithm reduces is to i, they to thei, may to mai, and today to todai, where NLTK's default leaves them whole. The Snowball English stemmer disagrees with the original on 1,160 words (4.1 percent), including was and has, which the original reduces to wa and ha. (Counted by tools/experiments/textproc/porter_stats.py, which also checks that the traced implementation used for this article agrees with NLTK's original mode and with this site's own stemmer on 251,369 words.) Recording the exact stemmer and mode with the index is part of the analysis consistency described in designing a modular search engine.

Porter's own revision, the English stemmer of the Snowball project and often called Porter2, fixes several faults of the original. For example, it leaves news and dying as news and die. For new systems it is generally preferred to the original algorithm (Porter, 2001).

References

• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 2.2.4. Cambridge University Press.
• 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
• Porter, M. F. The Porter stemming algorithm. https://tartarus.org/martin/PorterStemmer/