Dynamic programming for reduced NFAs for approximate string and sequence matching
Kybernetika (2002)
- Volume: 38, Issue: 1, page [81]-90
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topHolub, Jan. "Dynamic programming for reduced NFAs for approximate string and sequence matching." Kybernetika 38.1 (2002): [81]-90. <http://eudml.org/doc/33568>.
@article{Holub2002,
abstract = {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.},
author = {Holub, Jan},
journal = {Kybernetika},
keywords = {string and sequence matching; nondeterministic finite automata; string and sequence matching; nondeterministic finite automata},
language = {eng},
number = {1},
pages = {[81]-90},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Dynamic programming for reduced NFAs for approximate string and sequence matching},
url = {http://eudml.org/doc/33568},
volume = {38},
year = {2002},
}
TY - JOUR
AU - Holub, Jan
TI - Dynamic programming for reduced NFAs for approximate string and sequence matching
JO - Kybernetika
PY - 2002
PB - Institute of Information Theory and Automation AS CR
VL - 38
IS - 1
SP - [81]
EP - 90
AB - 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.
LA - eng
KW - string and sequence matching; nondeterministic finite automata; string and sequence matching; nondeterministic finite automata
UR - http://eudml.org/doc/33568
ER -
References
top- Baeza-Yates R. A., Gonnet G. H., 10.1145/135239.135243, Comm. ACM 35 (1992), 10, 74–82 (1992) DOI10.1145/135239.135243
- 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 (1989) Zbl0683.68034MR1037064
- 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 (1996)
- 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 (1997)
- Melichar B., String matching with 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 (1996)
- Sellers P. H., 10.1016/0196-6774(80)90016-4, J. Algorithms 1 (1980), 4, 359–373 (1980) Zbl0454.68110MR0604870DOI10.1016/0196-6774(80)90016-4
- Ukkonen E., 10.1016/0196-6774(85)90023-9, J. Algorithms 6 (1985), 1–3, 132–137 (1985) Zbl0566.68072MR0780855DOI10.1016/0196-6774(85)90023-9
- Wu S., Manber U., 10.1145/135239.135244, Comm. ACM 35 (1992), 10, 83–91 (1992) DOI10.1145/135239.135244
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.