Strength and Similarity of Affix Removal Stemming Algorithms
William B. Frakes
Computer Science Department
Virginia Tech
Christopher J. Fox
Computer Science Department
James Madison UniversityAbstract
This study evaluated the strength of, and similarity
among, four affix removal stemming algorithms.
Strength and similarity were evaluated in different
ways, including new metrics based on the Hamming
distance measure. Data was collected on stemmer
outputs for a list of 49,656 English words derived
from the UNIX spelling dictionary and the Mobycorpus. Conclusions about the relative strength andsimilarity of the four stemming algorithms arereported.

Introduction
Stemming algorithms, or stemmers, are used to groupwords based on semantic similarity. There are several
types of stemming algorithms. Affix removal
algorithms are the most common. Affix removal
stemming algorithms remove affixes (suffixes orprefixes) from words producing a root form called astem that often closely approximates the root
morpheme of a word.
Stemming algorithms are used in many types oflanguage processing and text analysis systems, and arealso widely used in information retrieval and databasesearch systems. There have been many studies ofconflation for information retrieval systems assummarized, for example, in [Frakes, 92]. Most ofthese studies have focused on the effect of stemmingon retrieval performance measured with recall andprecision. A few studies have also looked at stemming
as a method for index compression.
The closeness of a stem to its corresponding root
morpheme is sometimes used as a measure of stemmer
correctness. Another measure of stemmer correctness
is how many semantically related words are correctlyassigned to a conflation class. While stemmer
correctness is important, it is not the focus of thisstudy. Rather, we address the problem of how
stemming algorithms differ, so that one can choose
among them for a particular application. We address
this issue by evaluating the similarity of four affix
removal stemming algorithms using a variant of theHamming distance function and other measures.

Stemmer Strength Metrics
The degree to which a stemmer changes words that itstems is called stemmer strength. For affix removal
stemmers, such a change is either the removal ofcharacters corresponding to an affix, for example
reducing the word engineering to the stem engineer,or recoding. Recoding is replacing one letter withanother, for example changing y to I so that the word
sky becomes the stem ski.
Stemmer strength is important because, especially inthe character removal case, it can be predictive ofrecall and precision and of index compression. A
stronger stemmer will, on average, increase recall,decrease precision, and increase index compression.
Some ways to measure stemmer strength are:•••••

The mean number of words per conflation
class—This is the average number of words that
correspond to the same stem for a corpus. For
example if the words "engineer," "engineered,"and "engineering" are stemmed to "engineer,"then this conflation class size is three. Stronger
stemmers will tend to have more words per
conflation class.
Index compression factor—The index
compression factor is defined as (n-s)/n where nis the number of words in the corpus and s is thenumber of stems. In other words, the index
compression factor is the fractional reduction inindex size achieved through stemming. Forexample, a corpus with 50,000 words (n) and
40,000 stems (s), would have an index
compression factor of 20%. Stronger stemmers
will tend to have larger index compression
factors.
The number of words and stems that differ—
Stemmers often leave words unchanged. For
example, a stemmer might not alter "engineer"
because it is already a root word. Stronger
stemmers will change words more often thanweaker stemmers.
The mean number of characters removed informing stems—Stronger stemmers remove morecharacters from words to form stems. For
example, a stemmer that stems the corpus{engineer, engineered, engineering, engineers} tothe stem engineer would remove an average of(0+2+3+1)/4 = 1.5 characters. A weakness of thismetric is that it does not measure transformationsof stem endings. We therefore have developed
the following measures.
The median and mean modified Hamming

distance between words and their stems—The
Hamming distance between two strings of equal
length is defined as the number of characters in
the two strings that are different at the sameposition. For strings of unequal length we add thedifference in length to the Hamming distance togive a modified Hamming distance function d.
This measure takes into account transformationsof stem endings. For example, a stemmingalgorithm might reduce the corpus { try, tried,trying } to the stem tri. The mean modified
Hamming distance between the original words
and the stem is (1+2+4)/3 = 2.33 characters, andthe median is 2.
These six metrics are used to compare the strength of
the four stemmers.
Using these stemmer strength measures, it is possible
to define the limits of stemmer strength. The strongestpossible affix removal stemmer would be one thatremoved all but the first character from each stemmed
word. The number of conflation classes in this casewould be 26, the mean conflation class size would be
the number of words in the corpus divided by 26, andthe compression factor would be (n-26)/n where n is
the number of words in the corpus. The weakest
possible affix removal stemmer would be one thatchanges no characters in any stemmed word. Such astemmer would have one word per conflation class.
The index compression factor, number of words andstems that differ, mean characters removed, and mean
and median modified Hamming distance between
word and stem in this case would all be zero.

