Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts

Philip Bille; Rolf Fagerberg; Inge Li Gørtz

doi:10.1007/978-3-540-73437-6_8

Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts

Philip Bille
, Rolf Fagerberg
, Inge Li Gørtz

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

Abstract

We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes. We present a time-space trade-off that leads to algorithms improving the previously known complexities for both problems. In particular, we significantly improve the space bounds. In practical applications the space is likely to be a bottleneck and therefore this is of crucial importance.

Original language	English
Title of host publication	Combinatorial Pattern Matching, Proceedings
Publisher	Springer
Publication date	2007
Pages	52-62
ISBN (Print)	978-3-540-73436-9
DOIs	https://doi.org/10.1007/978-3-540-73437-6_8
Publication status	Published - 2007
Event	18th Annual Symposium on Combinatorial Pattern Matching - London, Canada Duration: 9 Jul 2007 → 11 Jul 2007 Conference number: 18

Conference

Conference	18th Annual Symposium on Combinatorial Pattern Matching
Number	18
Country/Territory	Canada
City	London
Period	09/07/2007 → 11/07/2007

Series	Lecture Notes in Computer Science
Volume	4580
ISSN	0302-9743

Access to Document

10.1007/978-3-540-73437-6_8

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{21f03e668b1f4a1e8f1df5603e3a4891,

title = "Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts",

abstract = "We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes. We present a time-space trade-off that leads to algorithms improving the previously known complexities for both problems. In particular, we significantly improve the space bounds. In practical applications the space is likely to be a bottleneck and therefore this is of crucial importance.",

author = "Philip Bille and Rolf Fagerberg and G{\o}rtz, \{Inge Li\}",

year = "2007",

doi = "10.1007/978-3-540-73437-6\_8",

language = "English",

isbn = "978-3-540-73436-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "52--62",

booktitle = "Combinatorial Pattern Matching, Proceedings",

note = "18th Annual Symposium on Combinatorial Pattern Matching ; Conference date: 09-07-2007 Through 11-07-2007",

}

Bille, P, Fagerberg, R & Gørtz, IL 2007, Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts. in Combinatorial Pattern Matching, Proceedings. Springer, Lecture Notes in Computer Science, vol. 4580, pp. 52-62, 18th Annual Symposium on Combinatorial Pattern Matching, London, Canada, 09/07/2007. https://doi.org/10.1007/978-3-540-73437-6_8

Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts. / Bille, Philip; Fagerberg, Rolf; Gørtz, Inge Li.
Combinatorial Pattern Matching, Proceedings. Springer, 2007. p. 52-62 (Lecture Notes in Computer Science, Vol. 4580).

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

TY - GEN

T1 - Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts

AU - Bille, Philip

AU - Fagerberg, Rolf

AU - Gørtz, Inge Li

N1 - Conference code: 18

PY - 2007

Y1 - 2007

N2 - We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes. We present a time-space trade-off that leads to algorithms improving the previously known complexities for both problems. In particular, we significantly improve the space bounds. In practical applications the space is likely to be a bottleneck and therefore this is of crucial importance.

AB - We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes. We present a time-space trade-off that leads to algorithms improving the previously known complexities for both problems. In particular, we significantly improve the space bounds. In practical applications the space is likely to be a bottleneck and therefore this is of crucial importance.

U2 - 10.1007/978-3-540-73437-6_8

DO - 10.1007/978-3-540-73437-6_8

M3 - Article in proceedings

SN - 978-3-540-73436-9

T3 - Lecture Notes in Computer Science

SP - 52

EP - 62

BT - Combinatorial Pattern Matching, Proceedings

PB - Springer

T2 - 18th Annual Symposium on Combinatorial Pattern Matching

Y2 - 9 July 2007 through 11 July 2007

ER -

Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this