IMPROVED DYNAMIC DICTIONARY MATCHING

被引:57
作者
AMIR, A
FARACH, M
IDURY, RM
LAPOUTRE, JA
SCHAFFER, AA
机构
[1] RUTGERS STATE UNIV,DIMACS,CTR DISCRETE MATH & THEORET COMP SCI,PISCATAWAY,NJ 08855
[2] RICE UNIV,HOUSTON,TX 77251
[3] PRINCETON UNIV,PRINCETON,NJ 08544
关键词
D O I
10.1006/inco.1995.1090
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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. (C) 1995 Academic Press. Inc.
引用
收藏
页码:258 / 282
页数:25
相关论文
共 31 条
[1]   EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH [J].
AHO, AV ;
CORASICK, MJ .
COMMUNICATIONS OF THE ACM, 1975, 18 (06) :333-340
[2]   DYNAMIC DICTIONARY MATCHING [J].
AMIR, A ;
FARACH, M ;
GALIL, Z ;
GIANCARLO, R ;
PARK, K .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 49 (02) :208-222
[3]   2-DIMENSIONAL DICTIONARY MATCHING [J].
AMIR, A ;
FARACH, M .
INFORMATION PROCESSING LETTERS, 1992, 44 (05) :233-239
[4]  
AMIR A, 1992, 24TH P ACM S THEOR C, P59
[5]   FAST 2-DIMENSIONAL PATTERN-MATCHING [J].
BAEZAYATES, R ;
REGNIER, M .
INFORMATION PROCESSING LETTERS, 1993, 45 (01) :51-57
[7]  
Bird R. S., 1977, Information Processing Letters, V6, P168, DOI 10.1016/0020-0190(77)90017-5
[8]   FAST STRING SEARCHING ALGORITHM [J].
BOYER, RS ;
MOORE, JS .
COMMUNICATIONS OF THE ACM, 1977, 20 (10) :762-772
[9]   MORE EFFICIENT BOTTOM-UP MULTIPATTERN MATCHING IN TREES [J].
CAI, J ;
PAIGE, R ;
TARJAN, R .
THEORETICAL COMPUTER SCIENCE, 1992, 106 (01) :21-60
[10]  
CHASE D, 1987, 14TH P ANN ACM S PRI, P168