Open AccessFuzzy String Matching Using a Prefix Table
Author(s) -
Armen Kostanyan
Publication year - 2020
Publication title -
mathematical problems of computer science
Language(s) - English
Resource type - Journals
eISSN - 2738-2788
pISSN - 2579-2784
DOI - 10.51408/1963-0065
Subject(s) - prefix , approximate string matching , string searching algorithm , generalization , string (physics) , pattern matching , computer science , matching (statistics) , construct (python library) , table (database) , sequence (biology) , algorithm , commentz walter algorithm , trie , mathematics , theoretical computer science , artificial intelligence , data structure , data mining , mathematical analysis , philosophy , linguistics , statistics , genetics , biology , mathematical physics , programming language
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.