License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.423
URN: urn:nbn:de:0030-drops-33558
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3355/
Go to the corresponding LIPIcs Volume Portal

Ben-Kiki, Oren ; Bille, Philip ; Breslauer, Dany ; Gasieniec, Leszek ; Grossi, Roberto ; Weimann, Oren

Optimal Packed String Matching

pdf-format:
37.pdf (0.5 MB)

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 =		{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
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI