Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The task of linear text segmentation is to split a large text document into shorter fragments, usually blocks of consecutive sentences. The algorithms that demonstrated the best performance for this task come at the price of high computational complexity. In our work we present an algorithm that has a computational complexity of O(n) with n being the number of sentences in a document. The performance of our approach is evaluated against algorithms of higher complexity using standard benchmark data sets and we demonstrate that our approach provides comparable accuracy.

REFERENCES

• 1: Doug Beeferman , Adam Berger , John Lafferty, Statistical Models for Text Segmentation, Machine Learning, v.34 n.1-3, p.177-210, Feb. 1999 [doi>10.1023/A:1007506220214]
• 2: Branimir K. Boguraev , Mary S. Neff, Discourse Segmentation in Aid of Document Summarization, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 3, p.3004, January 04-07, 2000
• 3: Thorsten Brants , Francine Chen , Ioannis Tsochantaridis, Topic-based document segmentation with probabilistic latent semantic analysis, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584829]
• 4: F. Choi, P. Wiemer-Hastings, and J. Moore. Latent semantic analysis for text segmentation. In In Proceedings of EMNLP, 2001.
• 5: F. Y. Y. Choi. Advances in domain independent linear text segmentation, 2000.
• 6: G. Dias and E. Alves. Unsupervised topic segmentation based on word co-occurrence and multi-word units for text summarization. In Proceedings of the ELECTRA Workshop associated to 28th ACM SIGIR Conference, Salvador, Brazil, pages 41--48, 2005.
• 7: S. T. Gries. Dispersions and adjusted frequencies in corpora. International Journal of Corpus Linguistics, 13(4):403--437.
• 8: Marti A. Hearst, TextTiling: segmenting text into multi-paragraph subtopic passages, Computational Linguistics, v.23 n.1, p.33-64, March 1997
• 9: M. A. Hearst. Multi-paragraph segmentation of expository text, 1994.
• 10: Oskari Heinonen, Optimal multi-paragraph text segmentation by dynamic programming, Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, August 10-14, 1998, Montreal, Quebec, Canada [doi>10.3115/980691.980814]
• 11: Xiang Ji , Hongyuan Zha, Domain-independent text segmentation using anisotropic diffusion and dynamic programming, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860494]
• 12: Athanasios Kehagias , Fragkou Pavlina , Vassilios Petridis, Linear text segmentation using a dynamic programming algorithm, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, April 12-17, 2003, Budapest, Hungary [doi>10.3115/1067807.1067831]
• 13: Yuhua Li , David McLean , Zuhair A. Bandar , James D. O'Shea , Keeley Crockett, Sentence Similarity Based on Semantic Nets and Corpus Statistics, IEEE Transactions on Knowledge and Data Engineering, v.18 n.8, p.1138-1150, August 2006 [doi>10.1109/TKDE.2006.130]
• 14: Lev Pevzner , Marti A. Hearst, A critique and improvement of an evaluation metric for text segmentation, Computational Linguistics, v.28 n.1, p.19-36, March 2002 [doi>10.1162/089120102317341756]
• 15: Jeffrey C. Reynar, Statistical models for topic segmentation, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.357-364, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034735]
• 16: K. Richmond and A. Smith. Detecting subject boundaries within text: A language independent statistical approach. In Brown University, Providence, Rhode Island, pages 47--54, 1997.
• 17: Caroline Sporleder , Mirella Lapata, Broad coverage paragraph segmentation across languages and domains, ACM Transactions on Speech and Language Processing (TSLP), v.3 n.2, p.1-35, July 2006 [doi>10.1145/1149290.1151098]
• 18: Bingjun Sun , Prasenjit Mitra , C. Lee Giles , John Yen , Hongyuan Zha, Topic segmentation with shared topic detection and alignment of multiple documents, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277778]
• 19: Masao Utiyama , Hitoshi Isahara, A statistical model for domain-independent text segmentation, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.499-506, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073076]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Keywords:
sentence similarity, sliding window, text segmentation