Computing convolution on grammar-compressed text

Toshiya Tanaka, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)


The convolution between a text string S of length N and a pattern string P of length m can be computed in Ο(N logm) 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 Ο(nmlogm)-time algorithm to compute the convolution between S and P. We then show that this can be improved to Ο(min{nm,N - α} logm) 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 Ο(r logm) time.

Original languageEnglish
Title of host publicationProceedings - DCC 2013
Subtitle of host publication2013 Data Compression Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Print)9780769549651
Publication statusPublished - 2013
Event2013 Data Compression Conference, DCC 2013 - Snowbird, UT, United States
Duration: Mar 20 2013Mar 22 2013

Publication series

NameData Compression Conference Proceedings
ISSN (Print)1068-0314


Other2013 Data Compression Conference, DCC 2013
Country/TerritoryUnited States
CitySnowbird, UT

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications


Dive into the research topics of 'Computing convolution on grammar-compressed text'. Together they form a unique fingerprint.

Cite this