The Porter Stemmer

Stemming reduces words to a common root so that run, runs, running, and runner can all match the same index entry. It trades precision for recall: university and universe both stem toward univers in the classic Porter algorithm, which occasionally over-merges unrelated words, but the recall gain (argue, argued, argues, arguing all collapse to argu) is worth it for full-text search.

Martin Porter published the algorithm in 1980 ("An Algorithm for Suffix Stripping"). It is NOT linguistically aware — it's a fixed sequence of rewrite rules gated by a simple heuristic called the measure, m, of a stem.

The measure m(stem)

Collapse a word into an alternating sequence of vowel groups (V) and consonant groups (C); a word has the shape [C](VC)^m[V], and m counts the VC repetitions. y counts as a vowel only when it follows a consonant (happy — the y is a vowel; yellow — the y is a consonant).

m("tree")    = 0   (C + V, no VC pair yet)
m("trouble") = 1   (C + VC + ... one VC pair)
m("oats")    = 1
m("private") = 2

Nearly every rule reads: "if this suffix matches AND m(stem) satisfies some bound, replace it." m is what stops the algorithm from stripping suffixes off words that are too short to survive it (bl shouldn't lose anything the way terribly should).

The five steps

1. Step 1a — plurals: sses -> ss, ies -> i, ss -> ss, s -> '' (caresses -> caress, ponies -> poni).
2. Step 1b — verb endings: eed -> ee only if m(stem) > 0 (feed keeps its eed since m("f") == 0). ed/ing are removed if the stem contains a vowel, then exactly one cleanup rule fires, first match wins: a stem ending at/bl/iz gets an e appended (conflated -> conflat -> conflate, troubling -> troubl -> trouble); a doubled consonant other than l/s/z is singled (hopping -> hopp -> hop, but hissing -> hiss is untouched because it already ends in ss); otherwise, if m(stem) == 1 and the stem ends CVC, an e is appended (rescues short words like fil -> file).
3. Step 1c — y -> i, but only if the part before the y contains a vowel (happy -> happi, sky is untouched — no vowel before the y).
4. Steps 2–4 — table-driven suffix replacement, longest/most-specific suffixes first: Step 2 handles multi-letter endings like ational -> ate, iveness -> ive, aliti -> al (gated by m(stem) > 0); Step 3 handles shorter ones like icate -> ic, ful -> '', ness -> '' (same gate); Step 4 strips bare suffixes with no replacement — al, ance, ence, er, ic, able, ment, ion (only when the stem ends in s or t), etc. — gated by the stricter m(stem) > 1.
5. Step 5a/5b — cleanup: a trailing e is dropped if m(stem) > 1, or if m(stem) == 1 and the stem does NOT end CVC (cease -> ceas because m("ceas") == 1 and it isn't CVC; sized -> size keeps its e because m("siz") == 1 and siz IS CVC). Step 5b singles a trailing double l when m(stem) > 1.

Watch what this does to conflated and troubling: Step 1b adds an e back (conflat -> conflate, troubl -> trouble) to satisfy the at/bl/iz rule, then Step 5a immediately strips that same e back off, because m("conflat") == 2 and m("troubl") == 1 with a non-CVC ending. Final answers: conflat, troubl. It looks like the algorithm undid its own work — and it did. This is a well-known quirk of the original 1980 rule set; the Snowball ("Porter2") successor closes gaps like this one.

Helper functions you need

• is_vowel(s, i) / is_consonant(s, i) — aeiou, plus y when preceded by a consonant.
• m(stem) — count of VC transitions after skipping any leading consonant run.
• contains_vowel(stem) — used to gate steps 1b and 1c.
• ends_double_consonant(stem) — last two letters identical and both consonants (pp, ss, ll, ...).
• ends_cvc(stem) — last three letters are consonant-vowel-consonant, and the final letter isn't w, x, or y (this exclusion stops -ow/-ay/-ix endings from qualifying).

Get these five helpers exactly right and the five steps become a mechanical chain of suffix-table lookups — no clever logic left, just careful, order-sensitive application of Porter's published rule tables. Search "Porter stemmer algorithm" for the complete Step 2–4 suffix tables if the summary above isn't enough to reconstruct every rule.

In production

Nobody hand-rolls this anymore — use a library (nltk.stem.PorterStemmer, snowballstemmer, Lucene's PorterStemFilter). The Snowball stemmer (Porter's own successor, aka "Porter2") fixes several edge cases and is the modern default. For languages beyond English, Snowball ships dozens of language-specific stemmers. Lemmatization (mapping to a real dictionary root via a POS tagger — better -> good) is more linguistically accurate but far more expensive; most search engines accept stemming's rougher edges for the speed.