Parallel Suffix Arrays for Corpus Exploration

Parallel Suffix Arrays for Corpus Exploration⋆ Johannes Goller Macmillan Limited Chiyoda Building, 2-37 Ichigayatamachi, Shinjuku-ku, Tokyo, 162-0843 Japan jogojapan@gmail.com Abstract. This paper describes how recently developed techniques for suffix array construc- tion and compression can be expanded to bring a new data structure, called parallel suffix array, into existence, which is suitable as an in-memory representation of large annotated corpora, enabling complex queries and fast extractions of the context of matching substrings. It is also shown how parallel suffix arrays are superior to existing corpus search engines, in particular when sequential queries and corpora that are hard to tokenize are involved. Keywords: Corpus search engine, suffix array, search engine for linguists 1 Introduction Corpus search engines (CSE) are in high demand for a number of reasons: (a) They help corpus linguists to obtain statistics and usage information for words, and they do this with much higher accuracy and flexibility than web search engines (cf. Kilgarriff, 2007); (b) they enable the im- plementation of automated or interactive linguistic tests, for example to verify whether certain generalized syntactic constructions, e.g. represented by finite state grammars, do or do not occur in large corpus samples; (c) if sufficiently powerful, they transform an annotated text corpus into a tool for data mining (cf. Ananiadou, 2009). CSEs accomplish these things in two steps: First, an index is constructed from annotated text, then queries are either manually inputted by users or generated by a separate process; the corpus search engine returns all matching substrings it finds for each query, either in random order, or sorted or grouped by user-defined criteria. It may also identify duplicate results and provide a frequency list of distinct matches. Existing CSEs differ from each other in several ways: (a) The kind of annotations they can process, (b) the complexity of queries, e.g. keyword search as opposed to regular expressions, (c) the data structures used inside the index. The choice of the data structure is significant, as it has a strong influence on how large the index grows in memory and how fast it can process queries. Fast query processing is important, esp. when large sets of auto-created query variations are processed, or when a multi-user system is designed to process many queries in parallel. Section 2 gives an overview of existing CSEs. Their underlying indexes are all based on tra- ditional relational databases or inverted file techniques. Section 3 describes parallel suffix arrays, a new data structure with very good theoretical performance for many types of complex queries, in many respects superior to existing data structures. Section 4 shows how the data structure can be expanded to a powerful CSE which will be called sufex. The final sections report on results of performance tests with a practical implementation of sufex and conclude with a brief discussion of its advantages and disadvantages. ⋆ At the time when this article was prepared, the author worked at the Centrum f¨ur Informations- und Sprachverar- beitung, Ludwig-Maximilians-Universit¨at M¨unchen, Germany. Copyright 2010 by Johannes Goller PACLIC 24 …

Content truncated to 500 words