Pattern matching problem is still very interesting and important problem. Algorithms for the exact pattern matching search for exact patterns in some texts or figures. Algorithms for an approximate pattern matching search for exact and similar patterns with some errors. They use some measures to evaluate a similarity of found similar patterns. In the area of the pattern matching allowing errors is possible to use fuzzy logic theory. In the paper we present the algorithm for a fuzzification of a deterministic finite state automaton using a similarity function of characters. The fuzzified automaton will accept exact and similar words. The second presented algorithm is a fuzzy modification of Aho-Corasick pattern matching algorithm which still work in linear time with respect to the length of the searching text.
The motivation to the Fuzzy Pattern Matching Problem
(FPMP) can be found in Exact Pattern Matching Problem
(EPMP). Words they are very closed to patterns (maybe
words with one error) will not be found in EPMP. A quite
good example is the typing of some text on the keyboard
[
borhood of the current character on a keyboard.
the required character is typed a character from the area on the keyboard adjacent to the required character. For example, the neighborhood of the character f is the set fn = {f, d, g, r, t, c, v}. The set of characters A = {f, r, o, l, i, c} belongs to the pattern frolic. In this case of typing errors, let us assign similarity value ( f ) to each element of the neighborhood in such way that the character itself has f equal to 1 and the characters from the f ’s neighborhood have f value < 1, because they really represent some error.
in many ways, for example the closest characters to the character on keyboard, the similar characters to the given character because of they have the same shape, and so on.
values of characters [
In the string matching problem allowing errors, an
input text, maybe containing errors, and a pattern string are
compared in order to find an imperfect pattern in input
text. Very interesting fuzzy measure between strings
using fuzzy automata with ε -moves was given in [
used notions and concepts needed to understand the problem, mainly fuzzy logic connectives and fuzzy automata.
2
ized by a membership function which associates to each
element x ∈ U a real number A(x) ∈ [
the membership degree of x in A. We use F (U ) to denote the set of all fuzzy sets on U . As the basic book for notions in the theory of fuzzy sets and fuzzy logic, we used
Definition 1. A mapping T : [
t-norms are considered as truth functions of generalized conjunction operators. s-conorms are considered as truth functions of generalized disjunction operators.
Remark 1. Well known t-norms: 1. Gödel conjunction: x TG y = TG(x, y) = min(x, y), 2. Lukasiewicz conjunction: x TL y = TL(x, y) = max{x + y − 1, 0}, 3. Product conjunction: x TP y = TP(x, y) = x ∗ y.
Definition 2. For a fuzzy subset V of A and a binary fuzzy relation R on A, the compositions V • R and R •V are fuzzy subsets of A defined, for any x∈ A, by (V • R)(x) (R • V )(x) = = max{T (V (y), R(y, x))}, y∈A max{T (R(x, y),V (y))} y∈A Example 1. Let V = {(a, 0.4), (b, 0.7), (c, 0.5)} be the fuzzy subset of A. Let A × A be the binary fuzzy relation defined by the Table 1. The composition of V by A× A can be done from the left and from the right side. If A × A is not symmetric relation then we can get different fuzzy sets. Definition 3. A fuzzy finite state automaton FA is a quintuple (Σ, Q, μ , S, F ), where: 2 (1) (2) 2 2 a b c
For each x ∈ Σ, μx is binary fuzzy relation on a set of
states Q. It is a fuzzy set of the Cartesian product Q × Q.
μx(p, q) ∈ [
μ Sts .1 0 0 Example 2. The fuzzy finite automaton FA1 = (Σ, Q, μ , S, F ), Σ = {a, b, c}, Q = {q0, q1, q2}, S = {q0}, S(q0) = 1, F = {q2}, F (q2) = 1, and transition functions for symbols in Σ are in the Table 2, the automaton is drawn in the Figure 1 . μb(q0, q1) = 0.1 and it can be explained as the compliance degree of interaction between states q0 and q1 for the symbol b. μa(q0, q0) = 0.4 is the compliance degree of interaction between states q0 and q0 for the symbol a. • Σ is a non-empty finite set of input characters (input alphabet), • Q is a non-empty finite set of states, • S, S ⊆ Q is a fuzzy set of a starting states on Q, • F, F ⊆ Q is a fuzzy set of final (accepting) states on
Q,
• μ : Q × Q × Σ → [
(V1 •TG μb)(q0) = maxq∈Q{TG(V1(q), μb(q, q0))} = V2(q0) = 0,
(V1 •TG μb)(q1) = maxq∈Q{TG(V1(q), μb(q, q1))} = V2(q1) = 0.1,
(V1 •TG μb)(q2) = maxq∈Q{TG(V1(q), μb(q, q2))} = V2(q2) = 0,
V2 = {(q0, 0), (q1, 0.1), (q2, 0)}.
Definition 4. Let R1 and R2 be two fuzzy binary relations on Q × Q, T be some t-norm. The max-T composition between R1 and R2, denoted R1 ◦T R2, is the fuzzy set on Q × Q such that for all (p, q) ∈ Q × Q
R1 ◦T R2(p, q) = maxr∈Q{T (R1(p, r), R2(r, q))}. (4) 2 Example 4. Let R1 = μa and R2 = μb be two fuzzy relations on Q × Q in the Example 2. Let TG be Gödel t-norm. The max − TG composition between μa and μb, is given in the Table 3. For example, μa ◦TG μb(q0, q1) can be computed as μa ◦TG μb(q0, q1) = maxr∈Q{TG{μa(q0, r), μb(r, q1)}} = .1, where min{μa(q0, q0), μb(q0, q1)} = min{0.4, 0.1} = 0.1, min{μa(q0, q1), μb(q1, q1)} = min{0, 0} = 0, min{μa(q0, q2), μb(q2, q1)} = min{0, 0} = 0, max{0.1, 0, 0} = 0.1 μ Sts .1 0 0
Definition 5. Let FA = (Σ, Q, μ, S, F) be a fuzzy finite state automaton.
(i) μˆ: F (Q) × Σ → F (Q) is the fuzzy state transition function. Given a fuzzy state V ∈ F (Q) and a symbol a ∈ Σ it is μˆ(V, a) = V •T μa, the result is a fuzzy state. (ii) μ∗ : F (Q) × Σ∗ → F (Q) is the extended transition function defined as (a) μ∗(V, ε) = V, for all V ∈ F (Q) (the result is a fuzzy state). (b) μ∗(V, αx) = μˆ(μ∗(V, α), x) = μ∗(V, α) •T μx, for all V ∈ F (Q), α ∈ Σ∗ and x ∈ Σ. • The language accepted by FA, denoted L (FA), is the fuzzy set on Σ∗ such that L (FA)(α) = maxq∈Q{T (μ∗(S, α)(q), F(q))} for all α ∈ Σ∗. Example 5. The value of the membership function for some word in L (FA) depends on used t-norm. For example, the word α =0 bca0 is accepted by FA1 in the Example 1. The starting fuzzy state is S = {(q0, 1), (q1, 0), (q2, 0)} and the finite fuzzy state is S= {(q0, 0), (q1, 0), (q2, 1)}. The membership values are: • TG: L (FA1)(α) = maxq∈Q{TG(μ∗(S, α)(q), F(q))}, μ∗(S,0 bca0) = μˆ(μ∗(S,0 bc0), a), μ∗(S,0 bc0) = μˆ(μ∗(S,0 b0), c), μ∗(S,0 b0) = μˆ(μ∗(S, ε), b) = {(q0, 0), (q1, 0.1), (q2, 0)} = S1, μ∗(S,0 bc0) = μˆ(μ∗(S,0 b0), c) {(q0, 0), (q1, 0.1), (q2, 0)} = S2, μ∗(S,0 bca0) = μˆ(μ∗(S,0 bc0), a) = μˆ(S2, a) = {(q0, 0), (q1, 0), (q2, 0.1)} = S3.
S •TG μb
=
μˆ(S1, c)
2
=
=
Using the Gödel conjunction the membership value
of the word is 0.1.
f : Σ × Σ → [
Fuzzification of DFA using a similarity
function
We will work with some deterministic finite state
automaton (DFA) M defined by [
Example 6. Let A be a deterministic finite state automaton A = (Σ, Q, δ , q0, F), Σ = {A, B,C}, Q = {q0, . . . , q7}, F = {q4, q6, q7}, δ is in the Table 6. Some results of the decomposition of δ according to states is in the Table 5.
Sts → q0 q1 q2 q3 q4 → q5 q6 → q7 →
A q1 − q3 − − − − −
B q5 q2 q5 q4 q5 q6 − −
C − − − − − q7 − − • R is reflexive if R(p, p) is defined for each p∈ Q. • R is symmetric if R(p, q) = R(q, p) for all p, q ∈ Q. If R is reflexive, and symmetric then R is called proximity relation. If R is also t-transitive, then R is called tsimilarity relation.
Definition 7. Let Σ = {a1, a2, . . . an} be some finite alphabet of characters used in some text. Each function f (ai, a j) = f (a j, ai) = 1, if ai = a j, v, v ∈ [0, 1), if ai 6= a j. δ∗ Sts
each pair of characters in Σ. A value v ∈ [
the similarity function it is necessary to choose some adequate fuzzy logic connectives. One of them is a max-T composition of two binary relations defined by (6). Definition 8. Let R1 be a fuzzy binary relation on Q × Σ and R2 be a fuzzy binary relation on Σ × Σ. The max − T composition between R1 and R2, denoted R1 ◦T R2, is the fuzzy set on Q × Σ such that for all p ∈ Q and a ∈ Σ R1 ◦T R2(p, a) = maxx∈Σ{T (R1(p, x), R2(x, a))}.
Q × Σ and R2 be a proximity relation representing a
similarity function f . Using (6) we will get the decomposed
(according to states) fuzzy transition functions of the
corresponding fuzzy automaton qμ : Q × Σ → [
μ(q, p, a) = = qμ(p, a) = (δq ◦T f )(p, a) maxx∈Σ{T (δq(p, x), f (x, a))} Example 7. The application of max − TG (Gödel conjunction) composition to δq and the similarity function f . Similarity function: f (A, A) = f (B, B) = f (C,C) = 1, f (A, B) = f (B, A) = 0, f (B,C) = f (C, B) = 0, f (C, A) = f (A,C) = 0.3. (5) 2 (6) 2 (7) μ Sts
If we analyze the formula (7), we should see that the value δq(p, x) represent the transition value in DFA, it means δq(p, x) ∈ {0, 1}. From the property follows that in the formula (7) should be used arbitrary t-norm T . The algorithm needs information about DFA and the similarity function. Using nested four cycles to formula (7) we will get the fuzzy transition function of the new automaton FA = (Σ, Q, μ , {q0f }, F f ), where {q0f }, F f ) are sets of fuzzy states. The time complexity is O(|Q|2.|Σ|2) in the worst case. In the common case, FA can be a nondeterministic finite automaton. Using some special conditions in DFA or in similarity functions FA can be deterministic. 4
small number of exact key words in some long texts.
key words, the automaton is DFA. The construction is modified using a similarity function using composition operation of binary relations described by formula (7).
The three basic functions of Aho-Corasick algorithm are: • a Goto function based on an automaton DFA, which maps (state, character) pairs to states and occasionally emits an output, • a Failure function, which tells the Goto function which state to jump into when the character it just read doesn’t match anything, • an Output function, which maps states to outputs sometimes more outputs than one per state. 4.1
Failure function
tion is done in a recursive way using a queue of states they are waiting for processing.
sition from state q0 will be put into the queue. The queue in our Example 7: (: 1, 5 :).
The value of the failure function f ail in the state q0 and in all states with possible transition from the state q0 will be q0, f ail[q0] = q0. f ail[s] = q0 if there exists some transition from state q0 to s. 2. While the queue is not empty the first element is taken from the queue to r and transitions from r for all symbols of alphabet are analyzed. If the transition for symbol i is possible then to t is assigned f ail(r) and to s the result state of the transition from the state r through symbol i. While a transition from state t through symbol i is not possible then t := f ail(t). After finding the possible transition from statet through symbol i to state v, the value of the failure function in the state s is put to state v. The state s is put in the end of the queue. 4.2
Fuzzy Aho-Corasick algorithm: 1. To prepare the searched patterns, let P be the length of all patterns. To build the alphabet of used characters Σ, |Σ| ≤ P. Σ will be the alphabet of DFA. To prepare the function f of similarity for characters. The similarity function describes the measure of character similarities.
Corasick Automaton (ACA) with the transition function δ . |Q|, |Q| ≤ P is the number of states. To remove all transitions from q0 to q0. Let Σq0 be the alphabet of characters of possible transitions from state q0 to the some other state (not to q0). The time complexity is O(|Q|2.|Σ|). 3. To prepare the fuzzification of ACA and to process the output of each state together with membership values. To return all removed transitions from q0 to q0 using the alphabet Σq0 . We get FACA. The time complexity is O(|Q|2.|Σ|2) = O(P4) in the worst case. 4. To build failure function f ail and modified output of all states in FACA. The time complexity is O(|Q|2). 5. To use FACA for a searching of patterns in some text given in the file and to print all founded positions of the found patterns. The FACA finds the patterns and their membership values. the text is read is analyzed in one step, it means, the linear time in the length of the text. Many texts should be searched by the prepared automaton and they will be read once only. 5
Example 8. We construct the fuzzy automaton to the following patterns.
Patterns: "ABAB", "BB", "BC".
Alphabet: Σ = {A, B,C}.
The deterministic finite state automaton is A = (Σ, Q, δ , q0, F ), Q = {q0, . . . , q7}, F = {q4, q6, q7}. δ is in the Table 6.
We will use the similarity function from Example 7.
The fuzzy transition function from a state using a character to some state. The value −1 means any transition.
Real numbers present membership values. In the output, there are exact and similar words together with their membership values to the accepted language.
Failure function f ail:
To state Transition function of the FACA
A q1 : 1.0 -1 : 0.0 q3 : 1.0 -1 : 0.0
B q5 : 1.0 q2 : 1.0 -1 : 0.0 q4 : 1.0
lowing text string: ’ABABBCCCBAB’ gives the following results:
pattern
ABAB fuzzy value
use fuzzy logic theory in the area of the pattern matching.
and do not give any information about words with one error only. The information that the word is very closed to the pattern should be very important. It is enough for people to analyze this word in next time.