A fully compressed pattern matching algorithm for simple collage systems

Shunsuke Inenaga; Ayumi Shinohara; Masayuki Takeda

doi:10.1142/S0129054105003728

A fully compressed pattern matching algorithm for simple collage systems

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda

INF - System Information Sciences

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

We study the fully compressed pattern matching problem (FCPM problem): Given T and P which are descriptions of text T and pattern P respectively, find the occurrences of P in T without decompressing T or P. This problem is rather challenging since patterns are also given in a compressed form. In this paper we present an FCPM algorithm for simple collage systems. Collage systems are a general framework representing various kinds of dictionary-based compressions in a uniform way, and simple collage systems are a subclass that includes LZW and LZ78 compressions. Collage systems are of the form (〈D, S〉, where D is a dictionary and S is a sequence of variables from D. Our FCPM algorithm performs in O(∥D∥ ² + mn log|S|) time, where n = |T| = ∥D∥ + |S| and m = |P|. This is faster than the previous best result of O(m ²n ²) time.

Original language	English
Pages (from-to)	1155-1166
Number of pages	12
Journal	International Journal of Foundations of Computer Science
Volume	16
Issue number	6
DOIs	https://doi.org/10.1142/S0129054105003728
Publication status	Published - 2005 Dec

Keywords

Algorithm
Collage systems
Fully compressed pattern matching
String processing
Text compression

Access to Document

10.1142/S0129054105003728

Cite this

@article{7136497ada094dd4b8ca74e62c0e2491,

title = "A fully compressed pattern matching algorithm for simple collage systems",

abstract = "We study the fully compressed pattern matching problem (FCPM problem): Given T and P which are descriptions of text T and pattern P respectively, find the occurrences of P in T without decompressing T or P. This problem is rather challenging since patterns are also given in a compressed form. In this paper we present an FCPM algorithm for simple collage systems. Collage systems are a general framework representing various kinds of dictionary-based compressions in a uniform way, and simple collage systems are a subclass that includes LZW and LZ78 compressions. Collage systems are of the form (〈D, S〉, where D is a dictionary and S is a sequence of variables from D. Our FCPM algorithm performs in O(∥D∥ 2 + mn log|S|) time, where n = |T| = ∥D∥ + |S| and m = |P|. This is faster than the previous best result of O(m 2n 2) time.",

keywords = "Algorithm, Collage systems, Fully compressed pattern matching, String processing, Text compression",

author = "Shunsuke Inenaga and Ayumi Shinohara and Masayuki Takeda",

note = "Funding Information: *Main part of this research was done when the author was visiting the Department of Computer Science, the University of Helsinki, Finland. tSupported by JSPS Research Fellowships for Young Scientists *Main part of this research was done when the author was working for the Department of Informatics, Kyushu University, Japan, and PRESTO, Japan Science and Technology Agency (JST).",

year = "2005",

month = dec,

doi = "10.1142/S0129054105003728",

language = "English",

volume = "16",

pages = "1155--1166",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "6",

}

TY - JOUR

T1 - A fully compressed pattern matching algorithm for simple collage systems

AU - Inenaga, Shunsuke

AU - Shinohara, Ayumi

AU - Takeda, Masayuki

N1 - Funding Information: *Main part of this research was done when the author was visiting the Department of Computer Science, the University of Helsinki, Finland. tSupported by JSPS Research Fellowships for Young Scientists *Main part of this research was done when the author was working for the Department of Informatics, Kyushu University, Japan, and PRESTO, Japan Science and Technology Agency (JST).

PY - 2005/12

Y1 - 2005/12

N2 - We study the fully compressed pattern matching problem (FCPM problem): Given T and P which are descriptions of text T and pattern P respectively, find the occurrences of P in T without decompressing T or P. This problem is rather challenging since patterns are also given in a compressed form. In this paper we present an FCPM algorithm for simple collage systems. Collage systems are a general framework representing various kinds of dictionary-based compressions in a uniform way, and simple collage systems are a subclass that includes LZW and LZ78 compressions. Collage systems are of the form (〈D, S〉, where D is a dictionary and S is a sequence of variables from D. Our FCPM algorithm performs in O(∥D∥ 2 + mn log|S|) time, where n = |T| = ∥D∥ + |S| and m = |P|. This is faster than the previous best result of O(m 2n 2) time.

AB - We study the fully compressed pattern matching problem (FCPM problem): Given T and P which are descriptions of text T and pattern P respectively, find the occurrences of P in T without decompressing T or P. This problem is rather challenging since patterns are also given in a compressed form. In this paper we present an FCPM algorithm for simple collage systems. Collage systems are a general framework representing various kinds of dictionary-based compressions in a uniform way, and simple collage systems are a subclass that includes LZW and LZ78 compressions. Collage systems are of the form (〈D, S〉, where D is a dictionary and S is a sequence of variables from D. Our FCPM algorithm performs in O(∥D∥ 2 + mn log|S|) time, where n = |T| = ∥D∥ + |S| and m = |P|. This is faster than the previous best result of O(m 2n 2) time.

KW - Algorithm

KW - Collage systems

KW - Fully compressed pattern matching

KW - String processing

KW - Text compression

UR - http://www.scopus.com/inward/record.url?scp=33746228626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746228626&partnerID=8YFLogxK

U2 - 10.1142/S0129054105003728

DO - 10.1142/S0129054105003728

M3 - Article

AN - SCOPUS:33746228626

SN - 0129-0541

VL - 16

SP - 1155

EP - 1166

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 6

ER -

A fully compressed pattern matching algorithm for simple collage systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this