Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection

Details Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection

2011-10-15

arxiv.org/abs/1110.3381v1

Computer Science

Data Structures and Algorithms

Scientific paper

Consider an input text string T[1,N] drawn from an unbounded alphabet. We study partial computation in suffix-based problems for Data Compression and Text Indexing such as (I) retrieve any segment of K<=N consecutive symbols from the Burrows-Wheeler transform of T, and (II) retrieve any chunk of K<=N consecutive entries of the Suffix Array or the Suffix Tree. Prior literature would take O(N log N) comparisons (and time) to solve these problems by solving the total problem of building the entire Burrows-Wheeler transform or Text Index for T, and performing a post-processing to single out the wanted portion. We introduce a novel adaptive approach to partial computational problems above, and solve both the partial problems in O(K log K + N) comparisons and time, improving the best known running times of O(N log N) for K=o(N). These partial-computation problems are intimately related since they share a common bottleneck: the suffix multi-selection problem, which is to output the suffixes of rank r_1,r_2,...,r_K under the lexicographic order, where r_1

Affiliated with

Also associated with

No associations

Rating

Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-687413