Scribd
Upload
15 views8 pages

Understanding the Porter Stemming Algorithm

Prter stemming algorithm

Uploaded by

siddu.elligati2005
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
15 views8 pages

Understanding the Porter Stemming Algorithm

Prter stemming algorithm

Uploaded by

siddu.elligati2005
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

PORTER STEMMING ALGORITHM

In linguistics (study of language and its structure), a stem is part of a word, that is
common to all of its inflected variants.
 CONNECT
 CONNECTED
 CONNECTION
 CONNECTING
Above words are inflected variants of CONNECT. Hence, CONNECT is a stem.
To this stem we can add different suffixes to form different words.
The process of reducing such inflected (or sometimes derived) words to their word
stem is known as Stemming. For example, CONNECTED, CONNECTION and
CONNECTING can be reduced to the stem CONNECT.
The Porter Stemming algorithm (or Porter Stemmer) is used to remove the
suffixes from an English word and obtain its stem which becomes very useful in
the field of Information Retrieval (IR). This process reduces the number of terms
kept by an IR system which will be advantageous both in terms of space and time
complexity.

Consonants and Vowels

A consonant is a letter other than the vowels and other than a letter “Y” preceded
by a consonant. So in “TOY” the consonants are “T” and “Y”, and in “SYZYGY”
they are “S”, “Z” and “G”.

If a letter is not a consonant it is a vowel.

A consonant will be denoted by c and a vowel by v.

A list of one or more consecutive consonants (ccc…) will be denoted by C, and a


list of one or more consecutive vowels (vvv…) will be denoted by V. Any word, or
part of a word, therefore has one of the four forms given below.

 CVCV … C → collection, management


 CVCV … V → conclude, revise
 VCVC … C → entertainment, illumination
 VCVC … V → illustrate, abundance
All of these forms can be represented using a single form as,

[C]VCVC … [V]
Here the square brackets denote arbitrary presence of consonants or vowels.

(VC)m denotes VC repeated m times. So the above expression can be written as,

[C](VC)m[V]

What is m?

The value m found in the above expression is called the measure of any word or
word part when represented in the form [C](VC)m[V]. Here are some examples for
different values of m:
 m=0 → TREE, TR, EE, Y, BY
 m=1 → TROUBLE, OATS, TREES, IVY
 m=2 → TROUBLES, PRIVATE, OATEN, ROBBERY
Rules
The rules for replacing (or removing) a suffix will be given in the form as shown
below.

(condition) S1 → S2

This means that if a word ends with the suffix S1, and the stem before S1 satisfies
the given condition, S1 is replaced by S2. The condition is usually given in terms
of m in regard to the stem before S1.

(m > 1) EMENT →
Here S1 is ‘EMENT’ and S2 is null. This would map REPLACEMENT to
REPLAC, since REPLAC is a word part for which m = 2.

Conditions
The conditions may contain the following:

 *S – the stem ends with S (and similarly for the other letters)
 *v* – the stem contains a vowel
 *d – the stem ends with a double consonant (e.g. -TT, -SS)
 *o – the stem ends cvc, where the second c is not W, X or Y (e.g. -WIL, -HOP)
And the condition part may also contain expressions with and, or and not.

(m>1 and (*S or *T)) tests for a stem with m>1 ending in S or T.
(*d and not (*L or *S or *Z)) tests for a stem ending with a double consonant and
does not end with letters L, S or Z.
How rules are obeyed?
In a set of rules written beneath each other, only one is obeyed, and this will be the
one with the longest matching S1 for the given word. For example, with the
following rules,

1. SSES → SS
2. IES → I
3. SS → SS
4. S →
(Here the conditions are all null) CARESSES maps to CARESS since SSES is the
longest match for S1. Equally CARESS maps to CARESS (since S1=”SS”) and
CARES to CARE (since S1=”S”).

The Algorithm

Step 1a
1. SSES → SS
2. IES → I
3. SS → SS
4. S →

Step 1b
1. (m>0) EED → EE
2. (*v*) ED →
3. (*v*) ING →

If the second or third of the rules in Step 1b is successful, the following


is performed.

1. AT → ATE
2. BL → BLE
3. IZ → IZE
4. (*d and not (*L or *S or *Z)) → single letter
5. (m=1 and *o) → E
Step 1c
1. (*v*) Y → I

