Stemming

Stemming is the process for reducing inflected (or sometimes derived) words to their stem, base or root 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. The algorithm has been a long-standing problem in computer science; the first paper on the subject was published in 1968. The process of stemming, often called conflation, is useful in search engines for query expansion or indexing and other natural language processing problems.

Stemming programs are commonly referred to as stemming algorithms or stemmers.

Examples

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". A stemming algorithm reduces the words "fishing", "fished", "fish", and "fisher" to the root word, "fish".

History

The first ever published stemmer was written by Julie Beth Lovins in 1968. [Julie Beth Lovins (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 was published in the July 1980 issue of the journal "Program". This stemmer was 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 the Porter stemming algorithm were written and freely distributed; however, many of these implementations contained subtle flaws. As a result, these stemmers did not match their potential. To eliminate this source of error, Martin Porter released an official [http://tartarus.org/~martin/PorterStemmer/ free-software implementation] of the algorithm around the year 2000. He extended this work over the next few years by building Snowball, a framework for writing stemming algorithms, and implemented an improved English stemmer together with stemmers for several other languages.

Algorithms

There are several types of stemming algorithms which differ in respect to performance and accuracy and how certain stemming obstacles are overcome.

Brute Force Algorithms

Brute force stemmers employ a lookup table which contains relations between root forms and inflected forms. To stem a word, the table is queried to find a matching inflection. If a matching inflection is found, the associated root form is returned.

Brute force approaches are criticized for their general lack of elegance in that no algorithm is applied that would more quickly converge on a solution. In other words, there are more operations performed during the search than should be necessary. Brute force searches consume immense amounts of storage to host the list of relations (relative to the task). The algorithm is only accurate to the extent that the inflected form already exists in the table. Given the number of words in a given language, like English, it is unrealistic to expect that all word forms can be captured and manually recorded by human action alone. Manual training of the algorithm is overly time-intensive and the ratio between the effort and the increase in accuracy is marginal at best.

Brute force algorithms do overcome some of the challenges faced by the other approaches. Not all inflected word forms in a given language "follow the rules" appropriately. While "running" might be easy to stem to "run" in a suffix stripping approach, the alternate inflection, "ran", is not. Suffix stripping algorithms are somewhat powerless to overcome this problem, short of increasing the number and complexity of the rules, but brute force algorithms only require storing a single extra relation between "run" and "ran". While that is true, this assumes someone bothered to store the relation in the first place, and one of the major problems of improving brute force algorithms is the coverage of the language.

Brute force algorithms are initially very difficult to design given the immense amount of relations that must be initially stored to produce an acceptable level of accuracy (the number can span well into the millions). However, brute force algorithms are easy to improve in that decreasing the stemming error is only a matter of adding more relations to the table. Someone with only a minor experience in linguistics is capable of improving the algorithm, unlike the suffix stripping approaches which require a solid background in linguistics.

For technical accuracy, some programs may use suffix stripping to generate the lookup table given a text corpus, and then only consult the lookup table when stemming. This is not regarded as a brute force approach, although a lookup table is involved.

uffix Stripping Algorithms

Suffix stripping algorithms do not rely on a lookup table that consists of inflected forms and root form relations. Instead, a typically smaller list of "rules" are stored which provide a path for the algorithm, given an input word form, to find its root form. Some examples of the rules include:

* if the word ends in 'ed', remove the 'ed'
* if the word ends in 'ing', remove the 'ing'
* if the word ends in 'ly', remove the 'ly'

Suffix stripping approaches enjoy the benefit of being much simpler to maintain than brute force algorithms, assuming the maintainer is sufficiently knowledgeable in the challenges of linguistics and morphology and encoding suffix stripping rules. Suffix stripping algorithms are sometimes regarded as crude given the poor performance when dealing with exceptional relations (like 'ran' and 'run'). The solutions produced by suffix stripping algorithms are limited to those lexical categories which have well known suffices with few exceptions. This, however, is a problem, as not all parts of speech have such a well formulated set of rules. Lemmatisation attempts to improve upon this challenge.

Lemmatisation Algorithms

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 normalization rules for each part of speech. The part of speech is first detected prior to attempting to find the root since for some languages, the stemming rules change depending on a word's part of speech.

This approach is highly conditional upon obtaining the correct lexical category (part of speech). While there is overlap between the normalization rules for certain categories, identifying the wrong category or being unable to produce the right category limits the added benefit of this approach over suffix stripping algorithms. The basic idea is that, if we are able to grasp more information about the word to be stemmed, then we are able to more accurately apply normalization rules (which are, more or less, suffix stripping rules).

tochastic Algorithms

Stochastic algorithms involve using probability to identify the root form of a word. Stochastic algorithms are trained (they "learn") on a table of root form to inflected form relations to develop a probabilistic model. This model is typically expressed in the form of complex linguistic rules, similar in nature to those in suffix stripping or lemmatisation. Stemming is performed by inputting an inflected form to the trained model and having the model produce the root form according to its internal ruleset, which again is similar to suffix stripping and lemmatisation, except that the decisions involved in applying the most appropriate rule, or whether or not to stem the word and just return the same word, or whether to apply two different rules sequentially, are applied on the grounds that the output word will have the highest probability of being correct (which is to say, the smallest probability of being incorrect, which is how it is typically measured).

Some lemmatisation algorithms are stochastic in that, given a word which may belong to multiple parts of speech, a probability is assigned to each possible part. This may take into account the surrounding words, called the context, or not. Context-free grammars do not take into account any additional information. In either case, after assigning the probabilities to each possible part of speech, the most likely part of speech is chosen, and from there the appropriate normalization rules are applied to the input word to produce the normalized (root) form.

Hybrid Approaches

Hybrid approaches use two or more of the approaches described above in unison. A simple example is a suffix tree algorithm which first consults a lookup table using brute force. However, instead of trying to store the entire set of relations between words in a given language, the lookup table is kept small and is only used to store a minute amount of "frequent exceptions" like "ran => run". If the word is not in the exception list, apply suffix stripping or lemmatisation and output the result.

Affix Stemmers

In linguistics, the term affix refers to either a prefix or a suffix. In addition to dealing with suffixes, several approaches also attempt to remove common prefixes. For example, given the word "indefinitely", identify that the leading "in" is a prefix that can be removed. Many of the same approaches mentioned earlier apply, but go by the name affix stripping.

Matching Algorithms

Such algorithms use a stem database (for example a set of documents that contain stem words). These stems, as mentioned above, are not necessarily valid words themselves (but rather common sub-strings, as the "brows" in "browse" and in "browsing"). In order to stem a word the algorithm tries to match it with stems from the database, applying various constraints, such as on the relative length of the candidate stem within the word (so that, for example, the short prefix "be", which is the stem of such words as "be", "been" and "being", would not be considered as the stem of the word "beside").

Language Challenges

While much of the early academic work in this area was focused on the English language (with significant use of the Porter Stemmer algorithm), many other languages have been investigated. [ [http://www.clef-campaign.org/2007/working_notes/DolamicCLEF2007.pdf] Dolamic, Savoy: Stemming Approaches for East European Languages (CLEF 2007)] [ [http://portal.acm.org/citation.cfm?doid=1141277.1141523 ] Savoy: Light stemming approaches for the French, Portuguese, German and Hungarian languages (SAC 2006) ISBN 1-59593-108-2] [ [http://www3.interscience.wiley.com/cgi-bin/abstract/10049677/ABSTRACT?CRETRY=1&SRETRY=0] Popovic & Willett: The Effectiveness of Stemming for Natural-Language Access to Slovene Textual Data (1992) Journal of the American Society for Information Science] [ [http://staff.science.uva.nl/~mdr/Publications/Files/clef2005-proc-adhoc.pdf] Stemming in Hungarian at CLEF 2005] [ [http://InformationR.net/ir/12-3/paper315.html] Viera, A.F.G. & Virgil, J.: Uma revisão dos algoritmos de radicalização em língua portuguesa (2007) Information Research, 12(3) paper 315.]

Hebrew and Arabic are still considered difficult research languages for stemming. 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.Fact|date=December 2007|date=December 2007.

Multilingual Stemming

Multilingual stemming applies morphological rules of two or more languages simultaneously instead of rules for only a single language when interpreting a search query. Commercial systems using multilingual stemming exist. [ [http://www.coveo.com/en/Support/articles/Information%20-%20CES4-060330-3%20-%20Understanding%20Stemming.htm "Understanding Stemming"] . Coveo Knowledge Base (2006)]

Error metrics

There are two error measurements in stemming algorithms, overstemming and understemming. Overstemming is an error where two separate inflected words are stemmed to the same root, but should not have been - a false positive. Understemming is an error where two separate inflected words should be stemmed to the same root, but are not - a false negative. Stemming algorithms attempt to minimize each type of error, although reducing one type can lead to increasing the other.

Applications

Information Retrieval

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 were soon found to be rather limited, however, and this has led early Information retrieval researchers to deem stemming irrelevant in general. [Ricardo Baeza-Yates and Berthier Ribeiro-Neto (1999). "Modern Information Retrieval". ACM Press/Addison Wesley.] An alternative approach, based on searching for n-grams rather than stems, may be used instead. Also, recent research has shown greater benefits for retrieval in other languages. [Jaap Kamps, Christof Monz, Maarten de Rijke and Börkur Sigurbjörnsson (2004). Language-dependent and Language-independent Approaches to Cross-Lingual Text Retrieval. In: C. Peters, J. Gonzalo, M. Braschler and M. Kluck, eds. "Comparative Evaluation of Multilingual Information Access Systems". Springer Verlag, pp. 152–165.] [Eija Airio (2006). Word normalization and decompounding in mono- and bilingual IR. Information Retrieval 9:249–271.]

Usage in commercial products

Many commercial companies have been using stemming since at least the 1980's and have produced algorithmic and lexical stemmers in many languages. [ [http://www.dtsearch.com/CS_DeveloperTools.html#languages] International Developer Tools. dtSearch] [ [http://technet2.microsoft.com/Office/en-us/library/87065c9d-d39d-479d-909b-02160ec6d7791033.mspx?mfr=true] Building Multilingual Solutions by using Sharepoint Products and Technologies. Microsoft Technet]

The Snowball stemmers have been compared with commercial lexical stemmers with varying results. [ [http://www.clef-campaign.org/2003/WN_web/19.pdf CLEF 2003: Stephen Tomlinson compared the Snowball stemmers with the Hummingbird lexical stemming (lemmatization) system.] ] [ [http://www.clef-campaign.org/2004/working_notes/WorkingNotes2004/21.pdf CLEF 2004: Stephen Tomlison "Finnish, Portuguese and Russian Retrieval with Hummingbird SearchServer"] ]

Google search adopted word stemming in 2003. [ [http://www.google.com/support/bin/static.py?page=searchguides.html&ctx=basics#stemming The Essentials of Google Search] . Web Search Help Center. Google Inc.] Previously a search for "fish" would not have returned "fishing". Other software search algorithms vary in their use of word stemming. Programs that simply search for substrings obviously will find "fish" in "fishing" but when searching for "fishes" will not find occurrences of the word "fish".

ee also

* Root (linguistics) - linguistic definition of the term "root"
* Stem (linguistics) - linguistic definition of the term "stem"
* Morphology (linguistics)
* Lemma (linguistics) - linguistic definition
* Lemmatization
* Lexeme
* Inflection
* Derivation - stemming is a form of reverse derivation
* Natural language processing - stemming is generally regarded as a form of NLP
* Text mining - stemming algorithms play a major role in commercial NLP software
* Computational linguistics

References

Further reading

* Dawson, J.L. (1974) "Suffix Removal for Word Conflation", Bulletin of the Association for Literary and Linguistic Computing, 2(3): 33-46
* Frakes, W.B. (1984) "Term Conflation for Information Retrieval", Cambridge University Press
* Frakes, W.B. & Fox, C.J. (2003) "Strength and Similarity of Affix Removal Stemming Algorithms", SIGIR Forum, 37: 26-30
* Frakes, W. B. (1992) "Stemming algorithms, Information retrieval: data structures and algorithms", Prentice-Hall, Inc., Upper Saddle River, NJ
* Hafer, M.A. & Weiss, S.F., (1974) "Word segmentation by letter successor varieties", Information Processing & Management 10 (11/12), 371-386.
* Harman, D., (1991) "How effective is suffixing?" Journal of the American Society for Information Science 42 (1), 7-15.
* Hull, D.A. (1996) "Stemming Algorithms – A Case Study for Detailed Evaluation", JASIS, 47(1): 70-84
* Hull, D.A. & Grefenstette, G. (1996) A" Detailed Analysis of English Stemming Algorithms", Xerox Technical Report
* Kraaij, W. & Pohlmann, R., 1996: "Viewing stemming as recall enhancement", in H-P. Frei, D. Harman, P. Schauble & R. Wilkinson (eds.), Proceedings of the 17th ACM SIGIR conference held at Zurich, August 18-22, pp.40-48.
* Krovetz, R. (1993) "Viewing Morphology as an Inference Process", In Proceedings of ACM-SIGIR93, pp191-203
* Lennon, M., Pierce, D.S., Tarry, B.D. & Willett, P. (1981) "An Evaluation of some Conflation Algorithms for Information Retrieval", Journal of Information Science, 3: 177-183
* Lovins, J. (1971) " [http://www.eric.ed.gov/sitemap/html_0900000b800c571a.html Error Evaluation for Stemming Algorithms as Clustering Algorithms] ", JASIS, 22: 28-40
* Lovins, J. B. "Development of a Stemming Algorithm." Mechanical Translation and Computational Linguistics 11, 1968, 22--31.
* Marie-Claire, J. and Smith, D. (2005) "Conservative stemming for search and indexing"
* Paice, C.D. (1990) " [http://www.comp.lancs.ac.uk/computing/research/stemming/paice/article.htm Another Stemmer] ", SIGIR Forum, 24: 56-61
* Paice, C.D. (1996) " [http://www3.interscience.wiley.com/cgi-bin/abstract/57804/ABSTRACT Method for Evaluation of Stemming Algorithms based on Error Counting] ", JASIS, 47(8): 632-649
* Popovic, M. and Willett, P., (1992) " [http://www3.interscience.wiley.com/cgi-bin/abstract/10049677/ABSTRACT The effectiveness of stemmng for natural language access to Slovene textual data] ", Journal of the American Society for Information Science, 43(5), 384-390.
* Porter, M.F. (1980) " [http://telemat.det.unifi.it/book/2001/wchange/download/stem_porter.html An Algorithm for Suffix Stripping] ", Program, 14(3): 130-137
* Savoy, J., (1993) " [http://www3.interscience.wiley.com/cgi-bin/abstract/10049824/ABSTRACT?CRETRY=1&SRETRY=0 Stemming of French words based on grammatical categories] " Journal of the American Society for Information Science, 44(1), 1-9.
* Ulmschneider, J.E. & Doszkocs, (1983) " [http://www.eric.ed.gov/sitemap/html_0900000b8007ea83.html A practical stemming algorithm for online search assistance] ", Online Review, 7(4), 301-318.
* Xu, J. & Croft, W.B., (1998) " [http://portal.acm.org/citation.cfm?doid=267954.267957 Corpus-based stemming using coocurrence of word variants] ", ACM Transactions on Information Systems, 16(1), 61-81.

External links

* [http://code.google.com/p/ir-themis/ Themis] - open source IR framework, includes Porter stemmer implementation (PostgreSQL, Java API)
* [http://www.utilitymill.com/utility/Porter_Stemming_Algorithm Web based Porter Stemming Algorithm implementation]
* [http://maya.cs.depaul.edu/~classes/ds575/porter.html Another web based Porter Stemming Algorithm implementation]
* [http://snowball.tartarus.org Snowball] - free stemming algorithms for many languages, includes source code, including stemmers for five romance languages
* [http://www.locknet.ro/projects/ann-ruby-stemmer Ruby-Stemmer] - Ruby extension to Snowball API
* [http://pecl.php.net/package/stem/ PECL] - PHP extension to the Snowball API
* [http://www.oleandersolutions.com/stemming.html Oleander Porter's algorithm] - stemming library in C++ released under BSD
* [http://www.cs.waikato.ac.nz/~eibe/stemmers/index.html Unofficial home page of the Lovins stemming algorithm] - with source code in a couple of languages
* [http://www.tartarus.org/~martin/PorterStemmer/index.html Official home page of the Porter stemming algorithm] - including source code in several languages
* [http://www.comp.lancs.ac.uk/computing/research/stemming/index.htm Official home page of the Lancaster stemming algorithm] - Lancaster University, UK
* [http://www.cmp.uea.ac.uk/Research/stemmer/ Official home page of the UEA-Lite Stemmer ] - University of East Anglia, UK
* [http://www.comp.lancs.ac.uk/computing/research/stemming/general/index.htm Overview of stemming algorithms]