Inverse Suffix Array Queries for 2-Dimensional Pattern Matching in Near-Compact Space
Inverse Suffix Array Queries for 2-Dimensional Pattern Matching in Near-Compact Space
复制标题
近紧空间中二维模式匹配的逆后缀数组查询
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Rahul Shah
中科院分区：
文献类型：
--
作者：
Dhrumil Patel;Rahul Shah
在二维（2D）模式匹配的问题中，文本被排列为矩阵M [1 .. n，1 ..n]，由n = n×n符号组成，该符号是从大小σ的字母集σ绘制的查询由一个M×M方形矩阵P [1 ..m，1 ..m]组成，从同一字母集σ绘制，任务是在M中找到P中的所有位置，其中P以（连续的）submatrix出现。这些图案可以具有任何大小，但只要它们的形状数据结构如后缀树，后缀阵列存在[5，8]，用于有效的模式匹配的任务。它们基于2D后缀的线性化工作，该后缀可以保留前缀匹配属性（即，每个图案匹配是某些后缀的前缀）。后缀数组（1D）是其对O（n log n）位的空间利用率，其中n是文本的大小在简洁的数据结构的领域，可以基于Burrows-Wheeler tansform和LF映射（或φ功能）开发后缀树和数组的压缩变体[7，4，15]实际上，实现了空间的O（nlogσ）位，这会产生与1D情况相似的问题，我们可以为2D模式匹配设计一个简洁的索引吗？有类似的洞穴 - 轮毂变换或LF映射？但是，在本文中尚未找到压缩，达到了与1D的复杂性。但是，有效的模式匹配简洁的文本索引设计基于两个1D压缩的后缀树，它需要（n log log n + n logσ）位置，比其幼稚的设计小得多，该设计虽然为O（n log n）位问题仍然是回避的，该索引对存在完整的2D简洁索引的存在充满希望，其所有功能与1D情况相似。
In a 2-dimensional (2D) pattern matching problem, the text is arranged as a matrix M [1 ..n, 1 ..n ] and consists of N = n × n symbols drawn from alphabet set Σ of size σ . The query consists of a m × m square matrix P [1 ..m, 1 ..m ] drawn from the same alphabet set Σ and the task is to find all the locations in M where P appears as a (contiguous) submatrix. The patterns can be of any size, but as long as they are square in shape data structures like suffix trees and suffix array exist [5, 8] for the task of efficient pattern matching. These are essentially 2D counterparts of classic suffix trees and arrays known for traditional 1-dimensional (1D) pattern matching. They work based on linearization of 2D suffixes which would preserve the prefix match property (i.e., every pattern match is a prefix of some suffix). The main limitation of the suffix trees and the suffix arrays (in 1D) was their space utilization of O ( N log N ) bits, where N is the size of the text. This was suboptimal compared to N log σ bits of space, which is information theoretic optimal for the text. With the advent of the field of succinct/compressed data structures, it was possible to develop compressed variants of suffix trees and array based on Burrows-Wheeler Tansform and LF-mapping (or Φ function) [7, 4, 15]. These data structures indeed achieve O ( N log σ ) bits of space or better. This gives rise to the question: analogous to 1D case, can we design a succinct or compressed index for 2D pattern matching? Can there be a 2D compressed suffix tree? Are there analogues of Burrows–Wheeler Transform or LF-mapping? The problem has been acknowledged for over a decade now and there have been a few attempts at applying Φ function [1] and achieving entropy based compression [10]. However, achieving the complexity breakthrough akin to 1D case has yet to be found. In this paper, we still do not know how to answer suffix array queries in O ( N log σ ) bits of space - which would have led to efficient pattern matching. However, for the first time, we show an interesting result that it is indeed possible to compute inverse suffix array (ISA) queries in near compact space in O ( polylog n ) time. Our 2D succinct text index design is based on two 1D compressed suffix trees and it takes O ( N log log N + N log σ ) bits of space which is much smaller than its naive design that takes O ( N log N ) bits. Although the main problem is still evasive, this index gives a hope on the existence of a full 2D succinct index with all functionalities similar to that of 1D case.