Practical Queries of a Massive n-gram Database

Practical Queries of a Massive n-gram Database Tobias Hawker School of Information Technologies University of Sydney NSW 2006, Australia toby@it.usyd.edu.au Mary Gardiner Centre for Language Technology Macquarie University gardiner@ics.mq.edu.au Andrew Bennetts Canonical Ltd. andrew@puzzling.org Abstract Large quantities of data are an increasingly essential resource for many Natural Lan- guage Processing techniques. The Web 1T corpus, a massive resource containing n- gram frequencies produced from one tril- lion words drawn from the World Wide Web, is a relatively new corpus whose size will increase performance on many data-hungry applications. In addition, a fixed resource of this kind reduces reliance on using web re- sults as experimental data, increasing repli- cability of researchers’ results. However, effectively utilising a resource of this size presents significant challenges. We discuss the challenges of using a data source of this magnitude, and describe strategies for overcoming these, including efficient ex- traction of queries including wildcards, and specialised data compression. We present a software suite, “Get 1T”, implementing these techniques, released as free software for use by the natural language research community, and others. 1 Introduction The size and quality of data used for statistical Nat- ural Language Processing can have a major impact on the results a system achieves (Banko and Brill, 2001). The World Wide Web gives researchers access to an unprecedented quantity of machine- readable natural language text. However, even for techniques that can take advantage of unannotated text, there is much more web data available than can normally be used, because this same size over- whelms the processing resources available to most researchers. One way of overcoming this practical problem is to use the processing resources of com- mercial search engines, by using the number of hits they report for frequency estimation — see for ex- ample Grefenstette (1999), Turney (2001), Keller and Lapata (2003) and Nakov and Hearst (2005). There are however several drawbacks to this ap- proach, recently highlighted by Kilgarriff (2007), particularly replicability of experiments. The recent release of the Web 1T corpus (Brants and Franz, 2006)1 presents an opportunity to ac- cess web-scale data for n-gram frequency estima- tion without the drawbacks of using a search en- gine. The corpus provides frequency counts for n- grams up to five tokens long, drawn from approxi- mately 1 trillion words of web data. Promising re- sults have already been achieved using this resource for Word Sense Disambiguation and Lexical Substi- tution (Hawker, 2007; Yuret, 2007) and for Noun- Phrase Bracketing (Vadas and Curran, 2007). However, the scale of even this distilled collec- tion of web data presents significant processing chal- lenges. Na¨ıve methods for extracting the desired in- formation from the corpus, such as linear search or keyword indexing, are hopelessly impractical, and even algorithms with good asymptotic performance such as binary search are limited in their applicabil- ity. Approaches that attempt to overcome the scaling problems by using indices for the set of discrete to- 1http://www.ldc.upenn.edu/Catalog/docs/ LDC2006T13/readme.txt Proceedings of the Australasian Language Technology Workshop 2007, pages 40-48 40 kens in …

Content truncated to 500 words