Fast text searching
- 1 October 1992
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 35 (10) , 83-91
- https://doi.org/10.1145/135239.135244
Abstract
Summary:searching for all occurrences of a pattern (string or sequence) in some text, where the pattern can occur with some limited number of errors given by edit distance. Several methods were designed for the approximate string matching that simulate nondeterministic finite automata (NFA) constructed for this problem. This paper presents reduced NFAs for the approximate string matching usable in case, when we are interested only in occurrences having edit distance less than or equal to a given integer, but we are not interested in exact edit distance of each found occurrence. Then an algorithm based on the dynamic programming that simulates these reduced NFAs is presented. It is also presented how to use this algorithm for the approximate sequence matchingKeywords
This publication has 14 references indexed in Scilit:
- Approximate string matching in sublinear expected timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An Improved Algorithm For Approximate String MatchingSIAM Journal on Computing, 1990
- Fast parallel and serial approximate string matchingJournal of Algorithms, 1989
- A new approach to text searchingPublished by Association for Computing Machinery (ACM) ,1989
- Fast string matching with k differencesJournal of Computer and System Sciences, 1988
- Data structures and algorithms for approximate string matchingJournal of Complexity, 1988
- Generalized String MatchingSIAM Journal on Computing, 1987
- Approximate String MatchingACM Computing Surveys, 1980
- A fast string searching algorithmCommunications of the ACM, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977