Implement the first steps of a Porter-style stemmer, the classic way search engines merge word forms.
What to build
A program that stems each word with a fixed list of rules and reports how many distinct stems remain.
Requirements
- Words of three letters or fewer are not changed. Otherwise apply, in order: (1) plurals: ending
ssesbecomesss; elseiesbecomesi; else a finalsis dropped unless the word ends inss. - (2) If the word now ends in
ed, or else ining, and the part before that ending contains a vowel (a, e, i, o, u), remove the ending. Then, if the rest ends inat,bloriz, adde; otherwise, if it ends in a doubled letter that is not a vowel,l,sorz, drop one of the two letters. - (3) If the word ends in
yand the part before theycontains a vowel, change theytoi. - For each distinct input word, in order of first appearance, print
word -> stem. Then printdistinct words W, distinct stems S.
Input
One line of lowercase words.
Output
One line per distinct word, then the summary line.
Constraints
At most 200 words, each at most 30 letters.
Example
Input:
cats running hoped caresses ponies
Output:
cats -> cat
running -> run
hoped -> hop
caresses -> caress
ponies -> poni
distinct words 5, distinct stems 5
Why it works
Each rule removes an ending that changes the grammar but not the meaning, so related forms such as "connect", "connected" and "connecting" end up with the same stem; the vowel checks stop rules from eating short words such as "sing" and "bed".
Examples
cats running hoped caresses ponies
cats -> cat running -> run hoped -> hop caresses -> caress ponies -> poni distinct words 5, distinct stems 5
connect connected connecting connects happy
connect -> connect connected -> connect connecting -> connect connects -> connect happy -> happi distinct words 5, distinct stems 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Apply the rules in order to a working copy of the word; each rule looks at the result of the previous one.
Hint 2
`w.endswith(("at", "bl", "iz"))` checks several endings at once; a doubled letter is `w[-1] == w[-2]`.
Solution
Show one correct solution (try it yourself first)
VOWELS = "aeiou"
def has_vowel(s):
return any(c in VOWELS for c in s)
def stem(w):
if len(w) <= 3:
return w
if w.endswith("sses"):
w = w[:-2]
elif w.endswith("ies"):
w = w[:-2]
elif w.endswith("s") and not w.endswith("ss"):
w = w[:-1]
for ending in ("ed", "ing"):
if w.endswith(ending) and has_vowel(w[: -len(ending)]):
w = w[: -len(ending)]
if w.endswith(("at", "bl", "iz")):
w += "e"
elif len(w) >= 2 and w[-1] == w[-2] and w[-1] not in VOWELS + "lsz":
w = w[:-1]
break
if w.endswith("y") and has_vowel(w[:-1]):
w = w[:-1] + "i"
return w
seen, stems = [], []
for w in input().split():
if w in seen:
continue
seen.append(w)
s = stem(w)
if s not in stems:
stems.append(s)
print(f"{w} -> {s}")
print(f"distinct words {len(seen)}, distinct stems {len(stems)}")