Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bille, Philip; Gørtz, Inge Li; Skjoldjensen, Frederik Rye http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-73351
URL:

; ;

Deterministic Indexing for Packed Strings

pdf-format:


Abstract

Given a string S of length n, the classic string indexing problem is to preprocess S into a compact data structure that supports efficient subsequent pattern queries. In the deterministic variant the goal is to solve the string indexing problem without any randomization (at preprocessing time or query time). In the packed variant the strings are stored with several character in a single word, giving us the opportunity to read multiple characters simultaneously. Our main result is a new string index in the deterministic and packed setting. Given a packed string S of length n over an alphabet s, we show how to preprocess S in O(n) (deterministic) time and space O(n) such that given a packed pattern string of length m we can support queries in (deterministic) time O(m/a + log m + log log s), where a = w /log s is the number of characters packed in a word of size w = log n. Our query time is always at least as good as the previous best known bounds and whenever several characters are packed in a word, i.e., log s << w, the query times are faster.

BibTeX - Entry

@InProceedings{bille_et_al:LIPIcs:2017:7335,
  author =	{Philip Bille and Inge Li G\ortz and Frederik Rye Skjoldjensen},
  title =	{{Deterministic Indexing for Packed Strings}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{6:1--6:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{Juha K{\"a}rkk{\"a}inen, Jakub Radoszewski, and Wojciech Rytter},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7335},
  URN =		{urn:nbn:de:0030-drops-73351},
  doi =		{10.4230/LIPIcs.CPM.2017.6},
  annote =	{Keywords: suffix tree, suffix array, deterministic algorithm, word packing}
}

Keywords: suffix tree, suffix array, deterministic algorithm, word packing
Seminar: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue date: 2017
Date of publication: 2017


DROPS-Home | Fulltext Search | Imprint Published by LZI