XBWT tricks

Giovanni Manzini

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

Abstract

The eXtended Burrows-Wheeler Transform (XBWT) is a data transformation introduced in [Ferragina et al., FOCS 2005] to compactly represent a labeled tree and simultaneously support navigation and path-search operations over its label structure. A natural application of the XBWT is to store a dictionary of strings. A recent extensive experimental study [Martínez-Prieto et al., Information Systems, 2016] shows that, among the available string dictionary implementations, the XBWT is attractive because of its good tradeoff between small space usage, speed, and support for substring searches. In this paper we further investigate the use of the XBWT for storing a string dictionary. Our first contribution is to show how to add suffix links (aka failure links) to a XBWT string dictionary. For a XBWT dictionary with n internal nodes our suffix links can be traversed in constant time and only take 2n + o(n) bits of space. Our second contribution are practical construction algorithms for the XBWT, including the additional data structure supporting the traversal of suffix links. Our algorithms build on the many well engineered algorithms for Suffix Array and BWT construction and offer different tradeoffs between running time and working space.

Lingua originaleInglese
Titolo della pubblicazione ospiteString Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings
EditorShunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
EditoreSpringer Verlag
Pagine80-92
Numero di pagine13
ISBN (stampa)9783319460482
DOI
Stato di pubblicazionePubblicato - 2016
Pubblicato esternamente
Evento23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 - Beppu, Japan
Durata: 18 ott 201620 ott 2016

Serie di pubblicazioni

NomeLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9954 LNCS
ISSN (stampa)0302-9743
ISSN (elettronico)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016
Paese/TerritorioJapan
CittàBeppu
Periodo18/10/1620/10/16

Fingerprint

Entra nei temi di ricerca di 'XBWT tricks'. Insieme formano una fingerprint unica.

Cita questo