A Text Transformation Scheme for Degenerate Strings

Jacqueline W. Daykin, Bruce Watson

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)


The Burrows-Wheeler Transformation computes a permutation of a string of letters over an alphabet, and is well-suited to compression-related applications due to its invertability and data clustering properties. For space eciency the input to the transform can be preprocessed into Lyndon factors. We consider scenarios with uncertainty regarding the data: a position in an indeterminate or degenerate string is a set of letters. We first define Indeterminate Lyndon Words and establish their associated unique string factorization; we then introduce the novel Degenerate Burrows-Wheeler Transformation which may apply the indeterminate Lyndon factorization. A core computation in Burrows-Wheeler type transforms is the linear sorting of all conjugates of the input string - we achieve this in the degenerate case by applying lex-extension ordering. Indeterminate Lyndon factorization, and the degenerate transform and its inverse, can all be computed in linear time and space with respect to total input size of degenerate strings.
Iaith wreiddiolSaesneg
TeitlProceedings of the 2nd International Conference on Algorithms for Big Data
Is-deitlPalermo, Italy, April 07-09, 2014.
GolygyddionCostas S. Iliopoulos, Alessio Langiu
CyhoeddwrCEUR Workshop Proceedings
Nifer y tudalennau7
StatwsCyhoeddwyd - 16 Ebr 2014
Cyhoeddwyd yn allanolIe

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'A Text Transformation Scheme for Degenerate Strings'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn