zbMATH — the first resource for mathematics

Approximate string matching using factor automata. (English) Zbl 0949.68088
Given a text \(T\) over alphabet \(\Sigma\) and a complete index for \(T\) constructed using the finite automaton (called the factor automaton or DAWG) accepting all the substrings (factors) of text \(T.\) An answer to the query whether a pattern \(P\) occurs in text \(T\) with \(k\) differences is discussed to be done by an algorithm having the time complexity independent on the length of text \(T.\) The algorithm searches for the final state of the finite automaton accepting the intersection of languages \(\text{Fac}(T)\) (the set of all factors of \(T)\) and \(L_{k}(P)\) (the set of all strings having at most \(k\) differences with respect to pattern \(P\)).

68Q45 Formal languages and automata
Full Text: DOI
[1] Baeza-Yates, R.A.; Gonnet, G.H., A new approach to text searching, Commun. ACM., 35, 10, 74-82, (1992)
[2] Blumer, A.; Blumer, J.; Ehrenfeucht, A.; Haussler, D.; McConnel, R., Complete inverted files for efficient text retrieval and analysis, J. assoc. comput. Mach., 34, 3, 578-595, (1987)
[3] Crochemore, M.; Hancart, C., Automata for matching patterns, (), 399-462, (Chapter 9)
[4] Crochemore, M.; Rytter, W., Text algorithms, (1994), Oxford University Press Oxford · Zbl 0844.68101
[5] M. Crochemore, R. Vérin, Direct construction of compact directed acyclic word graphs, in: A. Apostolico, J. Hein (Eds.), Proc. 8th Ann. Symp. Combinatorial Pattern Matching, Aarhus, Denmark, 1997, Lecture Notes in Computer Science, vol. 1264, Springer, Berlin, pp. 116-129.
[6] J. Holub, Dynamic programming for reduced NFAs for approximate string and sequence matching, in: J. Holub, M. Šimánek (Eds.), Proc Prague Stringology Club Workshop ’98, Czech Technical University, Prague, Czech Republic, 1998, Collaborative Report DC-98-06, pp. 73-82.
[7] J. Holub, B. Melichar, Approximate string matching using factor automata, in: C.S. Iliopoulos (Ed.), Proc. 9th Australasian Workshop On Combinatorial Algorithms, Perth, WA, Australia, 1998, pp. 28-39. · Zbl 0949.68088
[8] Hopcroft, J.E.; Ullman, J.D., Introduction to automata, languages and computations, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[9] Ukkonen, E., Algorithms for approximate string matching, Inf. control, 64, 1-3, 100-118, (1985) · Zbl 0575.68090
[10] Wu, S.; Manber, U., Fast text searching allowing errors, Comm. ACM, 35, 10, 83-91, (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.