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 条
  • [1] Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
    Liu, J. J.
    Wang, Y. L.
    Lee, R. C. T.
    JOURNAL OF COMPLEXITY, 2008, 24 (02) : 173 - 184
  • [2] Edit distance of run-length encoded strings
    Arbell, O
    Landau, GM
    Mitchell, JSB
    INFORMATION PROCESSING LETTERS, 2002, 83 (06) : 307 - 314
  • [3] Constrained Longest Common Subsequences with Run-Length-Encoded Strings
    Liu, Jia-Jie
    Wang, Yue-Li
    Chiu, Yu-Shan
    COMPUTER JOURNAL, 2015, 58 (05) : 1074 - 1084
  • [4] A New String Edit Distance and Applications
    Petty, Taylor
    Hannig, Jan
    Huszar, Tunde, I
    Iyer, Hari
    ALGORITHMS, 2022, 15 (07)
  • [5] Parallel comparison of run-length-encoded strings on a linear systolic array
    Bogliolo, Alessandro
    Freschi, Valerio
    INFORMATION SCIENCES, 2007, 177 (01) : 231 - 238
  • [6] Efficient retrieval of approximate palindromes in a run-length encoded string
    Chen, Kuan-Yu
    Hsu, Ping-Hui
    Chao, Kun-Mao
    THEORETICAL COMPUTER SCIENCE, 2012, 432 : 28 - 37
  • [7] Classes of cost functions for string edit distance
    Rice, SV
    Bunke, H
    Nartker, TA
    ALGORITHMICA, 1997, 18 (02) : 271 - 280
  • [8] Classes of cost functions for string edit distance
    S. V. Rice
    H. Bunke
    T. A. Nartker
    Algorithmica, 1997, 18 : 271 - 280
  • [9] The String Edit Distance Matching Problem With Moves
    Cormode, Graham
    Muthukrishnan, S.
    ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (01)
  • [10] Template-based rendering of run-length-encoded volumes
    Lee, CH
    Koo, YM
    Shin, YG
    JOURNAL OF VISUALIZATION AND COMPUTER ANIMATION, 1998, 9 (03): : 145 - 161
12345