Step 2
1. (m>0) ATIONAL → ATE
2. (m>0) TIONAL → TION
3. (m>0) ENCI → ENCE
4. (m>0) ANCI → ANCE
5. (m>0) IZER → IZE
6. (m>0) ABLI → ABLE
7. (m>0) ALLI → AL
8. (m>0) ENTLI → ENT
9. (m>0) ELI → E
10.(m>0) OUSLI → OUS
11.(m>0) IZATION → IZE
12.(m>0) ATION → ATE
13.(m>0) ATOR → ATE
14.(m>0) ALISM → AL
15.(m>0) IVENESS → IVE
16.(m>0) FULNESS → FUL
17.(m>0) OUSNESS → OUS
18.(m>0) ALITI → AL
19.(m>0) IVITI → IVE
20.(m>0) BILITI → BLE

Step 3
1. (m>0) ICATE → IC
2. (m>0) ATIVE →
3. (m>0) ALIZE → AL
4. (m>0) ICITI → IC
5. (m>0) ICAL → IC
6. (m>0) FUL →
7. (m>0) NESS →

Step 4
1. (m>1) AL →
2. (m>1) ANCE →
3. (m>1) ENCE →
4. (m>1) ER →
5. (m>1) IC →
6. (m>1) ABLE →
7. (m>1) IBLE →
8. (m>1) ANT →
9. (m>1) EMENT →
10.(m>1) MENT →
11.(m>1) ENT →
12.(m>1 and (*S or *T)) ION →
13.(m>1) OU →
14.(m>1) ISM →
15.(m>1) ATE →
16.(m>1) ITI →
17.(m>1) OUS →
18.(m>1) IVE →
19.(m>1) IZE →

Step 5a
1. (m>1) E →
2. (m=1 and not *o) E →

Step 5b
1. (m > 1 and *d and *L) → single letter

For each word you input to the algorithm, all the steps from 1 to 5 will be
executed and the output will be produced at the end.
Example Inputs
Let’s consider a few example inputs and check what will be their

stemoutputs.

Example 1
In the first example, we input the word MULTIDIMENSIONAL to the Porter
Stemming algorithm. Let’s see what happens as the word goes through steps 1 to 5.

 The suffix will not match any of the cases found in steps 1, 2 and 3.
 Then it comes to step 4.
 The stem of the word has m > 1 (since m = 5) and ends with “AL”.
 Hence in step 4, “AL” is deleted (replaced with null).
 Calling step 5 will not change the stem further.
 Finally the output will be MULTIDIMENSION.
MULTIDIMENSIONAL → MULTIDIMENSION
Example 2
In the second example, we input the word CHARACTERIZATION to the Porter
Stemming algorithm. Let’s see what happens as the word goes through steps 1 to 5.

 The suffix will not match any of the cases found in step 1.
 So it will move to step 2.
 The stem of the word has m > 0 (since m = 3) and ends with “IZATION”.
 Hence in step 2, “IZATION” will be replaced with “IZE”.
 Then the new stem will be CHARACTERIZE.
 Step 3 will not match any of the suffixes and hence will move to step 4.
 Now m > 1 (since m = 3) and the stem ends with “IZE”.
 So in step 4, “IZE” will be deleted (replaced with null).
 No change will happen to the stem in other steps.
 Finally the output will be CHARACTER.
CHARACTERIZATION → CHARACTERIZE → CHARACTER

Common questions

Powered by AI

The Porter Stemming algorithm benefits Information Retrieval (IR) systems by reducing the number of terms, which improves space and time efficiency . It achieves this by condensing words into their root forms, allowing searches for various word forms to be matched to the same stem. However, this can also lead to potential drawbacks such as over-stemming, where distinct terms are incorrectly reduced to the same stem, or under-stemming, where related terms remain unlinked, affecting precision and recall in IR results . Hence, while it enhances computational efficiency, stemming must be carefully tailored to the specific linguistic nuances of use cases in IR systems.

