**Article:**A space and time efficient algorithm for constructing compressed suffix arrays

Title | A space and time efficient algorithm for constructing compressed suffix arrays |
---|---|

Authors | Hon, WK2 Lam, TW2 Sadakane, K1 Sung, WK3 Yiu, SM2 |

Keywords | Compression Construcion Pattern mathching Text indexing |

Issue Date | 2007 |

Publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm |

Citation | Algorithmica (New York), 2007, v. 48 n. 1, p. 23-36 [How to Cite?] DOI: http://dx.doi.org/10.1007/s00453-006-1228-8 |

Abstract | With the first human DNA being decoded into a sequence of about 2.8 billion characters, much biological research has been centered on analyzing this sequence. Theoretically speaking, it is now feasible to accommodate an index for human DNA in the main memory so that any pattern can be located efficiently. This is due to the recent breakthrough on compressed suffix arrays, which reduces the space requirement from O(n log n) bits to O(n) bits. However, constructing compressed suffix arrays is still not an easy task because we still have to compute suffix arrays first and need a working memory of O(n log n) bits (i.e., more than 13 gigabytes for human DNA). This paper initiates the study of constructing compressed suffix arrays directly from the text. The main contribution is a construction algorithm that uses only O(n) bits of working memory, and the time complexity is O(n log n). Our construction algorithm is also time and space efficient for texts with large alphabets such as Chinese or Japanese. Precisely, when the alphabet size is |∑|, the working space is O(n log |∑|) bits, and the time complexity remains O(n log n), which is independent of |∑|. © Springer 2007. |

ISSN | 0178-4617 2012 Impact Factor: 0.488 2012 SCImago Journal Rankings: 1.214 |

DOI | http://dx.doi.org/10.1007/s00453-006-1228-8 |

ISI Accession Number ID | WOS:000246152800002 |

References | References in Scopus |

DC Field | Value |
---|---|

dc.contributor.author | Hon, WK |

dc.contributor.author | Lam, TW |

dc.contributor.author | Sadakane, K |

dc.contributor.author | Sung, WK |

dc.contributor.author | Yiu, SM |

dc.date.accessioned | 2010-09-06T09:50:31Z |

dc.date.available | 2010-09-06T09:50:31Z |

dc.date.issued | 2007 |

dc.description.abstract | With the first human DNA being decoded into a sequence of about 2.8 billion characters, much biological research has been centered on analyzing this sequence. Theoretically speaking, it is now feasible to accommodate an index for human DNA in the main memory so that any pattern can be located efficiently. This is due to the recent breakthrough on compressed suffix arrays, which reduces the space requirement from O(n log n) bits to O(n) bits. However, constructing compressed suffix arrays is still not an easy task because we still have to compute suffix arrays first and need a working memory of O(n log n) bits (i.e., more than 13 gigabytes for human DNA). This paper initiates the study of constructing compressed suffix arrays directly from the text. The main contribution is a construction algorithm that uses only O(n) bits of working memory, and the time complexity is O(n log n). Our construction algorithm is also time and space efficient for texts with large alphabets such as Chinese or Japanese. Precisely, when the alphabet size is |∑|, the working space is O(n log |∑|) bits, and the time complexity remains O(n log n), which is independent of |∑|. © Springer 2007. |

dc.description.nature | Link_to_subscribed_fulltext |

dc.identifier.citation | Algorithmica (New York), 2007, v. 48 n. 1, p. 23-36 [How to Cite?] DOI: http://dx.doi.org/10.1007/s00453-006-1228-8 |

dc.identifier.citeulike | 4736346 |

dc.identifier.doi | http://dx.doi.org/10.1007/s00453-006-1228-8 |

dc.identifier.epage | 36 |

dc.identifier.hkuros | 128171 |

dc.identifier.isi | WOS:000246152800002 |

dc.identifier.issn | 0178-4617 2012 Impact Factor: 0.488 2012 SCImago Journal Rankings: 1.214 |

dc.identifier.issue | 1 |

dc.identifier.openurl | |

dc.identifier.scopus | eid_2-s2.0-34547375123 |

dc.identifier.spage | 23 |

dc.identifier.uri | http://hdl.handle.net/10722/88951 |

dc.identifier.volume | 48 |

dc.language | eng |

dc.publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm |

dc.publisher.place | United States |

dc.relation.ispartof | Algorithmica (New York) |

dc.relation.references | References in Scopus |

dc.subject | Compression |

dc.subject | Construcion |

dc.subject | Pattern mathching |

dc.subject | Text indexing |

dc.title | A space and time efficient algorithm for constructing compressed suffix arrays |

dc.type | Article |

<?xml encoding="utf-8" version="1.0"?> <item><contributor.author>Hon, WK</contributor.author> <contributor.author>Lam, TW</contributor.author> <contributor.author>Sadakane, K</contributor.author> <contributor.author>Sung, WK</contributor.author> <contributor.author>Yiu, SM</contributor.author> <date.accessioned>2010-09-06T09:50:31Z</date.accessioned> <date.available>2010-09-06T09:50:31Z</date.available> <date.issued>2007</date.issued> <identifier.citation>Algorithmica (New York), 2007, v. 48 n. 1, p. 23-36</identifier.citation> <identifier.issn>0178-4617</identifier.issn> <identifier.uri>http://hdl.handle.net/10722/88951</identifier.uri> <description.abstract>With the first human DNA being decoded into a sequence of about 2.8 billion characters, much biological research has been centered on analyzing this sequence. Theoretically speaking, it is now feasible to accommodate an index for human DNA in the main memory so that any pattern can be located efficiently. This is due to the recent breakthrough on compressed suffix arrays, which reduces the space requirement from O(n log n) bits to O(n) bits. However, constructing compressed suffix arrays is still not an easy task because we still have to compute suffix arrays first and need a working memory of O(n log n) bits (i.e., more than 13 gigabytes for human DNA). This paper initiates the study of constructing compressed suffix arrays directly from the text. The main contribution is a construction algorithm that uses only O(n) bits of working memory, and the time complexity is O(n log n). Our construction algorithm is also time and space efficient for texts with large alphabets such as Chinese or Japanese. Precisely, when the alphabet size is |∑|, the working space is O(n log |∑|) bits, and the time complexity remains O(n log n), which is independent of |∑|. © Springer 2007.</description.abstract> <language>eng</language> <publisher>Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm</publisher> <relation.ispartof>Algorithmica (New York)</relation.ispartof> <subject>Compression</subject> <subject>Construcion</subject> <subject>Pattern mathching</subject> <subject>Text indexing</subject> <title>A space and time efficient algorithm for constructing compressed suffix arrays</title> <type>Article</type> <identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=48:1&spage=23&epage=36&date=2007&atitle=A+Space+and+Time+Efficient+Algorithm+for+Constructing+Compressed+Suffix+Arrays+</identifier.openurl> <description.nature>Link_to_subscribed_fulltext</description.nature> <identifier.doi>10.1007/s00453-006-1228-8</identifier.doi> <identifier.scopus>eid_2-s2.0-34547375123</identifier.scopus> <identifier.hkuros>128171</identifier.hkuros> <relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-34547375123&selection=ref&src=s&origin=recordpage</relation.references> <identifier.volume>48</identifier.volume> <identifier.issue>1</identifier.issue> <identifier.spage>23</identifier.spage> <identifier.epage>36</identifier.epage> <identifier.isi>WOS:000246152800002</identifier.isi> <publisher.place>United States</publisher.place> <identifier.citeulike>4736346</identifier.citeulike> </item>

Author Affiliations

- Kyushu University
- The University of Hong Kong
- National University of Singapore