A novel method for stemmer generation based on hidden markov models

ABSTRACT

In this paper, we present a method based on Hidden Markov Models (HMMs) to generate statistical stemmers. Using a list of words as training set, the method estimates the HMM parameters which are used to calculate the most probable stem for an arbitrary word. Stemming is performed by computing the most probable path, through the HMM states, corresponding to the input word. Linguistic knowledge or a training set of manually stemmed words are not required. We describe the method and the results of the experiments carried out using standard test collections for five different languages.

REFERENCES

• 1: J. Allan, editor. Challenges in Information Retrieval and Language Modeling, Report of a Workshop held at the Center for Intelligent Information Retrieval on September, 2002, University of Massachusetts, Amherst, MA, Published on April, 24th 2003 at http://ciir.cs.umass.edu/irchallenges/.
• 2: Michela Bacchin , Nicola Ferro , Massimo Melucci, The Effectiveness of a Graph-Based Algorithm for Stemming, Proceedings of the 5th International Conference on Asian Digital Libraries: Digital Libraries: People, Knowledge, and Technology, p.117-128, December 11-14, 2002
• 3: M. Braschler and B. Ripplinger. Stemming and decompounding for German text retrieval. In Proceedings of the European Conference on Information Retrieval Research (ECIR), pages 177--192, Pisa, Italy, 2003.
• 4: G. Di Nunzio, N. Ferro, M. Melucci, and N. Orio The University of Padova at CLEF 2003: Experiments to evaluate probabilistic models for automatic stemmer generation and query word translation Working Notes of the Cross-Language Evaluation Forum Workshop, in press.
• 5: W. B. Frakes, Stemming algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 6: John Goldsmith, Unsupervised learning of the morphology of a natural language, Computational Linguistics, v.27 n.2, p.153-198, June 2001 [doi>10.1162/089120101750300490]
• 7: D. Harman. How effective is suffixing. Journal of the American Society for Information Science, 42(1):7--15, 1991.
• 8: David A. Hull, Stemming algorithms: a case study for detailed evaluation, Journal of the American Society for Information Science, v.47 n.1, p.70-84, Jan. 1996 [doi>10.1002/(SICI)1097-4571(199601)47:1<70::AID-ASI7>3.3.CO;2-Q]
• 9: Wessel Kraaij , Renée Pohlmann, Viewing stemming as recall enhancement, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.40-48, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243209]
• 10: Robert Krovetz, Viewing morphology as an inference process, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.191-202, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160718]
• 11: J. Lovins. Development of a stemming algorithm. Mechanical Translation and Computational Linguistics, 11:22--31, 1968.
• 12: Lucene. The Lucene Search Engine. http://jakarta.apache.org/lucene/docs/index.html, 2003.
• 13: A. M. Mood, F. A. Graybill, and D. C. Boes. Introduction to the Theory of Statistics. McGraw-Hill, Inc., 1974.
• 14: C. D. Paice, Constructing literature abstracts by computer: techniques and prospects, Information Processing and Management: an International Journal, v.26 n.1, p.171-186, 1990 [doi>10.1016/0306-4573(90)90014-S]
• 15: M. Popovic and P. Willett. The effectiveness of stemming for natural language access to S lovene textual data. Journal of the American Society for Information Science, 43(5):384--390, 1992.
• 16: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 17: M. Porter. Snowball. http://www.snowball.tartarus.org/, May 2003.
• 18: M. F. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
• 19: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 20: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 21: Jacques Savoy, A stemming procedure and stopword list for general French corpora, Journal of the American Society for Information Science, v.50 n.10, p.944-952, 1999 [doi>10.1002/(SICI)1097-4571(1999)50:10<944::AID-ASI9>3.3.CO;2-H]
• 22: Páraic Sheridan , Jean Paul Ballerini, Experiments in multilingual information retrieval using the SPIDER system, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.58-65, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243213]
• 23: Jinxi Xu , W. Bruce Croft, Corpus-based stemming using cooccurrence of word variants, ACM Transactions on Information Systems (TOIS), v.16 n.1, p.61-81, Jan. 1998 [doi>10.1145/267954.267957]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Experimentation

Keywords:
HMM, hidden Markov models, multi-lingual information retrieval, stemming, unsupervised training