The measure 'm' determines whether certain suffixes can be removed based on the structure of the word's stem. For example, in the word 'REPLACEMENT', the measure 'm' is calculated as 2 in 'REPLAC', qualifying it for the suffix 'EMENT' to be removed, resulting in the stem 'REPLAC' . Similarly, 'TROUBLES' has an 'm' of 2 thanks to the two consonant-vowel sequences, allowing suffixes like 'LES' to be addressed depending on the conditions applied . These conditions rely on 'm' to ensure the stemming process achieves a linguistically valid base form.

The condition *o* tests if a stem ends with a consonant-vowel-consonant sequence where the final consonant is not 'W', 'X', or 'Y'. This impacts the reduction of words like 'HOPPING', as the CVC pattern 'HOP' results in the removal of the double consonant 'P', reducing it to 'HOP'. This operation is performed under the rule that allows shortening the doubled consonant to a single letter if it ends with *d and not (*L or *S or *Z). Such specific conditions help control accurate stemming by acknowledging unique phonetic constructs.

Though the Porter Stemming algorithm is effective in reducing word variants for computational efficiency, it lacks nuances in linguistic morphology and semantics. It performs stemming based on generic rules, often leading to over-stemming (e.g., 'general' and 'generous' might be reduced to the same stem) or under-stemming, which fails to resolve differences in meaning . Furthermore, the algorithm doesn't consider contextual semantics or irregular word forms, potentially resulting in a loss of syntactic specificity. This highlights the trade-off between algorithmic simplicity and linguistic accuracy.

When a suffix in a word does not match any rules at the initial steps of the Porter Stemming algorithm, such as in 'MULTIDIMENSIONAL', it progresses to subsequent steps where different conditions are examined. In this case, 'MULTIDIMENSIONAL' ultimately reaches step 4 with 'm=5' and ends with 'AL'. The condition (m>1) AL → allows the 'AL' to be removed, converging it to 'MULTIDIMENSION' . This structured process ensures all suffix possibilities are investigated, providing thorough coverage through hierarchical rule application.

Steps 5a and 5b in the Porter Stemming algorithm are designed to apply final refinements to the stemmed result to ensure no excessive characters remain. In step 5a, conditions like (m>1) E → optimize suffix removal, handling cases where a final 'E' is unnecessarily lengthening the word, which is applicable for stems with 'm>1'. In step 5b, the condition (m>1 and *d and *L) → single letter targets stems ending in doubled consonants, ensuring the correct form is shortened to a single consonant, such as reducing 'CRUELLER' to 'CRUEL' . These steps adjust the stem to conform to minimal forms without trailing unnecessary suffixes.

The stem format [C](VC)m[V] in the Porter Stemming algorithm aids in understanding the repetition of consonant-vowel patterns in a word. For 'SYZYGY', recognizing consonants and vowels in its structure helps assess potential transformations. With no clear VC pattern repeating due to its unique sequence 'SYZY', the measure 'm' remains low (m=0), which restricts further reduction . This linguistic framework allows the algorithm to adjust treatment based on internal word phonetic structures, ensuring appropriate handling of less common words.

In the Porter Stemmer, conditions are used to test whether the stem satisfies certain criteria before suffixes are removed, thereby preventing inappropriate deletions. For example, a condition like 'm>1 and (*S or *T)' checks if the stem is long enough and ends with 'S' or 'T' before applying suffix removal like 'ION' . In a word like 'NATION', with 'm=2', the stem 'NAT' satisfies the condition 'm>1', allowing 'ION' to be removed properly to achieve 'NAT'. This ensures that suffix removal aligns with proper morphological and phonetic structures.

The precedence of the longest matching suffix rule ensures that the most specific and appropriate rule is applied during the stemming process, which can significantly affect the outcome. For 'CARESSES', the rule for 'SSES' being longer than 'SS' or 'S' takes precedence, mapping it to 'CARESS', which prevents over-stemming or incorrect shortening . This step ensures precision and accuracy in locating the optimal stem by following a hierarchy of specificity.

Consonants (C) and vowels (V) play a crucial role in the form representation [C](VC)m[V] used in the Porter Stemming algorithm, as they define the structure and repetition pattern within a word. This representation helps determine the measure 'm', which represents the number of times the VC sequence is repeated. For example, words like 'TREE' have an 'm' of 0 due to no repeated VC sequence, while 'TROUBLE' has an 'm' of 1 due to a single VC sequence . This calculation affects the possible suffixes that can be removed, influencing the final stem form of a word.

You might also like