Article: Compressed index for a dynamic collection of texts
| Title | Compressed index for a dynamic collection of texts |
|---|---|
| Authors | Chan, HL1 Hon, WK1 Lam, TW1 |
| Issue Date | 2004 |
| Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| Citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3109, p. 445-456 [How to Cite?] |
| Abstract | Let T be a string with n characters over an alphabet of bounded size. The recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very efficient pattern matching [2, 4]. This paper extends the work on optimal-space indexing to a dynamic collection of texts. Precisely, we give a compressed index using O(n) bits where n is the total length of texts, such that searching for a pattern P takes O(|P| log n + occ log2 n) time where occ is the number of occurrences, and inserting or deleting a text T takes O(|T| log n) time. © Springer-Verlag 2004. |
| ISSN | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| References | References in Scopus |
| dc.contributor.author | Chan, HL |
|---|---|
| dc.contributor.author | Hon, WK |
| dc.contributor.author | Lam, TW |
| dc.date.accessioned | 2010-09-25T15:00:41Z |
| dc.date.available | 2010-09-25T15:00:41Z |
| dc.date.issued | 2004 |
| dc.description.abstract | Let T be a string with n characters over an alphabet of bounded size. The recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very efficient pattern matching [2, 4]. This paper extends the work on optimal-space indexing to a dynamic collection of texts. Precisely, we give a compressed index using O(n) bits where n is the total length of texts, such that searching for a pattern P takes O(|P| log n + occ log2 n) time where occ is the number of occurrences, and inserting or deleting a text T takes O(|T| log n) time. © Springer-Verlag 2004. |
| dc.description.nature | Link_to_subscribed_fulltext |
| dc.identifier.citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3109, p. 445-456 [How to Cite?] |
| dc.identifier.epage | 456 |
| dc.identifier.hkuros | 107889 |
| dc.identifier.issn | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| dc.identifier.scopus | eid_2-s2.0-35048868341 |
| dc.identifier.spage | 445 |
| dc.identifier.uri | http://hdl.handle.net/10722/93422 |
| dc.identifier.volume | 3109 |
| dc.language | eng |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| dc.publisher.place | Germany |
| dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| dc.relation.references | References in Scopus |
| dc.title | Compressed index for a dynamic collection of texts |
| dc.type | Article |
Author Affiliations
- The University of Hong Kong