Computing Convolution on Grammar-Compressed Text
Computing Convolution on Grammar-Compressed Text
复制标题
DOI：
10.1109/dcc.2013.53
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
Toshiya Tanaka;I. Tomohiro;Shunsuke Inenaga;H. Bannai;M. Takeda
中科院分区：
文献类型：
--
作者：
Toshiya Tanaka;I. Tomohiro;Shunsuke Inenaga;H. Bannai;M. Takeda
长度为N的文本串S和长度为m的模式串P之间的卷积可以通过FFT在O（Nlog m）时间内计算。众所周知，各种类型的近似字符串匹配问题都可以简化为卷积。在本文中，我们假设输入的文本字符串是在一个压缩的形式，作为一个直线程序（SLP），这是一个上下文无关的语法在乔姆斯基范式，推导出一个单一的字符串。给定大小为n的SLP S描述长度为N的文本S，以及长度为m的未压缩模式P，我们提出了一个简单的O（nm log m）-时间算法来计算S和P之间的卷积。然后，我们表明，这可以改进为O（min{nm，N - α} log m）时间，其中α ≥ 0是表示SLP捕获的长度为m的子串的冗余量的值。改进的关键是我们的新算法，计算之间的卷积一个trie的大小r和一个模式字符串P的长度m在O（rlog m）的时间。
The convolution between a text string S of length N and a pattern string P of length m can be computed in O(N log m) time by FFT. It is known that various types of approximate string matching problems are reducible to convolution. In this paper, we assume that the input text string is given in a compressed form, as a straight-line program (SLP), which is a context free grammar in the Chomsky normal form that derives a single string. Given an SLP S of size n describing a text S of length N, and an uncompressed pattern P of length m, we present a simple O(nm log m)-time algorithm to compute the convolution between S and P. We then show that this can be improved to O(min{nm, N - α} log m) time, where α ≥ 0 is a value that represents the amount of redundancy that the SLP captures with respect to the length-m substrings. The key of the improvement is our new algorithm that computes the convolution between a trie of size r and a pattern string P of length m in O(r log m) time.