A unifying framework for compressed pattern matching

Author

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

Author_Institution

Dept. of Inf., Kyushu Univ., Fukuoka, Japan

fYear

1999

fDate

1999

Firstpage

89

Lastpage

96

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)

Keywords

data compression; dictionaries; string matching; text analysis; LZW compressed text; Lempel-Ziv family; byte-pair encoding; compressed pattern matching; dictionary based compression; pattern matching algorithm; static dictionary based method; string matching; unifying framework; Abstracts; Automata; Data compression; Dictionaries; Encoding; Informatics; Pattern matching; Reactive power;

fLanguage

English

Publisher

ieee

Conference_Titel

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

Conference_Location

Cancun

Print_ISBN

0-7695-0268-7

Type

conf

DOI

10.1109/SPIRE.1999.796582

Filename

796582