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

Philip Bille, Rolf Fagerberg, Inge Li Gørtz

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TitelCombinatorial Pattern Matching, 18th Annual Symposium, CPM 2007
RedaktørerBin Ma, Kaizhong Zhang
Antal sider11
Publikationsdato2007
Sider52-62
StatusUdgivet - 2007
BegivenhedAnnual Symposium on Combinatorial Pattern Matching -
Varighed: 24. aug. 2010 → …
Konferencens nummer: 18

Konference

KonferenceAnnual Symposium on Combinatorial Pattern Matching
Nummer18
Periode24/08/2010 → …
NavnLecture Notes in Computer Science
Vol/bind4580

Fingeraftryk

Approximate String Matching
Regular Expressions
Matching Problem
Compression
Trade-offs
Space-time
Likely
Text
Dictionary

Citer dette

Bille, P., Fagerberg, R., & Gørtz, I. L. (2007). Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts. I B. Ma, & K. Zhang (red.), Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007 (s. 52-62). Lecture Notes in Computer Science, Bind. 4580
Bille, Philip ; Fagerberg, Rolf ; Gørtz, Inge Li. / Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts. Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007. red. / Bin Ma ; Kaizhong Zhang. 2007. s. 52-62 (Lecture Notes in Computer Science, Bind 4580).
@inproceedings{5176cab0e7ec11dc9a76000ea68e967b,
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",
language = "English",
series = "Lecture Notes in Computer Science",
publisher = "Heinemann",
pages = "52--62",
editor = "Bin Ma and Kaizhong Zhang",
booktitle = "Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007",

}

Bille, P, Fagerberg, R & Gørtz, IL 2007, Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts. i B Ma & K Zhang (red), Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007. Lecture Notes in Computer Science, bind 4580, s. 52-62, Annual Symposium on Combinatorial Pattern Matching, 24/08/2010.

Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts. / Bille, Philip; Fagerberg, Rolf; Gørtz, Inge Li.

Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007. red. / Bin Ma; Kaizhong Zhang. 2007. s. 52-62 (Lecture Notes in Computer Science, Bind 4580).

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer 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

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.

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 52

EP - 62

BT - Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007

A2 - Ma, Bin

A2 - Zhang, Kaizhong

ER -

Bille P, Fagerberg R, Gørtz IL. Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts. I Ma B, Zhang K, red., Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007. 2007. s. 52-62. (Lecture Notes in Computer Science, Bind 4580).