Pizza&Chili Corpus
Compressed Indexes and their Testbeds

The Italian mirror | The Chilean mirror

Locally Compressed Suffix Array

Description

The Locally Compressed Suffix Array is a compressed representation of the suffix array.

The size of the index built on a text $ T$ of length $ n$ over an alphabet of size $ \sigma$ requires $ O(H_k\log(1/H_k)n\log n+n)$ bits of space in addition to $ T$ , for any $ k \le \alpha \log_\sigma n$ and any constant $ 0<\alpha<1$ .

This index can count the occurrences of a pattern of length $ m$ in time $ O(m\log n)$ and locate its $ occ$ occurrences in time $ O(occ+\log n)$ .

Implementation

R. González

Build_options

See README file.

Paper

Rodrigo González and Gonzalo Navarro. Compressed Text Indexes with Fast Locate. Proc. CPM'07, pages 216-227. LNCS 4580.

Downloads


Send Mail to Us | © P. Ferragina and G. Navarro, Last update: September, 2005.