Edit distance for a run-length-encoded string and an uncompressed string

被引：9
作者：
Liu, J. J.
Huang, G. S.
Wang, Y. L.
Lee, R. C. T.
机构：
[1] Natl Taiwan Univ Sci & Technol, Dept Informat Management, Taipei, Taiwan
[2] Natl Chi Nan Univ, Dept Comp Sci & Informat Engn, Nantou, Taiwan
来源：
INFORMATION PROCESSING LETTERS | 2007年 / 105卷 / 01期
关键词：
edit distance; run-length-encoding; string compression; algorithms;
D O I：
10.1016/j.ipl.2007.07.006
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We propose a new algorithm for computing the edit distance of an uncompressed string against a run-length-encoded string. For an uncompressed string of length n and a compressed string with M runs, the algorithm computes their edit distance in time O(Mn). This result directly implies an O(min{mN, Mn}) time algorithm for strings of lengths m and n with M and N runs, respectively. It improves the previous best known time bound O(mN + Mn). (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：12 / 16
页数：5
相关论文
共 50 条
[31]   String Matching with Variable Length Gaps [J].
Bille, Philip ;
Gortz, Inge Li ;
Vildhoj, Hjalte Wedel ;
Wind, David Kofoed .
STRING PROCESSING AND INFORMATION RETRIEVAL, 2010, 6393 :385-394
[32]   String matching with variable length gaps [J].
Bille, Philip ;
Gortz, Inge Li ;
Vildhoj, Hjalte Wedel ;
Wind, David Kofoed .
THEORETICAL COMPUTER SCIENCE, 2012, 443 :25-34
[33]   Practical linear space algorithms for computing string-edit distances [J].
Chan, Tony Y. T. .
COMPUTATIONAL INTELLIGENCE AND BIOINFORMATICS, PT 3, PROCEEDINGS, 2006, 4115 :504-513
[34]   Approximate Matching for Run-Length Encoded Strings Is 3SUM-Hard [J].
Chen, Kuan-Yu ;
Hsu, Ping-Hui ;
Chao, Kun-Mao .
COMBINATORIAL PATTERN MATCHING, PROCEEDINGS, 2009, 5577 :168-179
[35]   Extending the Bag Distance for String Similarity Search [J].
Mergen S. .
SN Computer Science, 4 (2)
[36]   PSH: A Probabilistic Signature Hash Method with Hash Neighborhood Candidate Generation for Fast Edit-Distance String Comparison on Big Data [J].
Jupin, Joseph ;
Shi, Justin Y. ;
Dragut, Eduard C. .
2016 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA), 2016, :122-127
[37]   Distinct squares in run-length encoded strings [J].
Liu, J. J. .
THEORETICAL COMPUTER SCIENCE, 2010, 411 (49) :4235-4241
[38]   String correction using the Damerau-Levenshtein distance [J].
Chunchun Zhao ;
Sartaj Sahni .
BMC Bioinformatics, 20
[39]   Research on String Similarity Algorithm based on Levenshtein Distance [J].
Zhang, Shengnan ;
Hu, Yan ;
Bian, Guangrong .
2017 IEEE 2ND ADVANCED INFORMATION TECHNOLOGY, ELECTRONIC AND AUTOMATION CONTROL CONFERENCE (IAEAC), 2017, :2247-2251
[40]   String correction using the Damerau-Levenshtein distance [J].
Zhao, Chunchun ;
Sahni, Sartaj .
BMC BIOINFORMATICS, 2019, 20 (Suppl 11)
12345