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. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1006/inco.1995.1090 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
improved dynamic dictionary matching,associative memory,nearest neighbor,pattern recognition,clustering,computational geometry,metric space | k-nearest neighbors algorithm,Content-addressable memory,K-SVD,Pattern recognition,Computer science,Computational geometry,Nearest neighbor graph,Artificial intelligence,Cluster analysis,Nearest neighbor search | Journal |
Volume | Issue | ISSN |
119 | 2 | Information and Computation |
ISBN | Citations | PageRank |
0-89871-313-7 | 45 | 2.65 |
References | Authors | |
19 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amihood Amir | 1 | 1985 | 191.89 |
Martin Farach | 2 | 805 | 117.05 |
Ramana M. Idurys | 3 | 204 | 24.03 |
Johannes A. La Poutré | 4 | 308 | 24.78 |
Alejandro A. Schäffer | 5 | 827 | 136.66 |