Full Compressed Affix Tree Representations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2017

Full Compressed Affix Tree Representations

Résumé

The Suffix Tree, a crucial and versatile data structure for string analysis of large texts, is often used in pattern matching and in bioinformatics applications. The Affix Tree generalizes the Suffix Tree in that it supports full tree functionalities in both search directions. The bottleneck of Affix Trees is their space requirement for storing the data structure. Here, we discuss existing representations and classify them into two categories: Synchronous and Asynchronous. We design Compressed Affix Tree indexes in both categories and explored how to support all tree operations bidirectionally. This work compares alternative approaches for compress the Affix Tree, measuring their space and time trade-offs for different operations. Moreover, to our knowledge, this is the first work that compares all Compressed Affix Tree implementations, i.e., four different approaches: the Affix Array, the Bidirectional Wavelet Index, and our two new structures, measures their space and time trade-offs, offering a practical benchmark for this structure.
Fichier principal
Vignette du fichier
Canovas-Rivals-dcc-2017.pdf (248.01 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-02093302 , version 1 (08-04-2019)

Identifiants

Citer

Rodrigo Cánovas, Eric Rivals. Full Compressed Affix Tree Representations. DCC: Data Compression Conference, IEEE, Apr 2017, Snowbird, UT, United States. pp.102-111, ⟨10.1109/DCC.2017.39⟩. ⟨lirmm-02093302⟩
99 Consultations
209 Téléchargements

Altmetric

Partager

More