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
    Kuan-Yu Chen
    Kun-Mao Chao
    Algorithmica, 2013, 65 : 354 - 370
  • [12] A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings
    Chen, Kuan-Yu
    Chao, Kun-Mao
    ALGORITHMICA, 2013, 65 (02) : 354 - 370
  • [13] Computing the Expected Edit Distance from a String to a PFA
    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
    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
    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
    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
    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
    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
    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
    Cheon, Hyunjoon
    Han, Yo-Sub
    DEVELOPMENTS IN LANGUAGE THEORY, DLT 2020, 2020, 12086 : 43 - 54
12345