TY - GEN

T1 - Threshold approximate matching in grammar-compressed strings

AU - Tiskin, Alexander

PY - 2014/1/1

Y1 - 2014/1/1

N2 - A grammar-compressed (GC) string is a string generated by a context-free grammar. This compression model captures many practical applications, and includes LZ78 and LZW compression as a special case. We give an efficient algorithm for threshold approximate matching on a GC-text against a plain pattern. Our algorithm improves on existing algorithms whenever the pattern is sufficiently long. The algorithm employs the technique of fast unit-Monge matrix distance multiplication, as well as a new technique for implicit unit-Monge matrix searching, which we believe to be of independent interest.

AB - A grammar-compressed (GC) string is a string generated by a context-free grammar. This compression model captures many practical applications, and includes LZ78 and LZW compression as a special case. We give an efficient algorithm for threshold approximate matching on a GC-text against a plain pattern. Our algorithm improves on existing algorithms whenever the pattern is sufficiently long. The algorithm employs the technique of fast unit-Monge matrix distance multiplication, as well as a new technique for implicit unit-Monge matrix searching, which we believe to be of independent interest.

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

M3 - Conference contribution

AN - SCOPUS:84978422577

SP - 124

EP - 138

BT - Proceedings of the Prague Stringology Conference 2014, PSC 2014

ER -