Fast Algorithms for Parsing Sequences of Parentheses with Few Errors

被引：9
作者：
Backurs, Arturs [1 ]
Onak, Krzysztof [2 ]
机构：
[1] MIT, Cambridge, MA 02139 USA
[2] IBM Res, Yorktown Hts, NY USA
来源：
PODS'16: PROCEEDINGS OF THE 35TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS | 2016年
关键词：
Dyck language; edit distance; parsing;
D O I：
10.1145/2902251.2902304
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We consider the problem of fixing sequences of unbalanced parentheses. A classic algorithm based on dynamic programming computes the optimum sequence of edits required to solve the problem in cubic time. We show the first algorithm that runs in linear time when the number of necessary edits is small. More precisely, our algorithm runs in O( n)+ d(O(1)) time, where n is the length of the sequence to be fixed and d is the minimum number of edits. The problem of fixing parentheses sequences is related to the task of repairing semi-structured documents such as XML and JSON.
引用
收藏
页码：477 / 488
页数：12
相关论文
共 15 条
[1]  
Abboud A., 2015, FOCS
[2]  
Aho A. V., 1972, SIAM Journal on Computing, V1, P305, DOI 10.1137/0201022
[3]   Color Fractal Descriptors for Adaxial Epidermis Texture Classification [J].
Backes, Andre R. ;
de Mesquita Sa Junior, Jarbas Joaci ;
Kolb, Rosana Marta .
PROGRESS IN PATTERN RECOGNITION, IMAGE ANALYSIS, COMPUTER VISION, AND APPLICATIONS, CIARP 2015, 2015, 9423 :51-58
[4]   All pairs shortest distances for graphs with small integer length edges [J].
Galil, Z ;
Margalit, O .
INFORMATION AND COMPUTATION, 1997, 134 (02) :103-139
[5]   On Repairing Structural Problems In Semi-structured Data [J].
Korn, Flip ;
Saha, Barna ;
Srivastava, Divesh ;
Ying, Shanshan .
PROCEEDINGS OF THE VLDB ENDOWMENT, 2013, 6 (09) :601-612
[6]   Incremental string comparison [J].
Landau, GM ;
Myers, EW ;
Schmidt, JP .
SIAM JOURNAL ON COMPUTING, 1998, 27 (02) :557-582
[7]  
Le Gall F., 2014, P 39 INT S SYMB ALG, P296, DOI [10.1145/2608628.2608664, DOI 10.1145/2608628.2608664]
[8]   APPROXIMATELY MATCHING CONTEXT-FREE LANGUAGES [J].
MYERS, G .
INFORMATION PROCESSING LETTERS, 1995, 54 (02) :85-92
[9]   Language Edit Distance & Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms & Connection to Fundamental Graph Problems [J].
Saha, Barna .
2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, :118-135
[10]   The Dyck Language Edit Distance Problem in Near-linear Time [J].
Saha, Barna .
2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, :611-620
12