Curtin University Homepage
  • Library
  • Help
    • Admin

    espace - Curtin’s institutional repository

    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item

    A taxonomy of suffix array construction algorithms

    Access Status
    Fulltext not available
    Authors
    Puglisi, Simon
    Smyth, William
    Turpin, A.
    Date
    2007
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Puglisi, Simon and Smyth, William and Turpin, Andrew. 2007. A taxonomy of suffix array construction algorithms. ACM Computing Surveys. 39 (2): pp. 1-31.
    Source Title
    ACM Computing Surveys
    Additional URLs
    http://doi.acm.org/10.1145/1242471.1242472
    ISSN
    03600300
    Faculty
    Curtin Business School
    Digital Ecosystems and Business Intelligence (DEBI) Institute
    Remarks

    ACM Copyright notice: Copyright © 2007 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or permissions@acm.org

    URI
    http://hdl.handle.net/20.500.11937/16863
    Collection
    • Curtin Research Publications
    Abstract

    In 1990, Manber and Myers proposed suffix arrays as a space-saving alternative to suffix trees and described the first algorithms for suffix array construction and use. Since that time, and especially in the last few years, suffix array construction algorithms have proliferated in bewildering abundance. This survey paper attempts to provide simple high-level descriptions of these numerous algorithms that highlight both their distinctive features and their commonalities, while avoiding as much as possible the complexities of implementation details. New hybrid algorithms are also described. We provide comparisons of the algorithms' worst-case time complexity and use of additional space, together with results of recent experimental test runs on many of their implementations.

    Related items

    Showing items related by title, author, creator and subject.

    • Suffix arrays: what are they good for?
      Puglisi, Simon; Smyth, Bill; Turpin, A. (2006)
      Recently the theoretical community has displayed a flurry of interest in suffix arrays, and compressed suffix arrays. New, asymptotically optimal algorithms for construction, search, and compression of suffix arrays have ...
    • Lempel-Ziv factorization using less time & space
      Chen, G.; Puglisi, Simon; Smyth, B. (2008)
      For 30 years the Lempel-Ziv factorization LZ x of a string x = x[1..n] has been a fundamental data structure of string processing, especially valuable for string compression and for computing all the repetitions (runs) ...
    • New suffix array algorithms - linear but not fast?
      Antonitio, A.; Ryan, P.; Smyth, Bill; Turpin, A.; Yu, X. (2004)
      In 2003 three (-)(n)-time algorithms were proposed for the construction of a suffix array of a string x = x[1..n] on an indexed alphabet, all of them inspired by the methodology of Farach's (-)(n)- time suffix tree ...
    Advanced search

    Browse

    Communities & CollectionsIssue DateAuthorTitleSubjectDocument TypeThis CollectionIssue DateAuthorTitleSubjectDocument Type

    My Account

    Admin

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Follow Curtin

    • 
    • 
    • 
    • 
    • 

    CRICOS Provider Code: 00301JABN: 99 143 842 569TEQSA: PRV12158

    Copyright | Disclaimer | Privacy statement | Accessibility

    Curtin would like to pay respect to the Aboriginal and Torres Strait Islander members of our community by acknowledging the traditional owners of the land on which the Perth campus is located, the Whadjuk people of the Nyungar Nation; and on our Kalgoorlie campus, the Wongutha people of the North-Eastern Goldfields.