Edit distance of run-length encoded strings

被引：24

作者：

Arbell, O ^{[1
]}

Landau, GM ^{[1
]}

Mitchell, JSB ^{[1
]}

机构：

[1] Univ Haifa, Dept Comp Sci, IL-31905 Haifa, Israel

来源：

INFORMATION PROCESSING LETTERS | 2002年 / 83卷 / 06期

基金：

美国国家科学基金会; 以色列科学基金会;

关键词：

string matching; dynamic programming; run-length compression; edit distance; algorithms;

D O I：

10.1016/S0020-0190(02)00215-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let X and Y be two run-length encoded strings, of encoded lengths k and 1, respectively. We present a simple 0(\X\l + \Y\k) time algorithm that computes their edit distance. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：307 / 314

页数：8

共 9 条

[1] Matching for run-length encoded strings [J].

Apostolico, A ;

Landau, GM ;

Skiena, S .

JOURNAL OF COMPLEXITY, 1999, 15 (01) :4-16

[2] 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

[3]

Crochemore M, 2002, SIAM PROC S, P679

[4]

Levenshtein V.I., 1966, SOV PHYS DOKL, V10, DOI DOI 10.1109/TVCG.2012.323

[5]

MAKINEN V, 2001, P 12 COMB PATT MACH, V2089, P31

[6]

Mitchell J.S.B., 1997, GEOMETRIC SHORTEST P

[7]

SANKOFF D, 1983, TIME WARPS STRING ED

[8] FINDING APPROXIMATE PATTERNS IN STRINGS [J].

UKKONEN, E .

JOURNAL OF ALGORITHMS, 1985, 6 (01) :132-137

[9] ALGORITHMS FOR APPROXIMATE STRING MATCHING [J].

UKKONEN, E .

INFORMATION AND CONTROL, 1985, 64 (1-3) :100-118

← 1 →