Fast and Compact Regular Expression Matching
| Autor: | Martin Farach-Colton, Philip Bille |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
FOS: Computer and information sciences
Matching (statistics) General Computer Science String (computer science) F.2.2 F.2.0 F.1.1 Subsequence indexing String searching algorithm Approximate string matching Approximate regular expression matching: String edit distance Theoretical Computer Science Four russian technique Computer Science - Data Structures and Algorithms Subsequence 3-dimensional matching Regular expression matching Edit distance Data Structures and Algorithms (cs.DS) Regular expression Algorithm Computer Science(all) Mathematics |
| DOI: | 10.48550/arxiv.cs/0509069 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|