Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Ben-Kiki, Oren; Bille, Philip; Breslauer, Dany; Gasieniec, Leszek; Grossi, Roberto; Weimann, Oren http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-33558
URL:

; ; ; ; ;

Optimal Packed String Matching

pdf-format:


Abstract

In the packed string matching problem, each machine word accomodates alpha characters, thus an n-character text occupies n/alpha memory words. We extend the Crochemore-Perrin constant-space O(n)-time string matching algorithm to run in optimal O(n/alpha) time and even in real-time, achieving a factor alpha speedup over traditional algorithms that examine each character individually. Our solution can be efficiently implemented, unlike prior theoretical packed string matching work. We adapt the standard RAM model and only use its AC0 instructions (i.e. no multiplication) plus two specialized AC0 packed string instructions. The main string-matching instruction is available in commodity processors (i.e. Intel's SSE4.2 and AVX Advanced String Operations); the other maximal-suffix instruction is only required during pattern preprocessing. In the absence of these two specialized instructions, we propose theoretically-efficient emulation using integer multiplication (not AC0) and table lookup.

BibTeX - Entry

@InProceedings{benkiki_et_al:LIPIcs:2011:3355,
  author =	{Oren Ben-Kiki and Philip Bille and Dany Breslauer and Leszek Gasieniec and Roberto Grossi and Oren Weimann},
  title =	{{Optimal Packed String Matching }},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{423--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3355},
  URN =		{urn:nbn:de:0030-drops-33558},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.423},
  annote =	{Keywords: String matching, bit parallelism, real time, space efficiency}
}

Keywords: String matching, bit parallelism, real time, space efficiency
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue date: 2011
Date of publication: 2011


DROPS-Home | Fulltext Search | Imprint Published by LZI