Suffix-Stripping Stemmers and the Conflations They Force

A user searching connections wants documents about connection, and probably also about connect, connected, and connecting. The cheapest way to arrange that is to rewrite every surface form into a shared key at both index and query time, and the dominant family of algorithms for doing so is suffix stripping: a table of rules that removes or replaces endings under conditions on what precedes them.

The output of such an algorithm is a stem, not a word. connection reduces to connect, connections to connect, and relational to relat, which is not anything. That is acceptable because the stem never surfaces to a user. It is only ever a dictionary key, and the requirement on it is that it group the right forms, not that it be pronounceable. What matters is which forms it groups, and which it wrongly merges.

The condition algebra that keeps stripping sane

A rule of the form “remove -ing” over-generates immediately: thing becomes th. Porter’s algorithm, published in 1980, imposes conditions on the stem that remains after the suffix is removed, and those conditions are the substance of the algorithm. The key one is the measure of a stem, written $m$, defined as the number of vowel-consonant sequences in it, where a vowel is written $V$ and a consonant $C$ and consecutive repeats collapse. Formally, a stem has measure $m$ if it matches $[C],(VC)^{m},[V]$; tr has $m=0$, private is C V C V C V and has $m=2$, and oats is V C V C with $m=1$.

Rules are then conditioned on the measure. A widely quoted one, from step 1c of the original description, replaces a terminal y with i when the stem contains a vowel, so happy becomes happi and cry stays cry. Step 2 replaces a terminal -ational with -ate when $m>0$, so relational becomes relate, and step 5a then deletes the final e because the stem’s measure exceeds 1, leaving relat. Step 4 deletes suffixes such as -al, -ance, and -ent only when $m>1$, so a short stem keeps them. Additional conditions guard against removing a suffix that would leave nothing, and against double consonants, which are collapsed, and against a final e, which is dropped under its own conditions in a later step.

The ordering is fixed and the steps are applied in sequence rather than as alternatives, which is why generalizations passes through several rules and lands on gener. Each step narrows the space of endings the next step can see.

Snowball is Porter’s own later reformulation, with the conditions expressed in a small language and with algorithms provided for several languages rather than English alone. It is not a different idea; it is the same idea with the rule set stated precisely enough to be reimplemented from the specification, and with the English variant generally agreed to fix some over-stripping in the original.

Where stems merge things that should not merge

Aggressive grouping increases recall and decreases precision, and the failures are specific.

The classic collisions in English involve derivationally unrelated words that happen to share a stem. universe and university both reduce to univers, so a query for one retrieves the other. general and generous both reduce to gener, merging an adjective with a character trait. organization and organ both reduce to organ, which merges an anatomical term with a business one.

The reason is structural: suffix stripping has no notion of part of speech or of the derivation that produced a word. It sees characters. A rule that removes the ending of university cannot know that the remainder is not a base form in the same paradigm as universe. Anything that groups by edit distance over endings will occasionally group across semantic lines, and the collisions concentrate in word families where a short base takes many derivational endings.

The opposite failure also occurs. Words that ought to group do not, because they are irregular: went and go, better and good, mice and mouse are not related by suffixation and no stripping rule will connect them. This is the boundary between stemming and lemmatization.

Lemmatization, and what it buys

A lemmatizer uses a lexicon and part-of-speech information to map an inflected form to its dictionary headword: went to go, is to be, better to good given an adjective tag. It produces real words, resolves irregular forms, and avoids the character-level collisions above. The cost is a dependency on a morphological dictionary and a tagger, both of which must run at index time for every token, and both of which are language-specific.

The two approaches are not interchangeable in effect. Lemmatization is more precise and more expensive; stemming is cheaper and noisier. The middle ground, proposed by Krovetz, keeps the lexicon small and targets only inflectional suffixes (-s, -ed, -ing) while refusing derivational ones, so connection and connect may or may not group depending on the dictionary, but universe and university never do because their difference is derivational rather than inflectional.

