| Title:
|
Dynamic programming for reduced NFAs for approximate string and sequence matching (English) |
| Author:
|
Holub, Jan |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
38 |
| Issue:
|
1 |
| Year:
|
2002 |
| Pages:
|
[81]-90 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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 matching. (English) |
| Keyword:
|
string and sequence matching |
| Keyword:
|
nondeterministic finite automata |
| MSC:
|
68P10 |
| MSC:
|
68Q45 |
| MSC:
|
68T10 |
| MSC:
|
68W05 |
| MSC:
|
68W32 |
| MSC:
|
90C39 |
| idZBL:
|
Zbl 1265.68042 |
| idMR:
|
MR1899848 |
| . |
| Date available:
|
2009-09-24T19:44:05Z |
| Last updated:
|
2015-03-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135447 |
| . |
| Reference:
|
[1] Baeza-Yates R. A., Gonnet G. H.: A new approach to text searching.Comm. ACM 35 (1992), 10, 74–82 10.1145/135239.135243 |
| Reference:
|
[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 Zbl 0683.68034, MR 1037064 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[6] Sellers P. H.: The theory and computation of evolutionary distances: Pattern recognition.J. Algorithms 1 (1980), 4, 359–373 Zbl 0454.68110, MR 0604870, 10.1016/0196-6774(80)90016-4 |
| Reference:
|
[7] Ukkonen E.: Finding approximate patterns in strings.J. Algorithms 6 (1985), 1–3, 132–137 Zbl 0566.68072, MR 0780855, 10.1016/0196-6774(85)90023-9 |
| Reference:
|
[8] Wu S., Manber U.: Fast text searching allowing errors.Comm. ACM 35 (1992), 10, 83–91 10.1145/135239.135244 |
| . |
