TY - JOUR

T1 - Fast bit-vector algorithms for approximate string matching under indel distance

AU - Hyyrö, Heikki

AU - Pinzon, Yoan

AU - Shinohara, Ayumi

PY - 2005

Y1 - 2005

N2 - The approximate string matching problem is to find all locations at which a query p of length m matches a substring of a text t of length n with at most k differences (insertions, deletions, substitutions). The fastest solutions in practice for this problem are the bit-parallel NFA simulation algorithms of Wu & Manber [4] and Baeza-Yates & Navarro [1], and the bit-parallel dynamic programming algorithm of Myers [3]. In this paper we present modified versions of these algorithms to deal with the restricted case where only insertions and deletions (called indel for short) are permitted. We also show test results with the algorithms.

AB - The approximate string matching problem is to find all locations at which a query p of length m matches a substring of a text t of length n with at most k differences (insertions, deletions, substitutions). The fastest solutions in practice for this problem are the bit-parallel NFA simulation algorithms of Wu & Manber [4] and Baeza-Yates & Navarro [1], and the bit-parallel dynamic programming algorithm of Myers [3]. In this paper we present modified versions of these algorithms to deal with the restricted case where only insertions and deletions (called indel for short) are permitted. We also show test results with the algorithms.

UR - http://www.scopus.com/inward/record.url?scp=24144477474&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=24144477474&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30577-4_44

DO - 10.1007/978-3-540-30577-4_44

M3 - Conference article

AN - SCOPUS:24144477474

SN - 0302-9743

VL - 3381

SP - 380

EP - 384

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 31st Conference on Current Trends in Theory and Practice of Computer Science

Y2 - 22 January 2005 through 28 January 2005

ER -