Fuzzy String Matching Using a Prefix Table - Kostanyan, Armen H. (Изд-во НАН РА)
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. Տողում ենթատողի որոնման խնդիրը արհեստական բանականության տարբեր բնագավառներոմ լայն կիրառում ունեցող խնդիրներից է։ Նշված խնդրի լուծման հանրահայտ ալգորիթմներն են՝ վերջավոր ավտոմատների մեթոդը և Կնուտի-Մորիսի-Պրատի (ԿՄՊ) ալգորիթմը։ Տվյալ հոդվածում դիտարկվում է հստակ տողում (տեքստում) ոչ հստակ ենթատողի (շաբլոնի) որոնման խնդիրը։ Ոչ հստակ ենթատողը սահմանվում է որպես տեքստի սիմվոլների ոչ հստակ հատկությունների հաջորդականություն։ Խնդրի լուծումը կառուցվում է ԿՄՊ ալգորիթմում օգտագործվող նախածանցների միաչափ աղյուսակի երկչափ ընդլայնման եղանակով։ Задача поиска подстроки в строке одна из часто встречающихся задач в области символических вычислений, имеющая многочисленные применения в задачах искусственного интеллекта. К числу наиболее известных алгоритмов для ее решения относятся метод конечных автоматов и алгоритм Кнута-Морриса-Прата (алгоритм КМП). В настоящей статье рассматривается задача поиска всех вхождений нечеткой подстроки в строке. При этом нечеткая подстрока определяется как последовательность нечетких свойств символов строки (текста). Поставленная задача решается с помощью двумерной таблицы префиксов, являющейся обобщением одномерной таблицы префиксов, используемой в алгоритме КМП
Keywords: Mathematical cybernetics; Computer science