Average complexity of backward q-gram string matching algorithms

被引：1

作者：

Salmela, Leena ^{[1
,2
]}

机构：

[1] Univ Helsinki, Dept Comp Sci, FI-00014 Helsinki, Finland

[2] Univ Helsinki, Helsinki Inst Informat Technol, FI-00014 Helsinki, Finland

来源：

INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 11期

基金：

芬兰科学院;

关键词：

Analysis of algorithms; String matching; Average case complexity;

D O I：

10.1016/j.ipl.2012.02.010

中图分类号：

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

学科分类号：

0812 ;

摘要：

Many efficient string matching algorithms make use of q-grams and process the text in windows which are read backward. In this paper we provide a framework for analyzing the average case complexity of these algorithms taking into account the statistical dependencies between overlapping q-grams. We apply this to the q-gram Boyer-Moore-Horspool algorithm adapted to various string matching problems and show that the algorithm is optimal on average. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：433 / 437

页数：5

共 17 条

[1] IMPROVED STRING SEARCHING [J].

BAEZAYATES, RA .

SOFTWARE-PRACTICE & EXPERIENCE, 1989, 19 (03) :257-271

[2] FAST STRING SEARCHING ALGORITHM [J].

BOYER, RS ;

MOORE, JS .

COMMUNICATIONS OF THE ACM, 1977, 20 (10) :762-772

[3]

CHANG W, 1994, LECT NOTES COMPUT SC, V807, P259

[4] SPEEDING-UP 2 STRING-MATCHING ALGORITHMS [J].

CROCHEMORE, M ;

CZUMAJ, A ;

GASIENIEC, L ;

JAROMINEK, S ;

LECROQ, T ;

PLANDOWSKI, W ;

RYTTER, W .

ALGORITHMICA, 1994, 12 (4-5) :247-267

[5]

Durian B, 2010, LECT NOTES COMPUT SC, V6049, P129, DOI 10.1007/978-3-642-13193-6_12

[6] Improving practical exact string matching [J].

Durian, Branislav ;

Holub, Jan ;

Peltola, Hannu ;

Tarhio, Jorma .

INFORMATION PROCESSING LETTERS, 2010, 110 (04) :148-152

[7]

Fredriksson K, 2004, ACM J EXP ALGORITH, V9, P1, DOI [DOI 10.1145/1005813.1041513, 10.1145/1005813.1041513]

[8] PRACTICAL FAST SEARCHING IN STRINGS [J].

HORSPOOL, RN .

SOFTWARE-PRACTICE & EXPERIENCE, 1980, 10 (06) :501-506

[9]

Knuth D. E., 1977, SIAM Journal on Computing, V6, P323, DOI 10.1137/0206024

[10] Fast exact string matching algorithms [J].

Lecroq, Thierry .

INFORMATION PROCESSING LETTERS, 2007, 102 (06) :229-235

← 1 2 →