The Library
Faster Subsequence Recognition in Compressed Strings
Tools
Tools
Tools
Tiskin, Alexander. (2009) Faster Subsequence Recognition in Compressed Strings. Journal of Mathematical Sciences, 158 (5). pp. 759-769. ISSN 1072-3374
Full text not available from this repository.
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 > Computer Science |
| Journal or Publication Title: | Journal of Mathematical Sciences |
| Publisher: | Springer Verlag |
| ISSN: | 1072-3374 |
| Date: | 2009 |
| Volume: | 158 |
| Number: | 5 |
| Page Range: | pp. 759-769 |
| Identification Number: | 10.1007/s10958-009-9396-0 |
| Publication Status: | Published |
| Related URLs: | |
| URI: | http://wrap.warwick.ac.uk/id/eprint/47559 |
Actions (login required)
 |
View Item |
