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 条
  • [21] A unified framework for string similarity search with edit-distance constraint
    Minghe Yu
    Jin Wang
    Guoliang Li
    Yong Zhang
    Dong Deng
    Jianhua Feng
    The VLDB Journal, 2017, 26 : 249 - 274
  • [22] minIL: A Simple and Small Index for String Similarity Search with Edit Distance
    Yang, Zhong
    Zheng, Bolong
    Wang, Xianzhi
    Li, Guohui
    Zhou, Xiaofang
    2022 IEEE 38TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2022), 2022, : 565 - 577
  • [23] Computing All-vs-All MEMs in Run-Length-Encoded Collections of HiFi Reads
    Diaz-Dominguez, Diego
    Puglisi, Simon J.
    Salmela, Leena
    STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2022, 2022, 13617 : 198 - 213
  • [24] MinJoin++: a fast algorithm for string similarity joins under edit distance
    Nikolai Karpov
    Haoyu Zhang
    Qin Zhang
    The VLDB Journal, 2024, 33 : 281 - 299
  • [25] Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton
    Calvo-Zaragoza, Jorgc
    Oncina, Jose
    de la Higucra, Colin
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2017, 28 (05) : 603 - 621
  • [26] MinJoin plus plus : a fast algorithm for string similarity joins under edit distance
    Karpov, Nikolai
    Zhang, Haoyu
    Zhang, Qin
    VLDB JOURNAL, 2024, 33 (02) : 281 - 299
  • [27] AN IMPROVED ALGORITHM FOR COMPUTING THE EDIT DISTANCE OF RUN-LENGTH CODED STRINGS
    BUNKE, H
    CSIRIK, J
    INFORMATION PROCESSING LETTERS, 1995, 54 (02) : 93 - 96
  • [28] EFFICIENT STRING EDIT SIMILARITY JOIN ALGORITHM
    Gouda, Karam
    Rashad, Metwally
    COMPUTING AND INFORMATICS, 2017, 36 (03) : 683 - 704
  • [29] Efficiently Supporting Edit Distance Based String Similarity Search Using B+-Trees
    Lu, Wei
    Du, Xiaoyong
    Hadjieleftheriou, Marios
    Ooi, Beng Chin
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2014, 26 (12) : 2983 - 2996
  • [30] Binary jumbled string matching for highly run-length compressible texts
    Badkobeh, Golnaz
    Fici, Gabriele
    Kroon, Steve
    Liptak, Zsuzsanna
    INFORMATION PROCESSING LETTERS, 2013, 113 (17) : 604 - 608
12345