Computing convolution on grammar-compressed text

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

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

5 被引用数 (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.

本文言語英語
ホスト出版物のタイトルProceedings - DCC 2013
ホスト出版物のサブタイトル2013 Data Compression Conference
出版社Institute of Electrical and Electronics Engineers Inc.
ページ451-460
ページ数10
ISBN(印刷版)9780769549651
DOI
出版ステータス出版済み - 2013
イベント2013 Data Compression Conference, DCC 2013 - Snowbird, UT, 米国
継続期間: 3月 20 20133月 22 2013

出版物シリーズ

名前Data Compression Conference Proceedings
ISSN(印刷版)1068-0314

その他

その他2013 Data Compression Conference, DCC 2013
国/地域米国
CitySnowbird, UT
Period3/20/133/22/13

!!!All Science Journal Classification (ASJC) codes

  • コンピュータ ネットワークおよび通信

フィンガープリント

「Computing convolution on grammar-compressed text」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル