Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Time and Space Efficient Search for Small Alphabets with Suffix Arrays
verfasst von : Jeong Seop Sim
Erschienen in: Fuzzy Systems and Knowledge Discovery
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
To search a pattern
P
in a text, index data structures such as suffix trees and suffix arrays are widely used. It is known that searching with suffix trees is faster than with suffix arrays in the aspect of time complexity. But recently, a few linear-time search algorithms for constant-size alphabet in suffix arrays have been suggested. One of such algorithms proposed by Sim et al. uses Burrows-Wheeler transform and takes
O
(|
P
|log|Σ|) time. But this algorithm needs too much space compared to Abouelhoda et al.’s algorithm to search a pattern.
In this paper we present an improved version for Sim et al.’s algorithm. It needs only 2
n
bytes at most if a given alphabet is sufficiently small.