A NEAR PATTERN-MATCHING SCHEME BASED UPON PRINCIPAL COMPONENT ANALYSIS

被引：15

作者：

CHEN, CY

CHANG, CC

LEE, RCT

机构：

[1] NATL CHUNG CHENG UNIV,INST COMP SCI & INFORMAT ENGN,CHIAYI 62107,TAIWAN

[2] NATL TSING HUA UNIV,INST COMP SCI,HSINCHU 30043,TAIWAN

[3] PROVIDENCE UNIV,TAICHUNG 43301,TAIWAN

[4] FENG CHIA UNIV,DEPT ELECTR,TAICHUNG 40724,TAIWAN

来源：

PATTERN RECOGNITION LETTERS | 1995年 / 16卷 / 04期

关键词：

NEAR PATTERN-MATCHING; PRINCIPAL COMPONENTS ANALYSIS; BINARY SEARCH;

D O I：

10.1016/0167-8655(94)00109-G

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, we present an efficient heuristic near pattern-matching scheme. Based upon an important multivariate analysis technique in statistics, called the principal components analysis, we develop algorithms to generate a set of new identifying keys for a given set of patterns to reduce the number of comparisons during the near-matching process. After some preprocessing work, the near-matching operation takes O(n log m) time in the worst case, where m is the number of identifying segments extracted from the patterns to be searched in a text file of length n.

引用

页码：339 / 345

页数：7

共 13 条

[1] AFIFI AA, 1990, COMPUTER AIDED MULTI
[2] EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH
AHO, AV
CORASICK, MJ
[J]. COMMUNICATIONS OF THE ACM, 1975, 18 (06) : 333 - 340
[3] BERKOVICH SY, 1985, AUG P INT S NEW DIR, P122
[4] FAST STRING SEARCHING ALGORITHM
BOYER, RS
MOORE, JS
[J]. COMMUNICATIONS OF THE ACM, 1977, 20 (10) : 762 - 772
[5] ON GENERALIZED KARHUNEN-LOEVE EXPANSION
CHIEN, YT
FU, KS
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1967, 13 (03) : 518 - +
[6] Fu K. S., 1968, SEQUENTIAL METHODS P, V240, P241
[7] Horowitz E., 1978, FUNDAMENTALS COMPUTE
[8] KNUTH DE, 1970, SIAM J COMPUT, V6, P323
[9] Lee R. C. T., 1976, IEEE Transactions on Software Engineering, VSE-2, P185, DOI 10.1109/TSE.1976.225946
[10] Morrison D.F, 1990, MULTIVARIATE STAT ME, P495

← 1 2 →