Fast approximate string matching in a dictionary
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A successful technique to search large textual databases allowing errors relies on an online search in the vocabulary of the text. To reduce the time of that online search, we index the vocabulary as a metric space. We show that with reasonable space overhead we can improve by a factor of two over the fastest online algorithms, when the tolerated error level is low (which is reasonable in text searching).Keywords
This publication has 10 references indexed in Scilit:
- Block addressing indices for approximate text retrievalPublished by Association for Computing Machinery (ACM) ,1997
- FastMapPublished by Association for Computing Machinery (ACM) ,1995
- Fast text searchingCommunications of the ACM, 1992
- Satisfying general proximity / similarity queries with metric treesInformation Processing Letters, 1991
- Fast string matching with k differencesJournal of Computer and System Sciences, 1988
- An algorithm for finding nearest neighbours in (approximately) constant average timePattern Recognition Letters, 1986
- Finding approximate patterns in stringsJournal of Algorithms, 1985
- The theory and computation of evolutionary distances: Pattern recognitionJournal of Algorithms, 1980
- The choice of reference points in best-match file searchingCommunications of the ACM, 1977
- Some approaches to best-match file searchingCommunications of the ACM, 1973