SpringerLink - Book Chapter

Pattern Matching in Text Compressed by Using Antidictionaries

Book Series

Lecture Notes in Computer Science

Publisher

Springer Berlin / Heidelberg

ISSN

0302-9743 (Print) 1611-3349 (Online)

Volume

Volume 1645/1999

Book

Combinatorial Pattern Matching

DOI

10.1007/3-540-48452-3

1999

ISBN

978-3-540-66278-5

DOI

10.1007/3-540-48452-3_3

Pages

37-49

Subject Collection

Computer Science

SpringerLink Date

Friday, January 01, 1999

Pattern Matching in Text Compressed by Using Antidictionaries

Yusuke Shibata⁶, Masayuki Takeda⁶, Ayumi Shinohara⁶ and Setsuo Arikawa⁶

(6)	Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan

Abstract

In this paper we focus on the problem of compressed pattern matching for the text compression using antidictionaries, which is a new compression scheme proposed recently by Crochemore et al. (1998). We show an algorithm which preprocesses a pattern of length m and an antidictionary M in O(m ² + ‖M‖) time, and then scans a compressed text of length n in O(n + r) time to find all pattern occurrences, where ‖M‖ is the total length of strings in M and r is the number of the pattern occurrences.

Yusuke Shibata
Email: yusuke@i.kyushu-u.ac.jp
URL: http://www.i.kyushu-u.ac.jp

Masayuki Takeda
Email: takeda@i.kyushu-u.ac.jp
URL: http://www.i.kyushu-u.ac.jp

Ayumi Shinohara
Email: ayumi@i.kyushu-u.ac.jp
URL: http://www.i.kyushu-u.ac.jp

Setsuo Arikawa
Email: arikawa@i.kyushu-u.ac.jp
URL: http://www.i.kyushu-u.ac.jp

Pattern Matching in Text Compressed by Using Antidictionaries

Fulltext Preview (Small, Large)