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

Simple item page
dc.creatorBille, Philip
dc.creatorFagerberg, Rolf
dc.creatorGoertz, Inge Li
dc.date2006-09-15
dc.date2007-05-03
dc.date.accessioned2026-07-07T07:59:11Z
dc.date.available2026-07-07T07:59:11Z
dc.descriptionWe 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, which in practical applications are likely to be a bottleneck.
dc.identifierhttps://arxiv.org/abs/cs/0609085
dc.identifierhttp://arxiv.org/abs/cs/0609085
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/128278
dc.subjectData Structures and Algorithms
dc.titleImproved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
dc.typetext

Files

Collections

arXiv