Extracting article text from the web with maximum subsequence segmentation

ABSTRACT

Much of the information on the Web is found in articles from online news outlets, magazines, encyclopedias, review collections, and other sources. However, extracting this content from the original HTML document is complicated by the large amount of less informative and typically unrelated material such as navigation menus, forms, user comments, and ads. Existing approaches tend to be either brittle and demand significant expert knowledge and time (manual or tool-assisted generation of rules or code), necessitate labeled examples for every different page structure to be processed (wrapper induction), require relatively uniform layout (template detection), or, as with Visual Page Segmentation (VIPS), are computationally expensive. We introduce maximum subsequence segmentation, a method of global optimization over token-level local classifiers, and apply it to the domain of news websites. Training examples are easy to obtain, both learning and prediction are linear time, and results are excellent (our semi-supervised algorithm yields an overall F1-score of 97.947%), surpassing even those produced by VIPS with a hypothetical perfect block-selection heuristic. We also evaluate against the recent CleanEval shared task with surprisingly good cross-task performance cleaning general web pages, exceeding the top "text-only" score (based on Levenshtein distance), 87.8% versus 84.1%.

REFERENCES

• 1: Brad Adelberg, NoDoSE—a tool for semi-automatically extracting structured and semistructured data from text documents, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.283-294, June 01-04, 1998, Seattle, Washington, United States
• 2: Orkut Buyukkokten , Hector Garcia-Molina , Andreas Paepcke, Accordion summarization for end-game browsing on PDAs and cellular phones, Proceedings of the SIGCHI conference on Human factors in computing systems, p.213-220, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365102]
• 3: Cai, D., Yu, S., Wen, J.R. and Ma, W.Y. Extracting content structure for web pages based on visual representation. APWeb 2003.
• 4: Cai, D., Yu, S., Wen, J.R. and Ma, W.Y. VIPS: a Vision-based Page Segmentation Algorithm. Microsoft Technical Report (MSR-TR-2003-79),2003
• 5: Deng Cai , Xiaofei He , Ji-Rong Wen , Wei-Ying Ma, Block-level link analysis, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009068]
• 6: Deng Cai , Shipeng Yu , Ji-Rong Wen , Wei-Ying Ma, Block-based web search, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009070]
• 7: Jinlin Chen , Baoyao Zhou , Jin Shi , Hongjiang Zhang , Qiu Fengwu, Function-based object model towards website adaptation, Proceedings of the 10th international conference on World Wide Web, p.587-596, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372161]
• 8: Liang Chen , Shaozhi Ye , Xing Li, Template detection for large scale search engines, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141534]
• 9: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 10: Fox, A., Goldberg, I., Gribble, S.D., Lee, D.C., Polito, A. and Brewer, E.A. Experience With Top Gun Wingman: A Proxy-Based Graphical Web Browser for the 3Com PalmPilot. Middleware 1998.
• 11: Nicholas Kushmerick, Wrapper induction: efficiency and expressiveness, Artificial Intelligence, v.118 n.1-2, p.15-68, April 2000 [doi>10.1016/S0004-3702(99)00100-9]
• 12: Alberto H. F. Laender , Berthier A. Ribeiro-Neto , Altigran S. da Silva , Juliana S. Teixeira, A brief survey of web data extraction tools, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565137]
• 13: Shian-Hua Lin , Jan-Ming Ho, Discovering informative content blocks from Web documents, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775134]
• 14: Liu, L., Pu, C. and Han, W. XWRAP: an XML-enabled wrapper construction system for Web information sources. ICDE 2000.
• 15: Ling Ma , Nazli Goharian , Abdur Chowdhury , Misun Chung, Extracting unstructured data from template generated web documents, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956961]
• 16: Marek, M., Pecina, P., Spousta, M. Web Page cleaning with Conditional Random Fields. WAC3 2007.
• 17: Kathleen R. McKeown , Regina Barzilay , David Evans , Vasileios Hatzivassiloglou , Judith L. Klavans , Ani Nenkova , Carl Sable , Barry Schiffman , Sergey Sigelman, Tracking and summarizing news on a daily basis with Columbia's Newsblaster, Proceedings of the second international conference on Human Language Technology Research, p.280-285, March 24-27, 2002, San Diego, California
• 18: Ion Muslea , Steven Minton , Craig A. Knoblock, Hierarchical Wrapper Induction for Semistructured Information Sources, Autonomous Agents and Multi-Agent Systems, v.4 n.1-2, p.93-114, March-June 2001 [doi>10.1023/A:1010022931168]
• 19: Porter, M.F. An algorithm for suffix stripping. Program, vol. 14, no. 3, pp. 130--137, 1980.
• 20: Punyakanok, V., Roth, D., Yih, W. and Zimak, D. Learning and inference over constrained output. IJCAI 2005.
• 21: Walter L. Ruzzo , Martin Tompa, A Linear Time Algorithm for Finding All Maximal Scoring Subsequences, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.234-241, August 06-10, 1999
• 22: Yi, L. and Liu, B. Web Page Cleaning for Web Mining through Feature Weighting. IJCAI-03.
• 23: Lan Yi , Bing Liu , Xiaoli Li, Eliminating noisy information in Web pages for data mining, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956785]
• 24: Shipeng Yu , Deng Cai , Ji-Rong Wen , Wei-Ying Ma, Improving pseudo-relevance feedback in web information retrieval using web page segmentation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775155]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Algorithms, Performance

Keywords:
maximum subsequence, page segmentation, text extraction