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 条
[11]   A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings [J].
Chen, Kuan-Yu ;
Chao, Kun-Mao .
ALGORITHMICA, 2013, 65 (02) :354-370
[12]   A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings [J].
Kuan-Yu Chen ;
Kun-Mao Chao .
Algorithmica, 2013, 65 :354-370
[13]   Computing the Expected Edit Distance from a String to a PFA [J].
Calvo-Zaragoza, Jorge ;
de la Higuera, Colin ;
Oncina, Jose .
Implementation and Application of Automata, 2016, 9705 :39-50
[14]   An algorithm for string edit distance allowing substring reversals [J].
Arslan, Abdullah N. .
BIBE 2006: SIXTH IEEE SYMPOSIUM ON BIOINFORMATICS AND BIOENGINEERING, PROCEEDINGS, 2006, :220-+
[15]   A fast algorithm for finding the positions of all squares in a run-length encoded string [J].
Liu, J. J. ;
Huang, G. S. ;
Wang, Y. L. .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) :3942-3948
[16]   A unified framework for string similarity search with edit-distance constraint [J].
Yu, Minghe ;
Wang, Jin ;
Li, Guoliang ;
Zhang, Yong ;
Deng, Dong ;
Feng, Jianhua .
VLDB JOURNAL, 2017, 26 (02) :249-274
[17]   Bounded Occurrence Edit Distance: A New Metric for String Similarity Joins with Edit Distance Constraints [J].
Komatsu, Tomoki ;
Okuta, Ryosuke ;
Narisawa, Kazuyuki ;
Shinohara, Ayumi .
SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2014, 8327 :363-374
[18]   Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism [J].
Freschi, V ;
Bogliolo, A .
INFORMATION PROCESSING LETTERS, 2004, 90 (04) :167-173
[19]   A Partition-Based Method for String Similarity Joins with Edit-Distance Constraints [J].
Li, Guoliang ;
Deng, Dong ;
Feng, Jianhua .
ACM TRANSACTIONS ON DATABASE SYSTEMS, 2013, 38 (02)
[20]   Computing the Shortest String and the Edit-Distance for Parsing Expression Languages [J].
Cheon, Hyunjoon ;
Han, Yo-Sub .
DEVELOPMENTS IN LANGUAGE THEORY, DLT 2020, 2020, 12086 :43-54
12345