NLP: A suffix-stripping stemmer

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 sses becomes ss; else ies becomes i; else a final s is dropped unless the word ends in ss.
  • (2) If the word now ends in ed, or else in ing, and the part before that ending contains a vowel (a, e, i, o, u), remove the ending. Then, if the rest ends in at, bl or iz, add e; otherwise, if it ends in a doubled letter that is not a vowel, l, s or z, drop one of the two letters.
  • (3) If the word ends in y and the part before the y contains a vowel, change the y to i.
  • For each distinct input word, in order of first appearance, print word -> stem. Then print distinct 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

Example 1 · Input
cats running hoped caresses ponies
Expected output
cats -> cat
running -> run
hoped -> hop
caresses -> caress
ponies -> poni
distinct words 5, distinct stems 5
Example 2 · Input
connect connected connecting connects happy
Expected output
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)}")

Lesson: Tokenization and normalization →