Morphology by Machine
Computational Linguistics
Course 1 · Chapter 4 · Morphology by Machine
Chapter 2 asked what counts as a word. This chapter asks a harder question: when are walk, walks, walked and walking the same word? A search for one should probably find the others, and a frequency count should probably group them. The tools for that sit between simple string handling and full linguistic analysis.
Stemming
Wikipedia's Stemming article defines it as "the process of reducing inflected (or sometimes derived) words to their word stem, base or root form". A stem can be a fragment, not a dictionary word: the Porter algorithm reduces argue, argued, argues, arguing and argus to argu.
| Algorithm type | What the article says |
|---|---|
| Lookup table | quick and good with irregular forms, but every inflected form must be listed |
| Suffix stripping | rules such as removing "ed", "ing" or "ly"; easier to maintain but crude with irregular pairs like "ran" and "run" |
| Lemmatisation | first identifies a word's part of speech, then applies normalization rules for that category |
| Stochastic | probability models trained on pairs of roots and inflected forms |
| Hybrid | combinations, such as a small exception list backed by suffix stripping |
- The Porter stemmer. Martin Porter published it in the July 1980 issue of Program; it became "the de facto standard algorithm used for English stemming". Around 2000 he released an official free implementation and later built Snowball, a framework for writing stemmers.
- Over-stemming. The article says Porter reduces universal, university and universe to univers: related by etymology but now very different in meaning, so conflating them can hurt search relevance.
- Under-stemming. Porter reduces alumna and alumnae to alumna but leaves alumnus as alumnu and alumni as alumni, so these are not grouped.
- Hard languages. Hebrew and Arabic are described as still difficult: Hebrew has nonconcatenative morphology, a writing system without vowels, and needs prefix stripping. Highly inflected languages like Turkish can have hundreds of inflected forms per root.
- In search. Early results for English were limited, which led some researchers to consider stemming largely irrelevant; stemming may help more in other languages. Google adopted word stemming in 2003; before that, a search for "fish" would not return "fishing".
A toy suffix stripper
The Python below is my own, not the Porter algorithm, and I could not run Porter here (no library for it was installed), so I do not compare outputs. I ran this code and copied its output.
The walk family collapses as hoped. But running becomes runn (not a word, and different from the stem of runs), this becomes thi because it ends in s, studies becomes studi, and ran is left alone, exactly the "crude with irregular pairs" problem. The length check (>= 3) keeps bus intact, but it is a patch, and it will break something else.
Lemmatization
The Lemmatization article defines it as grouping a word's inflected forms so they can be analysed as one item, identified by the lemma, the base or dictionary form: walk, walking, walked and walks share the lemma walk. Computationally it determines the lemma from the intended meaning, which requires identifying the part of speech and the context. The page's examples: better has good as its lemma, a link stemming misses because it requires a dictionary lookup; meeting may be a noun or a verb form and lemmatization picks by context.
| Stemming | Lemmatization | |
|---|---|---|
| Works on | the word alone, without context | the word with its part of speech and context |
| Output | may not be a real word ("lazy" becomes "lazi") | a dictionary form |
| Cost | simpler and faster | depends on correct part-of-speech identification; efficient algorithms remain an open research area |
| In search | can improve recall but lowers precision | "a trivial way" is simple dictionary lookup |
The page also says languages with long compound words need rule-based systems, which can be hand-crafted or learned from annotated corpora. A lookup lemmatizer in miniature (my code, tiny dictionary):
The irregular forms come out right, because someone listed them. Tables is untouched, because nobody did: the Stemming article's lookup-table caveat that every inflected form must be listed. Real lemmatizers combine lists with rules.
Regular Expressions
The Regular expression article describes one as "a sequence of characters that specifies a match pattern in text", used for find and find-and-replace and for input validation. They "originated in 1951," when Stephen Cole Kleene described regular languages with his notation of "regular events"; Ken Thompson built the notation into the QED editor and later ed, which led to grep.
| Construct | Meaning (per the article) |
|---|---|
| Concatenation | elements in sequence match strings joined in order |
Alternation | | gray|grey matches either |
Kleene star * | zero or more; + is one or more, ? zero or one |
., [], ^, $ | any character except newline; one character from a set; start and end anchors |
- Power. Regular expressions describe regular languages and have the same expressive power as regular grammars; they match "exactly the class of languages accepted by deterministic finite automata".
- Warnings. Backtracking implementations can take exponential time on patterns such as
(a|aa)*b, which can enable a security problem called ReDoS. Features like backreferences go beyond regular languages.
A morphological use, again with my own code. This tiny analyser splits an ending off a word using patterns with a three-letter minimum for the stem:
Words come out as a stem plus a label, which is the shape of a real morphological analysis. The three-letter minimum protects bus, sing and need, but it also means red and sung would be handled by luck: the rule knows nothing about what is a real stem.
Finite-State Ideas
The Finite-state transducer article defines an FST as a finite-state machine with two tapes, an input and an output, which maps between two sets of symbols. A finite-state automaton, with a single tape, defines a set of accepted strings; a transducer defines a relation between sets of strings. It adds that FSTs are often used for phonological and morphological analysis in NLP, with letters going in and morphemes coming out, and names Ronald Kaplan, Lauri Karttunen, Martin Kay and Kimmo Koskenniemi as pioneers. Weighted FSTs are used in machine translation, speech recognition, speech synthesis and optical character recognition. The article mentions Koskenniemi's 1983 two-level morphology only in its references and gives no worked example of a transducer, so I do not explain either here.
My analyse function above is not a finite-state transducer, but it does the same kind of job: one string in, an analysis out. Connecting it to the FST idea is my own framing.
py -X utf8; I could not run the Porter algorithm itself, so I make no comparison between it and my stripper. Describing my analyser as doing "the same kind of job" as a transducer is my own framing.
Try It Yourself
Run strip_suffix on hoped, hopes and hoping. What do you get, why is it wrong, and what does the Stemming article say about stems that are not real words?
Add tables to the lemma dictionary and then try chairs. What does this show about the lookup approach, in the Stemming article's words?
📄 View solutionRun strip_suffix on universe, universal, university, alumnus and alumni. Compare with what the article says the Porter stemmer does with the same words, and say what you can and cannot conclude.
Chapter 4 Quick Reference
- Stemming: reduce to a stem by rule; stems need not be real words; over- and under-stemming happen
- Lemmatization: find the dictionary form; needs part of speech and context
- Regular expressions: patterns with concatenation, alternation and star; equivalent in power to finite automata
- Finite-state transducer: two tapes, a relation between strings; used for morphology