Fuzzy String Matching Using a Prefix Table
Keywords:KMP algorithm, Approximate string matching, Fuzzy string matching
The string matching problem (that is, the problem of finding all occurrences of a pattern in the text) is one of the well-known problems in symbolic computations with applications in many areas of artificial intelligence. The most famous algorithms for solving it are the finite state machine method and the Knuth-Morris-Pratt algorithm (KMP). In this paper, we consider the problem of finding all occurrences of a fuzzy pattern in the text. Such a pattern is defined as a sequence of fuzzy properties of text characters. To construct a solution to this problem, we introduce a two-dimensional prefix table, which is a generalization of the one-dimensional prefix array used in the KMP algorithm.
R. S. Boyer and J. S. Moore, “A fast string matching algorithm,” Association for Computing Machinery, vol. 20, no. 10, pp. 762-772, 1977.
D. Knuth and M. Pratt, “Fast pattern matching in strings,” SIAM J. Comput. vol. 6, no. 2, pp. 323-350, 1977.
G. Landau and U. Vishkin, “Efficient string matching with k mismatches,” TCS, vol. 43, pp. 239-249, 1986.
R. Baeza-Yates and N. Gonzaio, “A faster algorithm for approximate string matching,” in Proc. of Seventh Annual Symp. Combinatorial Pattern Matching, Spinger-Verlag, 1996, pp. 1-23.
B. Smyth, “Computing Patterns in Strings”, Addison-Wesley UK, 2003.
A. Kostanyan, “Fuzzy String Matching with Finite Automata”, in Proceedings on 2017 IEEE Conference CSIT-2017, Yerevan, Armenia, pp. 25-29. IEEE Press, USA 2018.
L. A. Zadeh, “The concept of a linguistic variable and its application to approximate reasoning-I,” Information Sciences, vol. 8, pp. 199-249, 1975.