Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform

Jacqueline Daykin, Richard Groult, Yannick Guesnet, Thierry Lecroq, Arnaud Lefebvre, Martine Léonard, Laurent Mouchard, Élise Prieur-Gaston, Bruce Watson

Allbwn ymchwil: Cyfraniad at gyfnodolynErthygladolygiad gan gymheiriaid

7 Dyfyniadau(SciVal)
121 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

A degenerate or indeterminate string on an alphabet Σ is a sequence of non-empty subsets of Σ. Given a degenerate string t of length n and its Burrows–Wheeler transform we present a new method for searching for a degenerate pattern of length m in t running in O(mn) time on a constant size alphabet Σ. Furthermore, it is a hybrid pattern matching technique that works on both regular and degenerate strings. A degenerate string is said to be conservative if its number of non-solid letters is upper-bounded by a fixed positive constant q; in this case we show that the search time complexity is O(qm2) for counting the number of occurrences andO(qm2+occ) for reporting the found occurrences where occ is the number of occurrences of the pattern in t. Experimental results show that our method performs well in practice
Iaith wreiddiolSaesneg
Tudalennau (o-i)82-87
Nifer y tudalennau6
CyfnodolynInformation Processing Letters
Cyfrol147
Dyddiad ar-lein cynnar15 Maw 2019
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - Gorff 2019

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn