Very fast and simple approximate string matching

Authors
Navarro, G Baeza-Yates, R
Citation
G. Navarro et R. Baeza-yates, Very fast and simple approximate string matching, INF PROCESS, 72(1-2), 1999, pp. 65-70
Citations number
12
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
72
Issue
1-2
Year of publication
1999
Pages
65 - 70
Database
ISI
SICI code
0020-0190(19991029)72:1-2<65:VFASAS>2.0.ZU;2-4
Abstract
We improve the fastest known algorithm for approximate string matching, whi ch can be used only for low error levels. By using a new method to verify p otential matches and a new optimization technique for biased texts (such as English), the algorithm also becomes the fastest one for medium error leve ls. This includes most of the interesting cases in this area. (C) 1999 Publ ished by Elsevier Science B.V. All rights reserved.