Parallel Suffix Arrays for Linguistic Pattern Search

Proceedings of Recent Advances in Natural Language Processing, pages 487–494, Hissar, Bulgaria, 12-14 September 2011. Parallel Suffix Arrays for Linguistic Pattern Search Johannes Goller Macmillan, Digital Science Chiyoda Bldg., 2-37 Ichigayatamachi Shinjuku-ku, Tokyo jogojapan@gmail.com Abstract The paper presents the results of an ana- lysis of the merits and problems of us- ing suffix arrays as an index data struc- ture for annotated natural-language cor- pora. It shows how multiple suffix arrays can be combined to represent layers of an- notation, and how this enables matches for complex linguistic patterns to be identi- fied in the corpus quickly and, for a large subclass of patterns, with greater theoreti- cal efficiency than alternative approaches. The results reported include construction times and retrieval times for an annotated corpus of 1.9 billion characters in length, and a range of example patterns of varying complexity. 1 Introduction Empirical linguistic studies require access to large corpora of text, and they benefit greatly when the text is stored in a form that enables the efficient re- trieval of specific elements, such as sentences that match a pattern defined by a linguist. The size and contents of the corpus, the type and structure of its annotations, and the form of patterns involved vary greatly; the present paper deals with the re- quirements of only a subset of linguistic studies, which are characterized as follows: • The corpus is large (hundreds of millions of words), but not extremely large (hundreds of millions of documents); • Annotations exist in any number of layers, for example a layer of part-of-speech (POS) an- notations and a layer of semantic role labels, but the annotations on each individual layer are non-overlapping and non-ambiguous; • A pattern is essentially a regular expression, made up of literals (to be matched against the text), annotations (each with a specification of the layer it is expected to be found in) and wildcard elements (“gaps”); • The retrieval results are expected to be de- livered within seconds or minutes (that is, not necessarily as fast as web search), and to be comprehensive (that is, to contain all matches, not only the top-N defined by some relevancy ranking); • New patterns are generated constantly, per- haps by many different users or automated programs in parallel, while the text is largely static. Corpus search engines that respond to a similar, albeit not identical, set of requirements include the Corpus Workbench1, WebCorp Linguist’s Search Engine2 and Manatee/Bonito (Rychl´y, 2007). The implementation of all of these systems relies on the principle of inverted files, which is the main al- ternative to the suffix arrays presented here3. Both approaches are described and briefly compared in section 2, a direct comparison is also available in (Puglisi et al., 2006). Sections 3 and 4 introduce the concept of parallel suffix arrays and describe how it enables annotations and complex pattern search, including patterns equivalent to finite state machines. Section 5 describes results obtained us- ing an actual implementation of parallel suffix ar- rays. 2 The …

Content truncated to 500 words