Stemmer

From Free net encyclopedia

(Difference between revisions)

Revision as of 08:05, 27 March 2006
194.80.32.8 (Talk | contribs)

Next diff →

Current revision

Image:Mergefrom.gif It has been suggested that Stemming algorithm be merged into this article or section. ([[{{{2|: talk:Stemmer}}}|Discuss]])

A stemmer is a computer program or algorithm which determines a stem form of a given inflected (or, sometimes, derived) word form—generally a written word form. The stem need not be identical to the morphological root of the word; it is usually sufficient that related words map to the same stem, even if this stem is not in itself a valid root.

A stemmer for English, for example, should identify the string "cats" (and possibly "catlike", "catty" etc.) as based on the root "cat", and "stemmer", "stemming", "stemmed" as based on "stem".

English stemmers are fairly trivial (with only occasional problems, such as "dries" being the third-person singular present form of the verb "dry", "axes" being the plural of "axe" as well as "axis"); but stemmers become harder to design as the morphology, orthography, and character encoding of the target language becomes more complex. For example, an Italian stemmer is more complex than an English one (because of more possible verb inflections), a Russian one is more complex (more possible noun declensions), a Hebrew one is even more complex (due to non-catenative morphology and a writing system without vowels), and so on.

Stemmers are common elements in query systems such as Web search engines, since a user who runs a query on "daffodils" would probably also be interested in documents that contain the word "daffodil" (without the s). The effectiveness of stemming for English query systems is questionable, however. An alternative approach, based on searching for n-grams rather than stems, may be used instead.

A more complex approach to the problem of determining a stem of a word is lemmatisation. This process involves first determining the part of speech of a word, and applying different normalisation rules for each part of speech.

The first ever published stemmer was written by Julie Beth Lovins: Lovins JB (1968) Development of a stemming algorithm, Mechanical Translation and Computational Linguistics, 11: 22-31. This paper was remarkable for its early date, and had great influence on later work in this area.

A later stemmer was written by Martin Porter, and published in the July 1980 issue of the journal Program. This stemmer became very widely used, and became the de-facto standard algorithm used for English stemming. Dr Porter received the Tony Kent Strix award in 2000 for his work on stemming and information retrieval.

Many implementations of this algorithm were written and freely distributed. Unfortunately, many of these implementations contained subtle flaws, and as a result systems using these stemmers performed less well than they ought. To eliminate this source of error, around the year 2000 Martin Porter released an official free-software implementation of the algorithm. Over the next few years, he extended this work by building Snowball, a framework for writing stemming algorithms, and implemented an improved English stemmer together with stemmers for several other languages.

This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.

[edit]