{'fraction_non_alphanumeric': 0.03723171265878231, 'fraction_numerical': 0.01401664476565922, 'mean_word_length': 5.139784946236559, 'pattern_counts': {'":': 0, '<': 0, '<?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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Entropy-Compressed Indexes for Multidimensional Pattern Matching

In this talk, we will discuss the challenges involved in developing a multidimensional generalizations of compressed text indexing structures. These structures depend on some notion of Burrows-Wheeler transform (BWT) for multiple dimensions, though naive generalizations do not enable multidimensional pattern matching. We study the 2D case to possibly highlight combinatorial properties that do not emerge in the 1D case. We also present related work in 2D pattern matching and indexing. Introduction Suffix arrays and suffix trees are ubiquitous data structures at the heart of several text and string algorithms. They are used in a wide variety of applications, including pattern matching, text and information retrieval, Web searching, and sequence analysis in computational biology [14]. Compressed suffix arrays [13, 18, 19] and opportunistic FM-indexes [7, 8] represent new trends in the design of advanced indexes for full-text searching of documents, in that they support the functionalities of suffix arrays and suffix trees, which are more powerful than classical inverted files, yet they also overcome the aforementioned space limitations by exploiting, in a novel way, the notion of text compressibility and the techniques developed for succinct data structures and bounded-universe dictionaries. Grossi and Vitter [13] developed the compressed suffix array using 2n log |Σ| bits in the worst case with o(m) searching time. Sadakane [18, 19] related the space bound to the order-0 empirical entropy H0. Ferragina and Manzini devised the FM-index [7, 8], which is based on the Burrows-Wheeler transform (BWT) and is the first to encode the index size with respect to the hth-order empirical entropy Hh of the text. Navarro [17] recently developed an index requiring 4nHh + o(n) bits, and boasts fast search. Grossi, Gupta, and Vitter [11] exploited the higher-order entropy Hh of the text to represent a compressed suffix array in just nHh + O(n log log n/ log|Σ| n) bits. The index is optimal in space, apart from lower-order terms, achieving asymptotically the empirical entropy of the text (with a multiplicative constant 1). These data structures also have practical significance, as detailed in [12].