A faster algorithm for the computation of string convolutions using LZ78 parsing

作者：Freschi Valerio^*; Bogliolo Alessandro

来源：Information Processing Letters, 2010, 110(14-15): 609-613.

DOI：10.1016/j.ipl.2010.05.010

• String convolution
• Lempel-Ziv parsing
• Pattern matching
• Algorithms

String convolution between vectors of integers representing a pattern and a text is a widely used computational primitive in string processing. In this paper, we investigate the use of an algorithmic framework which exploits sequence repetitions (identified according to the Lempel-Ziv parsing technique, i.e., the LZ78 algorithm) to speed up conventional algorithms (based on Fast Fourier Transform) for the computation of convolution between a pattern and a text, when the text is long enough and the pattern is sufficiently small. In particular, we present a deterministic algorithm which, given a text T of length n (drawn from a constant size alphabet Sigma(T)) and a pattern P of length m (drawn from a constant size alphabet Z(P)), computes the convolution between P and T with time and space complexity O(n + nm/lognh), where h is the entropy of text T.

• 出版日期2010-7-1