A unifying framework for compressed pattern matching

Takuya Kida; Yusuke Shibata; Masayuki Takeda; Ayumi Shinohara; Setsuo Arikawa

doi:10.1109/SPIRE.1999.796582

A unifying framework for compressed pattern matching

Takuya Kida, Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

INF - System Information Sciences

Kyushu University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

33 Citations (Scopus)

Abstract

We introduce a general framework which is suitable to capture an essence of compressed pattern matching according to various dictionary based compressions, and propose a compressed pattern matching algorithm for the framework. The goal is to find all occurrences of a pattern in a text without decompression, which is one of the most active topics in string matching. Our framework includes such compression methods as Lempel-Ziv family, (LZ77, LZSS, LZ78, LZW) (J. Ziv and A. Lempel, 1978), byte-pair encoding, and the static dictionary based method. Technically, our pattern matching algorithm extends that for LZW compressed text presented by A. Amir et al. (1996).

Original language	English
Title of host publication	String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	89-96
Number of pages	8
ISBN (Electronic)	0769502687, 9780769502687
DOIs	https://doi.org/10.1109/SPIRE.1999.796582
Publication status	Published - 1999
Event	1999 String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999 - Cancun, Mexico Duration: 1999 Sept 22 → 1999 Sept 24

Publication series

Name	String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999

Conference

Conference	1999 String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999
Country/Territory	Mexico
City	Cancun
Period	99/9/22 → 99/9/24

Access to Document

10.1109/SPIRE.1999.796582

Cite this

Kida, T., Shibata, Y., Takeda, M., Shinohara, A., & Arikawa, S. (1999). A unifying framework for compressed pattern matching. In String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999 (pp. 89-96). Article 796582 (String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SPIRE.1999.796582

Kida, Takuya ; Shibata, Yusuke ; Takeda, Masayuki et al. / A unifying framework for compressed pattern matching. String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999. Institute of Electrical and Electronics Engineers Inc., 1999. pp. 89-96 (String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999).

@inproceedings{14a4a8df14c0450ab10abca7a3a5e0a9,

title = "A unifying framework for compressed pattern matching",

abstract = "We introduce a general framework which is suitable to capture an essence of compressed pattern matching according to various dictionary based compressions, and propose a compressed pattern matching algorithm for the framework. The goal is to find all occurrences of a pattern in a text without decompression, which is one of the most active topics in string matching. Our framework includes such compression methods as Lempel-Ziv family, (LZ77, LZSS, LZ78, LZW) (J. Ziv and A. Lempel, 1978), byte-pair encoding, and the static dictionary based method. Technically, our pattern matching algorithm extends that for LZW compressed text presented by A. Amir et al. (1996).",

author = "Takuya Kida and Yusuke Shibata and Masayuki Takeda and Ayumi Shinohara and Setsuo Arikawa",

note = "Publisher Copyright: {\textcopyright} 1999 IEEE.; 1999 String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999 ; Conference date: 22-09-1999 Through 24-09-1999",

year = "1999",

doi = "10.1109/SPIRE.1999.796582",

language = "English",

series = "String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "89--96",

booktitle = "String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999",

address = "United States",

}

Kida, T, Shibata, Y, Takeda, M, Shinohara, A & Arikawa, S 1999, A unifying framework for compressed pattern matching. in String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999., 796582, String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999, Institute of Electrical and Electronics Engineers Inc., pp. 89-96, 1999 String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999, Cancun, Mexico, 99/9/22. https://doi.org/10.1109/SPIRE.1999.796582

A unifying framework for compressed pattern matching. / Kida, Takuya; Shibata, Yusuke; Takeda, Masayuki et al.
String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999. Institute of Electrical and Electronics Engineers Inc., 1999. p. 89-96 796582 (String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A unifying framework for compressed pattern matching

AU - Kida, Takuya

AU - Shibata, Yusuke

AU - Takeda, Masayuki

AU - Shinohara, Ayumi

AU - Arikawa, Setsuo

PY - 1999

Y1 - 1999

N2 - We introduce a general framework which is suitable to capture an essence of compressed pattern matching according to various dictionary based compressions, and propose a compressed pattern matching algorithm for the framework. The goal is to find all occurrences of a pattern in a text without decompression, which is one of the most active topics in string matching. Our framework includes such compression methods as Lempel-Ziv family, (LZ77, LZSS, LZ78, LZW) (J. Ziv and A. Lempel, 1978), byte-pair encoding, and the static dictionary based method. Technically, our pattern matching algorithm extends that for LZW compressed text presented by A. Amir et al. (1996).

AB - We introduce a general framework which is suitable to capture an essence of compressed pattern matching according to various dictionary based compressions, and propose a compressed pattern matching algorithm for the framework. The goal is to find all occurrences of a pattern in a text without decompression, which is one of the most active topics in string matching. Our framework includes such compression methods as Lempel-Ziv family, (LZ77, LZSS, LZ78, LZW) (J. Ziv and A. Lempel, 1978), byte-pair encoding, and the static dictionary based method. Technically, our pattern matching algorithm extends that for LZW compressed text presented by A. Amir et al. (1996).

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

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

U2 - 10.1109/SPIRE.1999.796582

DO - 10.1109/SPIRE.1999.796582

M3 - Conference contribution

AN - SCOPUS:85013573073

T3 - String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999

SP - 89

EP - 96

BT - String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1999 String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999

Y2 - 22 September 1999 through 24 September 1999

ER -

Kida T, Shibata Y, Takeda M, Shinohara A, Arikawa S. A unifying framework for compressed pattern matching. In String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999. Institute of Electrical and Electronics Engineers Inc. 1999. p. 89-96. 796582. (String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999). doi: 10.1109/SPIRE.1999.796582

A unifying framework for compressed pattern matching

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this