Fast and practical approximate string matching

被引：55
作者：
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 [J].
ABRAHAMSON, K .
SIAM JOURNAL ON COMPUTING, 1987, 16 (06) :1039-1051
[2]   EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH [J].
AHO, AV ;
CORASICK, MJ .
COMMUNICATIONS OF THE ACM, 1975, 18 (06) :333-340
[3]   FAST 2-DIMENSIONAL PATTERN-MATCHING [J].
BAEZAYATES, R ;
REGNIER, M .
INFORMATION PROCESSING LETTERS, 1993, 45 (01) :51-57
[4]   A NEW APPROACH TO TEXT SEARCHING [J].
BAEZAYATES, R ;
GONNET, GH .
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 [J].
BAEZAYATES, RA ;
GONNET, GH .
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
1234