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 条

[41] Comparison of AESA and LAESA search algorithms using string and tree-edit-distances [J].

Rico-Juan, JR ;

Micó, L .

PATTERN RECOGNITION LETTERS, 2003, 24 (9-10) :1417-1426

[42] Computational approaches to apply the String Edit Algorithm to create accurate visual scan paths [J].

Fraga, Ricardo Palma ;

Kang, Ziho .

JOURNAL OF EYE MOVEMENT RESEARCH, 2024, 17 (04)

[43] A novel string distance metric for ranking Persian respelling suggestions [J].

Kashefi, Omid ;

Sharifi, Mohsen ;

Minaie, Behrooz .

NATURAL LANGUAGE ENGINEERING, 2013, 19 (02) :259-284

[44] Parameterized searching with mismatches for run-length encoded strings [J].

Apostolico, Alberto ;

Erdos, Peter L. ;

Juettner, Alpar .

THEORETICAL COMPUTER SCIENCE, 2012, 454 :23-29

[45] Hardness of comparing two run-length encoded strings [J].

Chen, Kuan-Yu ;

Hsu, Ping-Hui ;

Chao, Kun-Mao .

JOURNAL OF COMPLEXITY, 2010, 26 (04) :364-374

[46] Identifying Approximate Palindromes in Run-Length Encoded Strings [J].

Chen, Kuan-Yu ;

Hsu, Ping-Hui ;

Chao, Kun-Mao .

ALGORITHMS AND COMPUTATION, PT 2, 2010, 6507 :339-350

[47] Parameterized Searching with Mismatches for Run-Length Encoded Strings [J].

Alberto Apostolico ;

Erdos, Peter L. ;

Alpar Juettner .

STRING PROCESSING AND INFORMATION RETRIEVAL, 2010, 6393 :365-+

[48] How Compression and Approximation Affect Efficiency in String Distance Measures [J].

Ganesh, Arun ;

Kociurnaka, Tornasz ;

Lincoln, Andrea ;

Saha, Barna .

PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2022, :2867-2919

[49] Assessing the best edit in perturbation-based iterative refinement algorithms to compute the median string [J].

Mirabal, P. ;

Abreu, J. ;

Seco, D. .

PATTERN RECOGNITION LETTERS, 2019, 120 :104-111

[50] Some results about the use of tree/string edit distances in a nearest neighbour classification task [J].

Rico-Juan, JR ;

Micó, L .

PATTERN RECOGNITION AND IMAGE ANALYSIS, PROCEEDINGS, 2003, 2652 :821-828

← 1 2 3 4 5 →