Stemmer Similarity Metrics
There are several reasons to compare stemmers. For
example, information retrieval system designers needto understand the performance of different stemmers
in choosing one for index creation. A retrieval system
might offer users the choice of stemmers as a way tocontrol recall and precision. A comparison ofstemmers might also serve as the basis of developing
better stemmers.
We propose a stemmer metric for pairs of stemmers.
Currently there is no such metric for stemmer
similarity. We suggest a statistic based on the inverseof the modified Hamming distance between stems
produced by pairs of stemmers as our stemming
similarity metric.
It is easy to confuse stemmer strength and similarity
metrics. A stemmer strength metric maps a stemmer toa number that indicates how much a stemmer changes
words to produce stems. A stemmer similarity metricmaps n-tuples of stemmers (n at least 2), to a number
indicating stemmer likeness. Note that a stemmer
strength metric is a function of one stemmer, while astemmer similarity metric is a function of at least 2stemmers.

The stemmer similarity metric M for a pair ofstemming algorithms A1 and A2, given a wordlist W,
is the inverse of the mean modified Hamming distance(d) for all words in the wordlist, M(A1,A2,W) = n/Σ
d(xi,yi), for i ranging from 1 to n, where n is the size of
W and for all words wi in W, xi is the result of theapplication of A1 to wi and yi is the is the result of theapplication of A2 to wi. The inverse of the mean isused so that more similar algorithms will have higher
values of M.
For example, suppose W = {brittle, engineered,fairies} and that stemming algorithm A1 produces thestems {brit, engineer, fairy} from W, and stemmingalgorithm A2 produces {britt, engineered, fairi} fromW. Then M(A1,A2,W) is computed by dividing thewordlist size (3) by the sum of the modified Hamming
distances between the stems produced by eachstemmer for each word (for example, the modifiedHamming distance between brit and britt is 1). Theresult is 3/(1+2+1) = 0.75 as our measure of thesimilarity of algorithms A1 and A2.
We use this similarity metric to make pair wisecomparisons of the four stemmers. A metric is said tobe valid if it measures what it is supposed to measure.
The validity of a metric is usually established byshowing that the proposed metric is correlated withother known measures of the concept. We establish
the validity of M by showing that it agrees with therelative strengths of pairs of stemmers. For example,pairs of stemmers most alike in strength should havethe highest similarity measure, and pairs of stemmers
least alike in strength should have the lowest similarity
measure.

