TY - GEN

T1 - Towards approximate matching in compressed strings: Local subsequence recognition

AU - Tiskin, Alexander

PY - 2011/6/23

Y1 - 2011/6/23

N2 - A grammar-compressed (GC) string is a string generated by a context-free grammar. This compression model includes LZ78 and LZW compression as a special case. We consider the longest common subsequence problem and the local subsequence recognition problem on a GC-text against a plain pattern. We show that, surprisingly, both problems can be solved in time that is within a polylogarithmic factor of the best existing algorithms for the same problems on a plain text. In a wider context presented elsewhere, we use these results as a stepping stone to efficient approximate matching on a GC-text. © 2011 Springer-Verlag Berlin Heidelberg.

AB - A grammar-compressed (GC) string is a string generated by a context-free grammar. This compression model includes LZ78 and LZW compression as a special case. We consider the longest common subsequence problem and the local subsequence recognition problem on a GC-text against a plain pattern. We show that, surprisingly, both problems can be solved in time that is within a polylogarithmic factor of the best existing algorithms for the same problems on a plain text. In a wider context presented elsewhere, we use these results as a stepping stone to efficient approximate matching on a GC-text. © 2011 Springer-Verlag Berlin Heidelberg.

UR - http://www.scopus.com/inward/record.url?scp=79959299019&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-20712-9_32

DO - 10.1007/978-3-642-20712-9_32

M3 - Conference contribution

AN - SCOPUS:79959299019

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 401

EP - 414

BT - Computer Science – Theory and Applications (CSR 2011)

ER -