Fast and compact regular expression matching

Philip Bille; Martin Farach-Colton

Fast and compact regular expression matching

Philip Bille, Martin Farach-Colton

Rutgers University

Research output: Journal Article or Conference Article in Journal › Journal article › Research › 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
Journal	Theoretical Computer Science
Volume	409
Issue number	3
Pages (from-to)	486-496
Number of pages	11
ISSN	0304-3975
Publication status	Published - 28 Dec 2008

Keywords

String Matching
Regular Expression Matching
Approximate Regular Expression Matching
String Edit Distance
Subsequence Indexing

Cite this

@article{0f363a90e62a11dda259000ea68e967b,

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 = "String Matching, Regular Expression Matching, Approximate Regular Expression Matching, String Edit Distance, Subsequence Indexing, String Matching, Regular Expression Matching, Approximate Regular Expression Matching, String Edit Distance, Subsequence Indexing",

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

note = "Paper id:: 10.1016/j.tcs.2008.08.042",

year = "2008",

month = dec,

day = "28",

language = "English",

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

N1 - Paper id:: 10.1016/j.tcs.2008.08.042

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 - String Matching

KW - Regular Expression Matching

KW - Approximate Regular Expression Matching

KW - String Edit Distance

KW - Subsequence Indexing

KW - String Matching

KW - Regular Expression Matching

KW - Approximate Regular Expression Matching

KW - String Edit Distance

KW - Subsequence Indexing

M3 - Journal article

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

Fingerprint

Cite this