An Encoding for Order-Preserving Matching
An Encoding for Order-Preserving Matching
复制标题
一种保序匹配编码
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Rossano Venturini
中科院分区：
文献类型：
--
作者：
T. Gagie;G. Manzini;Rossano Venturini
编码数据结构存储了足够的信息来回答他们旨在支持但不足以恢复其基础数据集的查询。在本文中，我们给出了第一个编码数据结构，以解决订单保留模式匹配的具有挑战性的问题。这个问题仅在几年前才引入，但由于其在数据分析中的应用，已经引起了大大关注。如果其字符的相对顺序相同：例如（4、1、3、2）和（10、3、7、5）是一个保留订单的匹配，则说两个字符串被认为是订单的匹配。我们显示如何在大小sigma和常数c> = 1上给定一个字符串s [1..n] p [1..m]带有m> = log^c n，我们可以返回o（m）时间中s中p的订单保留次数。在绑定的同一时间内，我们还可以返回S中P的某些订单保留匹配的起始位置（如果存在这样的匹配）。如果log（sigma）= omega（log log n），我们证明我们的空间结合在最佳的恒定因素之内；如果log（Sigma）= Omega（log n），我们的查询时间是最佳的。我们的空间绑定与最坏情况下需要存储S本身所需的欧米茄（N log n）位对比，这是订单保留模式匹配的索引，而模式长度没有限制，或者即使对标准模式匹配的索引也有限制图案长度。此外，我们可以仅知道每个字符与O（log^c n）相邻字符相比的编码。
Encoding data structures store enough information to answer the queries they are meant to support but not enough to recover their underlying datasets. In this paper we give the first encoding data structure for the challenging problem of order-preserving pattern matching. This problem was introduced only a few years ago but has already attracted significant attention because of its applications in data analysis. Two strings are said to be an order-preserving match if the relative order of their characters is the same: e.g., (4, 1, 3, 2) and (10, 3, 7, 5) are an order-preserving match. We show how, given a string S[1..n] over an arbitrary alphabet of size sigma and a constant c >=1, we can build an O(n log log n)-bit encoding such that later, given a pattern P[1..m] with m >= log^c n, we can return the number of order-preserving occurrences of P in S in O(m) time. Within the same time bound we can also return the starting position of some order-preserving match for P in S (if such a match exists). We prove that our space bound is within a constant factor of optimal if log(sigma) = Omega(log log n); our query time is optimal if log(sigma) = Omega(log n). Our space bound contrasts with the Omega(n log n) bits needed in the worst case to store S itself, an index for order-preserving pattern matching with no restrictions on the pattern length, or an index for standard pattern matching even with restrictions on the pattern length. Moreover, we can build our encoding knowing only how each character compares to O(log^c n) neighbouring characters.