The Wordlist
Grady Ward’s Moby project has collected large wordlists from a variety of sources(ftp://sable.ox.ac.uk/pub/wordlists/Moby). We took
the Moby Common Dictionary wordlist, consisting of74,550 words appearing in at least two publisheddictionaries, and combined it with the 20,046 word
UNIX spelling dictionary. We then removed all entries
not consisting entirely of lower case letters, thus
eliminating proper names, abbreviations, hyphenatedterms, etc. The resulting wordlist is 49,656 common
English words with an average length of 8.07 letters,
and a standard deviation of 2.53 letters.
The wordlist used for this study includes all simple,
common words that several groups of dictionary
writers have found to be in wide use among native
American English speakers. This wordlist is a
representative sample of words that stemmers will beapplied to in practice.

Descriptive Stemmer Data
The four algorithms in this study, Lovins [1968], PaiceMeanStndrd Dev.

Lovins
1.72
1.64

Paice1.98
1.92

Porter1.16
1.40

S-removal
0.03
0.19

Minimum
25th Percentile
Median75th Percentile0013002300120000

Maximum

101393

Table 1: Modified Hamming Distance Descriptive Statistics
order, from strongest to weakest: Paice, Lovins,
Porter, and S-Removal.

[1990], Porter [1980], and S-removal [Harman 1991],
are all longest-match affix removal algorithms. All arerule-driven and run in linear time proportional to thesize of their input.

If a single numeric stemmer strength metric is desired,
we recommend the mean modified Hamming distancemetric for the following reasons:

Table 1 shows summary descriptive statistics for theresults of running the four stemmers on our wordlist.
All data used are modified Hamming distances
between words and their stems. The distributions are
hyperbolic for all four data sets. The maximum
Hamming distance is 13 and the mode is 0 for allstemmers (in other words, most often the stemmers do
not change the word).

••

The statistics in Table 1 show that the stemmers differ
in strength, and that some pairs are more similar thanothers. The analyses that follow are used to establish
the relative strengths and similarities of the stemmers.

•Stemmer Strength
Comparisons
In this section we analyze the strengths of the fourstemmers. We first consider the hypothesis that thestemmers are all of equal strength. To test thishypothesis, we conducted a pair wise sign test of
modified Hamming distances for the four stemmers.
The sign tests showed that there are significant
differences between all pairs of stemmers (p<0.0001).

•We looked at the six measures of stemmer strength
described above; the results are displayed in Table 2.

MeanCharacters
RemovedBased on these measures, we found that Paice is thestrongest stemmer, with Lovins somewhat weaker but
still quite strong. Porter is considerably weaker thanboth Paice and Lovins, but in turn is much stronger
than S-Removal, which in comparison with the rest isa very weak stemmer. These measures of stemmer
Compression
Mean
Word and Stem
Factor
Conflation
Different
Class Size

1.67
1.94
1.08
0.03

0.29
0.33
0.17
0.01

The six metrics are remarkably consistent in ranking
the relative strengths of the stemmers. Except for themedian modified Hamming distance metric, whichshows a tie between the Lovins and Porter stemmers,
each metric places the stemmers in the following
Stemmer

Lovins
Paice
PorterS-Removal

Mean
ModifiedHamming
Distance
1.72
1.98
1.16
0.03

MedianModified
Hamming
Distance
12
10

The mean modified Hamming distance metricdiscriminates between stemmers that the medianmodified Hamming distance metric does not,making it preferable as a tool for comparing
stemmer strength.
The mean modified Hamming distance metricaccounts for ending character transformations
while the mean characters removed metric does
not, making the former a more sensitive measure.
Both the compression factor and the mean
conflation class size are indirect measures ofstemmer strength in the sense that they reflect theeffects on other entities (the inverted index andthe set of conflation classes) rather than theresults of the stemmer itself on terms. The mean
modified Hamming distance is a direct measureand should be less sensitive to external factorsthat might affect these other two metrics.
The count of the number of words in a corpus forwhich the word and stem differ is a grossmeasure of stemmer strength because it does notaccount for how different each word is from its
stem, only that it is different. The mean modified
Hamming distance metric reflects the effect of astemming algorithm on each letter of every word.

Table 2: Modified Hamming Distance Descriptive Statistics

1.42
1.49
1.20
1.01

34437 (69.4%)34533 (69.5%)
27897 (56.2%)
1636 (3.3%)

strength correspond exactly with the mean modified
Hamming distance metric.

Stemmer Similarity
The purpose of stemmer similarity analysis is to show
the degree of relatedness of pairs of stemmers. This
helps with picking a stemmer, and with the evaluationof new stemmers. Selection of an existing stemmer
should be based on its uniqueness and its strength(discussed above). When a new stemmer is proposed,
it can be tested against existing ones using a wordlist.
If it is nearly identical to an existing stemmer, thenarguments for its adoption will need to be made on thegrounds of greater efficiency or simplicity.
Table 3 shows the stemmer similarity metric M andthe percentage of stems the same. This data suggestthat the stemmer similarity pairings from most to least
similar are: Paice-Lovins, Porter-Lovins, Porter-Paice,S-removal-Porter, S-removal-Lovins, and S-removalPaice.
Pairs
Paice-Lovins
Porter-Lovins
Porter-Paice
S-Removal-Porter
S-Removal-Lovins
S-Removal-Paice

1.306
1.248
1.041
0.886
0.592
0.515

Percentageof Stems
the Same
59.8
57.5
53.7
46.0
31.5
31.2

Table 3: Similarity Measure M andPercentage of Stems the SameThe validity of M is supported by the fact that M rates
stemmer likeness in perfect agreement with therelative strength of pairs of stemmers. Specifically the
Paice stemmer is clearly the strongest of the fourstemmers, followed closely in strength by the Lovins
stemmer. The Porter stemmer is weaker than Lovinsand Paice, and the S-removal stemmer is far weaker
than the others. The metric M rates the Lovins andPaice stemmers as the most similar, as one would
expect given their similar strength. The Porter
stemmer is rated as of intermediate similarity toLovins and Paice. The S-removal stemmer is rated asthe least similar to any of the others. The close
correspondence between values of M and the likenessof stemmers derivable from their relative strengths
validates M as a measure of stemmer similarity.

whiskers are 1.5 midspreads from the top and bottomof the box, respectively. Outliers are data points lying
beyond 1.5 midspreads from the median of adistribution. These are indicated as circles in thediagram. Extreme outliers, represented by asterisks, lieat least 2 midspreads above the 75th percentile or
below the 25th percentile. The distribution ofHamming distances between words and their stems
shows both outliers in all the stemmer distributions
and extreme outliers in the Paice, Porter, and S
removal stemmer distributions. Examination of theseoutliers leads to some interesting observations.
Outliers are unusual values of one sort or another, andin this case many of the outliers are clearly overstemmed (too many characters were removed). For
example, the Paice stemmer reduces"ultranationalism" to "ultra." Outlier analysis thus
leads to data helpful for improving the stemmers.
Over-stemming is correlated with stemmer strength. In
particular, over-stemming is very characteristic of thePaice stemmer, frequently occurs with the Lovins
stemmer, is relatively infrequent with the Porter
stemmer, and did not occur with the S removal
stemmer. Such stemming mistakes may have an effecton recall and precision.
Over stemming also seemed to be most prevalent inwords where the root morphemes are in the middle ofthe word. For example, "ultranationalism" has the root
morpheme ("nation") between a prefix and two
suffixes. The outliers were often over-stemmed all theway back to the prefix, or at least into the root
morpheme. This suggests that prefix removal done inconjunction with suffix removal might produce better
13.5

12.0

10.5

9.0

7.5

6.0

4.5

3.0

Outlier Analysis
Boxplots such as those in Figure 1 graphically
represent distributions. The top of the box is the 75thpercentile, the bottom of the box is the 25th percentile,and the bar in the middle of the box is the median. Thelines extending from the box are called whiskers, andthe midspread is the span between the 25th and 75th
percentiles of the distribution. The ends of the1.5

0.0
LovinsPaicePorter

S rem oval

Figure 1: Boxplots of Hamming Distances for fourStemmers

stemming results.
One way to improve stemmer performance (thoughnot explored in the literature) is to keep lists ofstemmer exceptions—words for which a stemmer
fails. The exception list can be searched before
stemming, and if the word is present, its correct stem
can be returned. The outliers provide many instancesof words that might be included in such a stemmer
exception list.

SummaryThis study evaluated the strength of, and similarity
among, four affix removal stemming algorithms:
Lovins, Paice, Porter, and S-Removal. Strength andsimilarity were evaluated in different ways, including
new metrics based on the Hamming distance measure.
Data was collected on stemmer outputs for a list of
49,656 English words derived from the UNIX spelling
dictionary and the Moby corpus.
Stemmer strength, that is, how much a stemmerchanges words that it stems, is important because it ispredictive of recall and precision and of index
compression. A stronger stemmer will, on average,
increase recall, decrease precision, and increase index
compression. We tested the hypothesis that thestemmers are all of equal strength using a pair wisesign test of modified Hamming distances for the fourstemmers. The sign tests showed that there are
significant differences between all pairs of stemmers(p<0.0001).
We considered six metrics for evaluating stemmer
strength. The metrics we considered are consistent inranking the relative strengths of the four stemmers
examined in this study in the following order, fromstrongest to weakest: Paice, Lovins, Porter, and SRemoval.
Stemmer similarity analysis is intended to show thedegree of relatedness of pairs of stemmers. This canhelp with selecting among stemmers and with theevaluation of new stemmers. Based on the stemmer

similarity metric M (inverse modified Hammingdistance) the pairings from most to least similar are:
Paice-Lovins, Porter-Lovins, Porter-Paice, SRemoval-Porter, S-Removal-Lovins, and S-RemovalPaice.
We examined outliers in the distribution of modified
Hamming distances between words and their stems foreach stemmer. Those cases where a stemmer removed
an unusually large number of characters from a word
were often clear instances of over-stemming (toomany characters were removed). Over-stemming iscorrelated with stemmer strength. In particular, overstemming is characteristic of the Paice stemmer,
frequently occurs with the Lovins stemmer, isrelatively infrequent with the Porter stemmer, and did
not occur with the S-removal stemmer.

NoteThis paper is a summary of a technical report of thesame name from the Software Engineering Guild,
1999.

References
Frakes, W. "Stemming Algorithms." In Frakes, W. andR. Baeza-Yates, (ed.) Information Retrieval: DataStructures and Algorithms. Englewood Cliffs, NJ:
Prentice-Hall, 1992.
Harman, D. "How Effective is Suffixing." Journal of
the American Society for Information Science 42 (1),1991, 7-15.
Lovins, J. B. "Development of a Stemming
Algorithm." Mechanical Translation andComputational Linguistics 11, 1968, 22-31.
Paice, Chris D. "Another Stemmer." SIGIR Forum 24(3), 1990, 56-61.
Porter, M. F. "An Algorithm for Suffix Stripping."
Program 14, 1980, 130-137.