Fuzzy String Matching Using a Prefix Table
DOI:
https://doi.org/10.51408/1963-0065Keywords:
KMP algorithm, Approximate string matching, Fuzzy string matchingAbstract
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.
References
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.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
