Geodesic
Dynamic programming for reduced NFAs for approximate string and sequence matching
Kybernetika, Tome 38 (2002) no. 1, pp. 81-90 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 matching.
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 matching.
Classification : 68P10, 68Q45, 68T10, 68W05, 68W32, 90C39
Keywords: string and sequence matching; nondeterministic finite automata 
@article{KYB_2002_38_1_a4,
     author = {Holub, Jan},
     title = {Dynamic programming for reduced {NFAs} for approximate string and sequence matching},
     journal = {Kybernetika},
     pages = {81--90},
     year = {2002},
     volume = {38},
     number = {1},
     mrnumber = {1899848},
     zbl = {1265.68042},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2002_38_1_a4/}
}
TY  - JOUR
AU  - Holub, Jan
TI  - Dynamic programming for reduced NFAs for approximate string and sequence matching
JO  - Kybernetika
PY  - 2002
SP  - 81
EP  - 90
VL  - 38
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/KYB_2002_38_1_a4/
LA  - en
ID  - KYB_2002_38_1_a4
ER  - 
%0 Journal Article
%A Holub, Jan
%T Dynamic programming for reduced NFAs for approximate string and sequence matching
%J Kybernetika
%D 2002
%P 81-90
%V 38
%N 1
%U http://geodesic.mathdoc.fr/item/KYB_2002_38_1_a4/
%G en
%F KYB_2002_38_1_a4
Holub, Jan. Dynamic programming for reduced NFAs for approximate string and sequence matching. Kybernetika, Tome 38 (2002) no. 1, pp. 81-90. http://geodesic.mathdoc.fr/item/KYB_2002_38_1_a4/

[1] Baeza-Yates R. A., Gonnet G. H.: A new approach to text searching. Comm. ACM 35 (1992), 10, 74–82 | DOI

[2] Galil Z., Park K.: An improved algorithm for approximate string matching. In: Proceedings of the 16th International Colloquium on Automata, Languages and Programming (G. Ausiello, M. Dezani-Ciancaglini, and S. Ronchi Della Rocca, eds., Lecture Notes in Computer Science 372), Springer–Verlag, Berlin, Stresa 1989, pp. 394–404 | MR | Zbl

[3] Holub J.: Reduced nondeterministic finite automata for approximate string matching. In: Proceedings of the Prague Stringologic Club Workshop’96 (J. Holub, ed.), Czech Technical University, Prague 1996, pp. 19–27. Collaborative Report DC–96–10

[4] Holub J.: Simulation of NFA in approximate string and sequence matching. In: Proceedings of the Prague Stringology Club Workshop’97 (J. Holub, ed.), Czech Technical University, Prague 1997, pp. 39–46. Collaborative Report DC–97–03

[5] Melichar B.: String matching with $k$ differences by finite automata. In: Proceedings of the 13th International Conference on Pattern Recognition, volume II, IEEE Computer Society Press, Vienna 1996, pp. 256–260

[6] Sellers P. H.: The theory and computation of evolutionary distances: Pattern recognition. J. Algorithms 1 (1980), 4, 359–373 | DOI | MR | Zbl

[7] Ukkonen E.: Finding approximate patterns in strings. J. Algorithms 6 (1985), 1–3, 132–137 | DOI | MR | Zbl

[8] Wu S., Manber U.: Fast text searching allowing errors. Comm. ACM 35 (1992), 10, 83–91 | DOI