Fast and compact regular expression matching

Philip Bille; Martin Farach-Colton

doi:10.1016/j.tcs.2008.08.042

Fast and compact regular expression matching

Philip Bille, Martin Farach-Colton

Research output: Contribution to journal › Article › peer-review

Abstract

We study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word RAM model of computation that allows logarithmic-sized words to be manipulated in constant time. We show how to improve the space and/or remove a dependency on the alphabet size for each problem using either an improved tabulation technique of an existing algorithm or by combining known algorithms in a new way.

Original language	English (US)
Pages (from-to)	486-496
Number of pages	11
Journal	Theoretical Computer Science
Volume	409
Issue number	3
DOIs	https://doi.org/10.1016/j.tcs.2008.08.042
State	Published - Dec 28 2008

Keywords

Approximate regular expression matching: String edit distance
Four russian technique
Regular expression matching
Subsequence indexing

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2008.08.042

Cite this

@article{885eec1d7cfc4719ad137747e35357b6,

title = "Fast and compact regular expression matching",

abstract = "We study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word RAM model of computation that allows logarithmic-sized words to be manipulated in constant time. We show how to improve the space and/or remove a dependency on the alphabet size for each problem using either an improved tabulation technique of an existing algorithm or by combining known algorithms in a new way.",

keywords = "Approximate regular expression matching: String edit distance, Four russian technique, Regular expression matching, Subsequence indexing",

author = "Philip Bille and Martin Farach-Colton",

year = "2008",

month = dec,

day = "28",

doi = "10.1016/j.tcs.2008.08.042",

language = "English (US)",

volume = "409",

pages = "486--496",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Fast and compact regular expression matching

AU - Bille, Philip

AU - Farach-Colton, Martin

PY - 2008/12/28

Y1 - 2008/12/28

N2 - We study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word RAM model of computation that allows logarithmic-sized words to be manipulated in constant time. We show how to improve the space and/or remove a dependency on the alphabet size for each problem using either an improved tabulation technique of an existing algorithm or by combining known algorithms in a new way.

AB - We study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word RAM model of computation that allows logarithmic-sized words to be manipulated in constant time. We show how to improve the space and/or remove a dependency on the alphabet size for each problem using either an improved tabulation technique of an existing algorithm or by combining known algorithms in a new way.

KW - Approximate regular expression matching: String edit distance

KW - Four russian technique

KW - Regular expression matching

KW - Subsequence indexing

UR - http://www.scopus.com/inward/record.url?scp=55949108676&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=55949108676&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2008.08.042

DO - 10.1016/j.tcs.2008.08.042

M3 - Article

AN - SCOPUS:55949108676

SN - 0304-3975

VL - 409

SP - 486

EP - 496

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

Fast and compact regular expression matching

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this