Data-Compression.org

data compression link collection

Opportunistic data structures with applications

Two papers in which it is show how to combine the BWT with the suffix array
data structure, in order to build a sort of compressed suffix array.
In the first paper it is proven that
the space occupancy of the compressed suffix array can be bounded in
terms of the entropy of the input string. In the second paper it is
proposed and tested a practical implementation of this data structure.

The first paper will appear in the Proc. of 41st IEEE Symposium on
Foundations of Computer Science; the second one in the Proc. of the 12th
SIAM-ACM Symposium on Discrete Algorithms.

http://www.mfn.unipmn.it/~manzini/papers/focs00.html

* * * * *

Posted in September 23rd, 2000

No User Commented In " Opportunistic data structures with applications "

Subscribes to this post Comment RSS or TrackBack URL

Leave Your Reply Below

 Username

 Email Address

 Website

Sticky note: Please double check your comments before submit Please Note: The comment moderation maybe active so there is no need to resubmit your comment