{'fraction_non_alphanumeric': 0.0342960944595822, 'fraction_numerical': 0.0064305177111716625, 'mean_word_length': 4.4388460778502274, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parallel Suffix Arrays for Corpus Exploration

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.


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 implementation 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 traditional 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.

Existing corpus search engines
The simplest method of corpus search is to search the text linearly, for example using finite state tools like "grep". If the text contains annotations, e.g. in XML, and is very large, using such tools involves writing complicated regular expressions and is time-consuming. Somewhat more advanced are concordance-building environments such as "Wordsmith" 1 and user interfaces for finite state matchers, such as "Unitex" 2 . The query response time of these systems depends directly on the size of the text and may range from several minutes to several hours for corpora with millions of words.
An approach that uses a real index and provides much faster access is to fit the corpus and all annotations into a relational database, as described by Mark Davies (Davies, 2004;Davies, 2003) and available as an online search tool for various large corpora with POS-annotations 3 . The relational databases store k-grams such that there is a separate data column for every individual token (k columns in total), and the POS-tag of every token in a separate column (another k columns). Queries representing sequences of surface tokens and POS-tags, up to k in length, can be performed as SQL queries against the database. The search engine returns (a) the frequency of the k-grams that matched, and (b) the surface string itself, which can be used for a subsequent search on a full-text index of the surface string to retrieve match contexts. Although a detailed performance analysis is not available, practical tests of the online tool show response times in the subsecond to 2 seconds range on a 100-million-token corpus, including network delays and display time. The disadvantage of the approach, however, is obviously that it is limited to sequential queries of up to k tokens in length ("k-slots-queries"). It does not enable regular expressions (except within each slot) or gap-filling techniques (see 4.2), and it requires tokenized input.
The most advanced corpus search methods currently available make use of inverted file indexes, i.e. the data structures that web search engines are based on (Witten et al., 1999). The earliest documented example of this approach appears to be the "Corpus Query System" (Christ, 1994), which maps each token and each tag that occurs in the text to a list of the positions at which it was found, and performs lookups in these position lists to find query matches. This is essentially an inverted file architecture; it was upgraded several times and is currently known as the IMS Workbench 4 . Another CSE using inverted files is the "Linguist's Search Engine" (LSE) of the WebCorp project (Renouf et al., 2007). The system is still being tested, and there are no detailed reports on its performance. A third system, which has been available as open-source software for many years, is "Manatee" (Rychlý, 2000;Rychlý, 2007) and its (non-open-source) extension, the "SketchEngine" (Kilgarriff et al., 2004), of which an online demo exists 5 .
Inverted-file based systems usually process simple queries in less than a second, even on very large corpora, and enable sequential queries and OR-queries of any length and including POS-tags or other elements that refer to pre-defined token-related annotations of the corpus. Like systems using the k-gram based approach described above, inverted-file based systems also require the corpus to be tokenized before they can index it.
The main advantages of the new approach described below are: (a) It does not require the text to be tokenized. Also annotations beginning or ending in the middle of tokens or spanning across multiple tokens are supported; (b) the system enables the full power of regular expressions and offers very good performance for gap-filling techniques (see in 4.2). The main disadvantage is its memory consumption; this and other pros and cons of the new approach are discussed in section 6.

Plain suffix arrays
A suffix array is any representation of the lexicographically sorted list of all suffixes of a text, where suffix is defined as any substring beginning somewhere in the text and ending at the end of the text, i.e. there are n suffixes in a text of length n. In the context of corpus search systems, the text is the concatenation of all documents and all sentences of the entire corpus, which means billions of characters in the case of a corpus like the BNC 6 . Rather than storing copies of all the substrings, the suffix array is usually represented as a list of n integers, each indicating the starting position of a suffix. An example of this is shown in fig. 1: The suffix array itself consists only of the integer list SA; the lower part of fig. 1 shows the strings corresponding to each position, written vertically. Suffix arrays have an important property related to substring searches: Given a text T , its suffix array SA and a search pattern P , the set of starting positions of matches for P in T forms a continuous range in SA, as each match is the initial part of a suffix of T . Because of the lexicographical sorting, these suffixes must be adjacent to each other in the suffix array. For example, the set of matches for substring ab in fig. 1 is the range [2; 3] of SA (corresponding to positions 4 and 1 of T ). This shall be called the range property of suffix arrays. For a long time, suffix arrays were not considered suitable for large-scale search problems, because no fast construction, retrieval or compression methods were available, so they were extremely hard to construct and use. During the past ten years, however, major progress was made in finding better construction and search algorithms: (a) Linear Construction: In 2003, three groups independently found methods to construct the suffix array in O(n) time (Kim et al., 2003;Ko and Aluru, 2003;Kärkkäinen and Sanders, 2003); (b) BW-Search: a new and better search procedure (Ferragina and Manzini, 2000), based on a new auxiliary data structure, the bwt (Burrows Wheeler Transform); (c) Wavelet trees: a new data structure which enables efficient access to certain properties of bwt (Grossi et al., 2003) and increases the speed of BW-search; (d) Various compression techniques for SA, which enable more space-efficient storage; for an overview, see (Navarro and Mäkinen, 2007).
As a result of these improvements, it is possible to identify the match range for any pattern P , m characters in length, in O(m) time 7 if BW-search and wavelet trees, but only weak compression are used. These new developments still have not solved the problem that searching the SA (and bwt) requires frequent random access to large data structures, hence these must be stored in memory, while disk access would cause inacceptable delays. But since servers equipped with more than 100 GB of main memory have become available, it is reasonable to resonsider suffix arrays, and to increase their potential by adding features required for CSEs: annotation support and pattern matching. The following sections describe how that can be done.

Parallel suffix arrays
The first step is to allow annotations to enter the index. Suppose a text T ∈ Σ * of length n is given, and one layer of r annotations Although in this example the annotations each relate to one word of the text, they could as well start and end in the middle of words or span across several words. However, I do, at this point, assume that annotations are non-overlapping. There are two ways to bring these annotations into the index for T : Method 1: Single-integer annotations. Three steps need to be performed: (1) Each distinct annotation label is mapped to a unique integer (e.g. using a hash table), that is, a new annotation alphabet Λ is created, in which each annotation is represented as one integer. (2) An extra integer is introduced in Λ, below represented by ∅, which is used as a dummy annotation for all areas of T that are not covered by any element of A (in the example above, this applies to the space characters between words). (3) A is replaced by a string A ∈ Λ * containing the new annotation symbols in the order of the T -positions they refer to, and a bitvector B T ↔A of length n indicating the starting positions of annotations relative to T . The example above now becomes: where V has been mapped to 1, Conj to 2, and so forth. The next step is to construct a suffix array SA A from the Λ-string A , along with bwt and wavelet trees. That enables fast searches for sequences consisting solely of annotations. It will later be shown how the bitvector is used to accomplish searches for mixed queries, i.e. queries containing both T -sequences and A-sequences.
Method 2: Complex annotations. Sometimes annotations are themselves complex and one would like to be able to search inside them, rather than mapping them to atomic integers. This is accomplished by appending a new character / ∈ Σ to every label a i as a separation mark, and then concatenating all labels to a new string A : In addition, two bitvectors B T ↔A and B A↔A are defined, the former in the same way as in method 1, while the latter is of length |A | and has a 1 wherever a new annotation starts in A : Again, a suffix array SA A for A enables searching for substrings of annotations as well as sequences of annotations. The -symbols prevent undesired matches across annotation-boundaries.
How the bitvectors are used for mixed T /A queries. Both the bitvector of method 1 and the bitvectors of method 2 need to undergo an indexation process, during which a rank index and a select index are generated for each bitvector, defined as follows: Let B be a bitvector and b its length, then rank B and select B are functions such that Using techniques described by (Jacobson, 1989), it is possible to construct, in O(b) time, data structures that implement these functions, such that a lookup can be performed in O(1) time and no more than b + o(b) bits of space are consumed in total (including the bitvector itself). In the case of single-integer annotations (method 1), rank B T ↔A and select B T ↔A are constructed; in the case of complex annotations, these and rank B A↔A and select B A↔A are constructed. In addition, in both cases the inverse suffix arrays for T and A must be computed and stored in memory: Given a suffix array SA, its inverse is defined as The array invSA can be generated from SA in linear time.
To see how these data structures work together, consider a mixed query σλ, where σ ∈ Σ * is a substring match against T and λ is a substring match against the annotations. We first assume that method 1 was used, hence that λ ∈ Λ * is a sequence of annotations mapped to integers. The next step is to search the suffix arrays and determine the match ranges (l σ , r σ ) for σ in SA T and (l λ , r λ ) for λ in SA A . Clearly, the number of occurrences of σ in T is occ σ = r σ − l σ , the number of matches for λ is occ λ = r λ − l λ . We must now check, for each σ-match, whether it is followed by a λ-match. Let l σ ≤ x < r σ one of the σ-matches. It begins at position p = SA T [x] of T and it is |σ| characters in length. Hence it is followed by a λ-match, if and only if an A-annotation starts at p + |σ| and that annotation corresponds to a λ-match in A , which is the case iff the corresponding position in A is a suffix in the match range (l λ , r λ ). We therefore verify: A-element starts at p: Is p a λ-match: If SA and invSA are available for random access, all of the above can be tested in O(1) time, hence it takes O(occ σ ) time to compute the set of σλ-matches from the two individual match ranges. Moreover, the procedure works in the reverse direction, too, starting from the λ-matches and determining those among them that are preceded by a σ-match (using select instead of rank; the time consumption becomes O(occ λ )). Hence it is possible to choose the matching direction according to whichever part of the query has fewer matches, i.e. let occ µ := min(occ σ , occ λ ), then the match combination can be computed in O(occ µ ) time. This is different when inverted files are used instead of suffix arrays, because they do not have the match range property. Verifying whether the position following a given match for σ is in the position list for λ requires a binary search of that list (O(log occ λ ) time), rather than a mere range check. Let occ M := max(occ σ , occ λ ), then the match combination generally takes O(occ µ log occ M ) time if inverted files are used.
This result can be extended to general sequential queries σ 1 λ 1 · · · σ m λ m of any length m: The match combination time depends only on the least frequent (i.e. most specific) element if suffix arrays are used, but it depends on the frequency of all elements if inverted files are used. In other words, suffix arrays have a least-frequency property for match combinations.
Moreover, it is possible to define gaps of fixed length (measured in terms of number of Tcharacters, or alternatively, as number of A-annotations) between the individual elements, e.g. a query like σ A:3 λ, indicating a distance of 3 arbitrarily A-annotated elements between σ and λ, can be evaluated in the same asymptotic time (because the length of the three wildcard elements following σ can be computed for each match candidate using rank and select, and then added to the candidate position p + |σ| + before making the match range check for λ).
The property also holds when complex annotations and method 2 are used, at least when searching for prefixes of annotations, rather than arbitrary substrings of them. The distance calculations must then be made using the rank/select indexes for B T ↔A to map positions between T and A, and those for B A↔A to compute the string length of annotations in A . If arbitrary substring matching in annotations is required, the match process is delayed by a factor related to the length of λ, as every position inside the annotation must be checked for being a possible match. I decided to name these data structures and methods parallel suffix arrays, because they are based on the idea to consider T and A as parallel (and to connect them through indexed bitvectors). Further generalization of this idea leads to a complete CSE which I will call sufex 8 .

General patterns
Multiple annotation layers It is straight-forward to add further layers of annotation, e.g. semantic or morphological information, constituent classes etc. Each layer A 1 , A 2 , . . . is represented by an annotation string A i , a bitvector B T ↔A i , and B A i ↔A i if it is complex. Direct mappings between layers A i , A j are unnecessary, as they can be emulated using B T ↔A i and B T ↔A j . Hence, total space consumption of the index grows in an additive manner as layers are added.
Branching queries When defining queries to a CSE it is important to be able to state alternatives to parts of the query. For example, one element of a larger query may be an expression that is supposed to either match a word annotated as verb, or alternatively, a form of "to be", followed by a participle (to indicate a verb in passive voice). Generally speaking, a query operator for alternatives, such as ⊕(e 1 , e 2 , . . . , e m ) , is required, defined to return the set of substrings of T that match one of the subexpressions e i . In traditional inverted-file based systems this is usually written as e 1 OR e 2 · · · OR e m . If all e i are distinct Σ-strings, the individual match sets for each e i are disjoint, and computing the final result set is simply a matter of concatenating them.
But if some of the e i refer to annotations or are themselves non-atomic, i.e. sequences or ⊕expressions, the individual match sets might not be disjoint, causing the end result to contain duplicate matches, which makes it difficult to read and might cause frequency counts to be wrong. Hence, duplicate elements must be detected and removed from the individual match sets. This can be done either by creating a searchable result set representation, such as a hash table or tree, and inserting each of the matches unless it has been inserted before; or, it can be done by creating a simpler, non-searchable result list and checking for each match for any e i whether it is also a match for one of the other e j , j < i. Both these methods are available when inverted files are used instead of suffix arrays, too, but if the second method is used, suffix arrays have an advantage because the member check for the e j , if it is atomic, involves only an O(1) range check, whereas it would be logarithmic for an inverted file.

Sequences of complex elements
In section 3, the least-frequency property was established for sequential queries, consisting of atomic elements and fixed-length-gaps, i.e. expressions like where e i ∈ Σ * , Λ * ; Q i ∈ {Σ, Λ}; x i integers. To reach the full power of regular expressions, it is important that such queries can also be processed if the e i are themselves complex, i.e. sequences or branching elements. This is indeed possible; the query then becomes a graph, and determining the least-frequent element, at which the matching should start, becomes a non-trivial problem. The number of matches of a sequence or branching subelement cannot be calculated accurately before the entire matching process has finished, but an upper bound can be determined: For a sequence, it is the frequency of its least-frequent subelement, for a branching element it is the sum of the frequencies of its branches. Based on this, it is possible to recursively determine the approximately best atomic subelement of the graph for the match combination process to begin. Once it has begun, the least-frequency property takes full effect during the processing of sequential substructures, and the range property accelerates the duplicate-checks where branching substructures are involved, as described above. Both is not the case with inverted files, hence the theoretical performance of sufex is, generally, superior even for the most complex query structures.
Iteration The final operation required for regular expressions is the iteration operator, which is denoted by (e) for any atomic or complex expression e. It corresponds to a sequence e T :0 e T :0 · · · T :0 e of undetermined length. Since all its elements are identical, the least-frequency property is preserved, even if the matching simply starts on the left end, or alternatively on the right end, and continues as long as new matches are found. Therefore, iteration elements can itself become part of complex queries, and the three operations Q:x , ⊕ and establish a query language with the power of regular expressions, over an annotated text with any number of annotation layers.

Gap-filling
In order to analyse linguistic patterns in specific contexts, it is desirable that not only substrings matching the entire query are identified, but that selected parts of the query, especially matches for gaps or annotation elements, can be extracted and separately returned as frequency lists. For example, if one wants to investigate the syntactic environment of "discussion", i.e. usages like "discussion on", "discussion with" etc., one might issue a query such as

Look-betweens and negation
Another feature related to gaps is the ability to define some of their content partially. For example, Sufex enables queries of the three types below: (a) e 1 (a) represents a gap of length x ≤ ≤ y elements of the annotation level Q; (b) specifies that somewhere inside the gap there must be a match for e 3 (positive look-between); (c) means there must be no match for e 3 in the gap (negative look-between). Without going into further detail, it should be noted that these types of queries can be readily incorporated into the matching process. 5 Sufex in practice

Construction
Sufex was implemented as a C++ program which takes as input a configuration file stating the number and types of annotation layers, and a file containing the text T with annotations in XML. In all tests reported here, three annotation layers were indexed: A POS (POS-annotations); A lem (baseforms of words, mapped to a 32-bit single-integer alphabet Λ lem ); A cPOS (POS along with morphological information; implemented as complex annotations). The index construction is performed by first establishing the parallel layers and bitvectors and then creating SA Q , invSA Q and the wavelet tree WVT Q for each layer Q ∈ {T, A POS , A lem , A cPOS }. For the construction of SA Q , a multi-threaded version of the DC-algorithm (Kärkkäinen et al., 2006) is used, invSA Q is computed in a trivial way in one pass over SA Q , and for WVT Q the multithreaded construction method described by (Goller, 2010) is used. All these steps take less than 15 min each even for corpora with billions of characters, except the constructions of SA Q and WVT Q . The running times for the latter two are given in table 1.
All tests were carried out on a large server with 4 AMD-Opteron CPUs (16 cores in total) and 128 GB of main memory. When the entire index is in RAM, total memory consumption was found to be approx. (0.06 · N )/1024 MB for a corpus of N characters with the three annotation layers described above. Hence, on a 32-bit server with about 3 GB of memory available for use by sufex, a corpus of ≈ 52 million characters (≈ 7 million words) can be processed efficiently 9 . Table 2 shows the processing times of several example queries. It demonstrates very clearly the effects of the least-frequency property: Queries that contain at least one relatively rare element, such as a specific word or lemma, are processed in much less than a second, whereas a query with atomic elements that are all very frequent takes much longer. When comparing these numbers to those of web search engines, it is important to remember that web search engines are designed to return only the N best results, typically N ≈ 2000. For the purpose of linguistic investigations, the user is generally interested in retrieving the complete result set, even if it means waiting for several minutes. But if necessary, partial result set retrieval could be implemented in sufex, and it would result in a significant reduction of response times.

Conclusion
Clearly sufex is able to process large annotated corpora and enable excellent query response times, which are generally in the subsecond range even for complex queries with many annotation elements, as long as the query contains at least one specific subelement. In this respect, sufex is superior to inverted file-based CSEs. Another important advantage is that neither annotation boundaries nor query elements need to be related to any kind of pretokenization of T . Note that this is useful not only when searching inside words, but also when searching for sequences of words or annotations: As long as they are all on the same layer, they can be searched for directly in SA, and no match combination process is required.
Drawbacks of the approach include: (a) Annotations must be defined as layers. Overlapping annotations are only possible if located on different layers. (b) High performance is only possible if the main data structures are loaded into RAM. This means that, at the present time, sufexbased CSEs for corpora with hundreds of millions of tokens require a relatively high, but not unrealistic, hardware investment. However, given its performance and flexibility, sufex is wellsuited for projects involving larger user-groups and joint research efforts of multiple institutions, which makes the availability of the necessary hardware budget more likely.
Sufex' gap-filling capabilities (4.2) allow it to be used not only interactively by linguists, but also by automated bootstrapping processes. For example, given a set S of words or patterns of interest, submitting a query g L sg R for each s ∈ S, where g L and g R are "gap-like" wildcard expressions for the left and right context, and having sufex generate frequency lists of the content found for g L and g R , makes it possible to iteratively refine a set of contexts, which in turn can be used to find further elements belonging to S. While such bootstrapping has already been used in many areas of NLP research, sufex improves it in two ways: (a) Contexts can be defined as complex expressions, including annotation symbols, rather than mere windows of N words; (b) Sufex is an index and provides answers within milliseconds (the more specific the queries become in the process, the faster the retrieval, due to the least-frequency property). It therefore has the potential to greatly facilitate the further development of such bootstrapping methods.