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] minIL: A Simple and Small Index for String Similarity Search with Edit Distance [J].

Yang, Zhong ;

Zheng, Bolong ;

Wang, Xianzhi ;

Li, Guohui ;

Zhou, Xiaofang .

2022 IEEE 38TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2022), 2022, :565-577

[22] A unified framework for string similarity search with edit-distance constraint [J].

Minghe Yu ;

Jin Wang ;

Guoliang Li ;

Yong Zhang ;

Dong Deng ;

Jianhua Feng .

The VLDB Journal, 2017, 26 :249-274

[23] Computing All-vs-All MEMs in Run-Length-Encoded Collections of HiFi Reads [J].

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 [J].

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 [J].

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 [J].

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 [J].

BUNKE, H ;

CSIRIK, J .

INFORMATION PROCESSING LETTERS, 1995, 54 (02) :93-96

[28] EFFICIENT STRING EDIT SIMILARITY JOIN ALGORITHM [J].

Gouda, Karam ;

Rashad, Metwally .

COMPUTING AND INFORMATICS, 2017, 36 (03) :683-704

[29] Efficiently Supporting Edit Distance Based String Similarity Search Using B+-Trees [J].

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 [J].

Badkobeh, Golnaz ;

Fici, Gabriele ;

Kroon, Steve ;

Liptak, Zsuzsanna .

INFORMATION PROCESSING LETTERS, 2013, 113 (17) :604-608

← 1 2 3 4 5 →