The Library
Faster Subsequence Recognition in Compressed Strings
Tools
Tiskin, Alexander (2009) Faster Subsequence Recognition in Compressed Strings. Journal of Mathematical Sciences, 158 (5). pp. 759-769. doi:10.1007/s10958-009-9396-0 ISSN 1072-3374.
PDF
fulltext.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (242Kb) |
Official URL: http://dx.doi.org/10.1007/s10958-009-9396-0
Abstract
Computation on compressed strings is one of the key approaches to processing massive data sets. We consider local subsequence recognition problems on strings compressed by straight-line programs (SLP), which is closely related to Lempel–Ziv compression. For an SLP-compressed text of length $\overline{m}$ , and an uncompressed pattern of length n, Cégielski et al. gave an algorithm for local subsequence recognition running in time $O\left( {\overline{m} n^2 \log n}\right)$. We improve the running time to $O\left( {\overline{m} n^{1.5} }\right)$. Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern in time $O\left( {\overline{m} n^{1.5} }\right)$; the same problem with a compressed pattern is known to be NP-hard.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Journal of Mathematical Sciences | ||||
Publisher: | Springer Verlag | ||||
ISSN: | 1072-3374 | ||||
Official Date: | 2009 | ||||
Dates: |
|
||||
Volume: | 158 | ||||
Number: | 5 | ||||
Page Range: | pp. 759-769 | ||||
DOI: | 10.1007/s10958-009-9396-0 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 21 December 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |