Compressed Indexes and their Testbeds

## LZ-Index |

4 n H_k(T) + o(n log s) bits of space for a text T[1,n] over
an alphabet of size s. Its worst case locate time is O(m^3 log s +
(m + occ) log n), where m is the pattern length and occ
the number of occurrences. In practice, its time to locate occurrences is
very competitive.
Gonzalo Navarro and Diego Arroyuelo, University of Chile (Chile). email us for any problem, bug, or comment:
({
Gonzalo Navarro.
- LZ-Index: The original LZ-index data structure.
- LZ-index-1: Reduced version of LZ-index, requiring
*3 n H_k*(*T*)*+ o*(*n*log s) bits of storage. [Last Update: May 29, 2007]. - LZ-index-7: Another reduced version of LZ-index, also requiring
*3 n H_k*(*T*)*+ o*(*n*log s) bits of storage. [Last Update: May 29, 2007]. - LZ-index-4: Reduced version of LZ-index, requiring (
*2+*e)*n H_k*(*T*)*+ o*(*n*log s). [Last Update: May 29, 2007].
The reduced versions are based on similar ideas to that presented in the paper: D. Arroyuelo, G. Navarro, and K. Sadakane. Soon we will make available a technical report explaining the details of these implementations. |

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