Fuzzy String Matching Using a Prefix Table

Authors

  • Armen H. Kostanyan Yerevan State University

DOI:

https://doi.org/10.51408/1963-0065

Keywords:

KMP algorithm, Approximate string matching, Fuzzy string matching

Abstract

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

2021-12-10

How to Cite

Kostanyan, A. H. . (2021). Fuzzy String Matching Using a Prefix Table. Mathematical Problems of Computer Science, 54, 116–121. https://doi.org/10.51408/1963-0065