arXiv Open Access 2009

Wee LCP

Johannes Fischer

Lihat Sumber

Abstrak

We prove that longest common prefix (LCP) information can be stored in much less space than previously known. More precisely, we show that in the presence of the text and the suffix array, o(n) additional bits are sufficient to answer LCP-queries asymptotically in the same time that is needed to retrieve an entry from the suffix array. This yields the smallest compressed suffix tree with sub-logarithmic navigation time.

Topik & Kata Kunci

cs.DS

Penulis (1)

Johannes Fischer

Format Sitasi

APA MLA BibTeX

Fischer, J. (2009). Wee LCP. https://arxiv.org/abs/0910.3123

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2009
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