Edit distance of run-length encoded strings

被引：23

作者：

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
Apostolico, A
Landau, GM
Skiena, S
[J]. JOURNAL OF COMPLEXITY, 1999, 15 (01) : 4 - 16
[2] AN IMPROVED ALGORITHM FOR COMPUTING THE EDIT DISTANCE OF RUN-LENGTH CODED STRINGS
BUNKE, H
CSIRIK, J
[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
UKKONEN, E
[J]. JOURNAL OF ALGORITHMS, 1985, 6 (01) : 132 - 137
[9] ALGORITHMS FOR APPROXIMATE STRING MATCHING
UKKONEN, E
[J]. INFORMATION AND CONTROL, 1985, 64 (1-3): : 100 - 118

← 1 →