Fast and practical approximate string matching

被引：53

作者：

BaezaYates, RA

Perleberg, CH

机构：

[1] Depto. de Cie. de la Comp., Universidad de Chile, Santiago

来源：

INFORMATION PROCESSING LETTERS | 1996年 / 59卷 / 01期

关键词：

algorithms; approximate string matching;

D O I：

10.1016/0020-0190(96)00083-X

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present new algorithms for approximate string matching based in simple, but efficient, ideas. First, we present an algorithm for string matching with mismatches based in arithmetical operations that runs in linear worst case time for most practical cases. This is a new approach to string searching. Second, we present an algorithm for string matching with errors based on partitioning the pattern that requires linear expected time for typical inputs.

引用

页码：21 / 27

页数：7

共 33 条

[1] GENERALIZED STRING MATCHING
ABRAHAMSON, K
[J]. SIAM JOURNAL ON COMPUTING, 1987, 16 (06) : 1039 - 1051
[2] EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH
AHO, AV
CORASICK, MJ
[J]. COMMUNICATIONS OF THE ACM, 1975, 18 (06) : 333 - 340
[3] FAST 2-DIMENSIONAL PATTERN-MATCHING
BAEZAYATES, R
REGNIER, M
[J]. INFORMATION PROCESSING LETTERS, 1993, 45 (01) : 51 - 57
[4] A NEW APPROACH TO TEXT SEARCHING
BAEZAYATES, R
GONNET, GH
[J]. COMMUNICATIONS OF THE ACM, 1992, 35 (10) : 74 - 82
[5] BAEZAYATES R, 1996, P COMB PATT MATCH CP
[6] BAEZAYATES RA, 1992, LECT NOTES COMPUT SC, V644, P185
[7] FAST STRING-MATCHING WITH MISMATCHES
BAEZAYATES, RA
GONNET, GH
[J]. INFORMATION AND COMPUTATION, 1994, 108 (02) : 187 - 199
[8] Chang W. I., 1990, Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6), P116, DOI 10.1109/FSCS.1990.89530
[9] CHANG WI, 1992, LECT NOTES COMPUT SC, V644, P175
[10] Fischer Michael J., 1974, SIAM AMS P, V7, P113

← 1 2 3 4 →