For most retrieval workloads the inflectional/derivational distinction is the one that matters. A user searching running benefits from matching run, and a user searching organization does not benefit from matching organ. Derivational grouping is where stemming earns its reputation for strange results.

Applying the same function to two sides

The algorithm must be applied identically at index time and at query time, or the keys will not agree. That sounds trivial and is the single most common deployment error: a pipeline change that adds a stemmer to the query analyzer while the existing index was built without one makes every query miss, because running now looks up run in a dictionary that only contains running.

Rebuilding the index is the only correct repair. Applying the stemmer lazily at query time and falling back to the unstemmed form when the stemmed lookup fails recovers some queries, but it is not equivalent to rebuilding, and the fallback path quietly changes what the scorer sees.

The same asymmetry applies to every filter in the chain, and it compounds when a filter also rewrites adjacency. A stop-word filter that preserves position gaps changes which stems can appear in a phrase, so the two decisions cannot be made independently.

import re

# A reduced subset of the Porter steps, sufficient to show the measure condition.
VOWELS = set("aeiou")

def measure(stem: str) -> int:
    pattern = re.sub(r"[^aeiou]+", "C", stem)
    pattern = re.sub(r"[aeiou]+", "V", pattern)
    pattern = re.sub(r"(.)\1+", r"\1", pattern)
    return pattern.count("VC")

def step_1a(term: str) -> str:
    if term.endswith("sses"):
        return term[:-2]                      # caresses -> caress
    if term.endswith("ies"):
        return term[:-2]                      # ponies -> poni
    stem = term[:-1]
    # Porter's condition is (*v*): the stem must contain a vowel at all
    if term.endswith("s") and not term.endswith("ss") and any(c in VOWELS for c in stem):
        return stem                           # cats -> cat, gas -> ga, caress unchanged
    return term

def step_2(term: str) -> str:
    # (m>0) ATIONAL -> ATE, so relational -> relate
    if term.endswith("ational") and measure(term[:-7]) > 0:
        return term[:-7] + "ate"
    return term

for w in ("caresses", "ponies", "caress", "cats", "gas"):
    print(w, "->", step_1a(w))
print("relational ->", step_2("relational"))

The ss exception is not cosmetic. Without it, caress loses a letter that belongs to the word and press, class, and access follow. The gas case shows the opposite direction of error: the rule fires because the stem contains a vowel, and the trailing s is not a plural marker at all. Every guard in the table exists because some real word would otherwise be mangled, and the table is a record of those cases rather than a derivation from first principles.

Languages other than English, and languages without spaces

Snowball provides stemmers for a set of European languages, each with its own suffix inventory and its own measure conditions. The concept generalizes because inflection is a morphological property, but the tables do not: German compounds and its case endings, Russian’s richer inflection, and Arabic’s pattern-based morphology each need a rule set written against that language.

For languages with heavy compounding, stemming alone is insufficient. German Lebensversicherungsgesellschaft is a compound whose head determines most of its meaning, and splitting it into components before stemming is a separate operation. Arabic and Hebrew need morphological analysis at the level of roots and patterns rather than prefixes and suffixes, because the stem itself is discontinuous.

The overall shape holds: a cheap deterministic rewrite that increases the chance two surface forms of the same concept share a key, applied symmetrically, accepting that a small fraction of distinct concepts will be merged. The alternative to any of this, indexing surface forms and expanding at query time, is covered under synonym expansion timing, and it trades index size for query latency in the opposite direction.

Measuring whether it helped

A stemmer’s effect is measured by running the same queries against two indexes and comparing effectiveness on a judged set of relevance labels. The common outcome in published comparisons is a gain in recall at shallow depth and a small loss in precision at the top, with the net effect positive for short queries and near zero for long ones. Because the effect is query-dependent, blanket decisions about whether stemming is on are less useful than decisions about which fields use it: a title field rarely benefits, and a body field usually does.

A cheap diagnostic that needs no judgments: take a sample of stems that map to more than one frequent surface form and read them. The list shows exactly which concepts have been merged, and a handful of obviously wrong merges is enough to justify a more conservative rule set or a switch to inflectional-only lemmatization.