Improved dynamic dictionary matching

Amihood Amir; Martin Farach; Ramana M. Idury; Johannes A. Lapoutre; Alejandro A. Schaffer

doi:10.1006/inco.1995.1090

Improved dynamic dictionary matching

Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. Lapoutre, Alejandro A. Schaffer

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

Abstract

In the dynamic dictionary matching problem, a dictionary D contains a set of patterns that can change over time by insertion and deletion of individual patterns. The user also presents text strings and asks for all occurrences of any patterns in the text. The two main contributions of this paper are: (1) a faster algorithm for dynamic string dictionary matching with bounded alphabets, and (2) a dynamic dictionary matching algorithm for two-dimensional texts and patterns. The first contribution is based on an algorithm that solves the general problem of maintaining a sequence of well-balanced parentheses under the operations insert, delete, and find nearest enclosing parenthesis pair. The main new idea behind the second contribution is a novel method to efficiently manipulate failure links for two-dimensional patterns.

Original language	English (US)
Pages (from-to)	258-282
Number of pages	25
Journal	Information and Computation
Volume	119
Issue number	2
DOIs	https://doi.org/10.1006/inco.1995.1090
State	Published - Jun 1995

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1006/inco.1995.1090

Cite this

@article{5500a3e31d83485588286a17fd225615,

title = "Improved dynamic dictionary matching",

abstract = "In the dynamic dictionary matching problem, a dictionary D contains a set of patterns that can change over time by insertion and deletion of individual patterns. The user also presents text strings and asks for all occurrences of any patterns in the text. The two main contributions of this paper are: (1) a faster algorithm for dynamic string dictionary matching with bounded alphabets, and (2) a dynamic dictionary matching algorithm for two-dimensional texts and patterns. The first contribution is based on an algorithm that solves the general problem of maintaining a sequence of well-balanced parentheses under the operations insert, delete, and find nearest enclosing parenthesis pair. The main new idea behind the second contribution is a novel method to efficiently manipulate failure links for two-dimensional patterns.",

author = "Amihood Amir and Martin Farach and Idury, {Ramana M.} and Lapoutre, {Johannes A.} and Schaffer, {Alejandro A.}",

year = "1995",

month = jun,

doi = "10.1006/inco.1995.1090",

language = "English (US)",

volume = "119",

pages = "258--282",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - Improved dynamic dictionary matching

AU - Amir, Amihood

AU - Farach, Martin

AU - Idury, Ramana M.

AU - Lapoutre, Johannes A.

AU - Schaffer, Alejandro A.

PY - 1995/6

Y1 - 1995/6

N2 - In the dynamic dictionary matching problem, a dictionary D contains a set of patterns that can change over time by insertion and deletion of individual patterns. The user also presents text strings and asks for all occurrences of any patterns in the text. The two main contributions of this paper are: (1) a faster algorithm for dynamic string dictionary matching with bounded alphabets, and (2) a dynamic dictionary matching algorithm for two-dimensional texts and patterns. The first contribution is based on an algorithm that solves the general problem of maintaining a sequence of well-balanced parentheses under the operations insert, delete, and find nearest enclosing parenthesis pair. The main new idea behind the second contribution is a novel method to efficiently manipulate failure links for two-dimensional patterns.

AB - In the dynamic dictionary matching problem, a dictionary D contains a set of patterns that can change over time by insertion and deletion of individual patterns. The user also presents text strings and asks for all occurrences of any patterns in the text. The two main contributions of this paper are: (1) a faster algorithm for dynamic string dictionary matching with bounded alphabets, and (2) a dynamic dictionary matching algorithm for two-dimensional texts and patterns. The first contribution is based on an algorithm that solves the general problem of maintaining a sequence of well-balanced parentheses under the operations insert, delete, and find nearest enclosing parenthesis pair. The main new idea behind the second contribution is a novel method to efficiently manipulate failure links for two-dimensional patterns.

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

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

U2 - 10.1006/inco.1995.1090

DO - 10.1006/inco.1995.1090

M3 - Article

AN - SCOPUS:0347494025

SN - 0890-5401

VL - 119

SP - 258

EP - 282

JO - Information and Computation

JF - Information and Computation

IS - 2

ER -

Improved dynamic dictionary matching

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this