YASS: Yet another suffix stripper

ABSTRACT

Stemmers attempt to reduce a word to its stem or root form and are used widely in information retrieval tasks to increase the recall rate. Most popular stemmers encode a large number of language-specific rules built over a length of time. Such stemmers with comprehensive rules are available only for a few languages. In the absence of extensive linguistic resources for certain languages, statistical language processing tools have been successfully used to improve the performance of IR systems. In this article, we describe a clustering-based approach to discover equivalence classes of root words and their morphological variants. A set of string distance measures are defined, and the lexicon for a given text collection is clustered using the distance measures to identify these equivalence classes. The proposed approach is compared with Porter's and Lovin's stemmers on the AP and WSJ subcollections of the Tipster dataset using 200 queries. Its performance is comparable to that of Porter's and Lovin's stemmers, both in terms of average precision and the total number of relevant documents retrieved. The proposed stemming algorithm also provides consistent improvements in retrieval performance for French and Bengali, which are currently resource-poor.

REFERENCES

• 1: Adamson, G. and Boreham, J. 1974. The use of an association measure based on character structure to identify semantically related pairs of words and document titles. Inf. Stor. Retrieval 10, 253--260.
• 2: Michela Bacchin , Nicola Ferro , Massimo Melucci, A probabilistic model for stemmer generation, Information Processing and Management: an International Journal, v.41 n.1, p.121-137, January 2005 [doi>10.1016/j.ipm.2004.04.006]
• 3: Buckley, C., Singhal, A., and Mitra, M. 1996. Using query zoning and correlation within SMART: TREC 5. In the 5th Text Retrieval Conference.
• 4: Buckley, C., Singhal, A., and Mitra, M. 1995. New retrieval approaches using SMART: TREC 4. In the 4th Text Retrieval Conference.
• 5: Fredric Gey , Noriko Kando , Carol Peters, Cross language information retrieval: a research roadmap, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792564]
• 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: John A. Goldsmith , Derrick Higgins , Svetlana Soglasnova, Automatic Language-Specific Stemming in Information Retrieval, Revised Papers from the Workshop of Cross-Language Evaluation Forum on Cross-Language Information Retrieval and Evaluation, p.273-284, September 21-22, 2000
• 8: Hsu, J. 1986. Multiple Comparisons: Theory and Methods. Chapman and Hall.
• 9: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 10: Robert Krovetz, Viewing morphology as an inference process, Artificial Intelligence, v.118 n.1-2, p.277-294, April 2000 [doi>10.1016/S0004-3702(99)00101-0]
• 11: Leah S. Larkey , Lisa Ballesteros , Margaret E. Connell, Improving stemming for Arabic information retrieval: light stemming and co-occurrence analysis, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564425]
• 12: Levenstein, V. I. 1966. Binary codes capable of correcting deletions, insertions and reversals. Commun. ACM 27, 4, 358--368
• 13: Lovins, J. 1968. Development of a stemming algorithm. Mech. Trans. Comput. Linguis. 11, 22--31.
• 14: Majumder, P., Mitra, M., and Chaudhuri, B. 2004. Construction and statistical analysis of an Indic language corpus for applied language research. Computing Science Tech. Rep. TR/ISI/CVPR/01/2004, CVPR Unit, Indian Statistical Institute, Kolkata.
• 15: Douglas W. Oard , Gina-Anne Levow , Clara I. Cabezas, CLEF Experiments at Maryland: Statistical Stemming and Backoff Translation, Revised Papers from the Workshop of Cross-Language Evaluation Forum on Cross-Language Information Retrieval and Evaluation, p.176-187, September 21-22, 2000
• 16: Porter, M. F. 1980. An algorithm for suffix stripping. Program 14, 3, 130--137.
• 17: Ramanathan, A. and Rao, D. 2003. A lightweight stemmer for Hindi. In Proceedings of the 10th Conference of the European Chapter of the Association for Computational Linguistics (EACL), on Computatinal Linguistics for South Asian Languages (Budapest, Apr.) Workshop.
• 18: Anne N. de Roeck , Waleed Al-Fares, A morphologically sensitive clustering algorithm for identifying Arabic roots, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.199-206, October 03-06, 2000, Hong Kong [doi>10.3115/1075218.1075244]
• 19: Monica Rogati , Scott McCarley , Yiming Yang, Unsupervised learning of Arabic stemming using a parallel corpus, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.391-398, July 07-12, 2003, Sapporo, Japan [doi>10.3115/1075096.1075146]
• 20: G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 21: 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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Linguistic processing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Bengali, French, Indian languages, clustering, corpus, stemming, string similarity