Beispiel: Aho-Corasick

Beispiel: Aho-Corasick-Algorithmus
Präprozessing: Konstruiere Trie mit Fehler- und Ausgabe-Links
P = {1032104, 2010321041, 22412430}
1i
0- 3i 3- 6i 2- 9i 1- 12i 0- 15i 4- 18i
m
1
m1- 24i
m
- 0i 2- 2i 0- 4i 1- 7i 0- 10i 3- 13i 2- 16i 1- 19i 0- 21i 4- 23i
@
2@
@
R i 4- i 1- i 2- i 4- i 3- i 0- i
m
5
v
Fail v
Out v
8
11
14
17
20
22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0 0 0 2 0 1 0 2 3 1 1 6 2 3 9 0 0 12 0 15 0 18 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0
Beispiel: Aho-Corasick-Algorithmus
Zustandsfolge
1 0 0 2 2 1 2 0 1 0 3 2 1 0 4 2 1 3 0 4 4 2 1 0
0 1 3 0 2 5 2 0 4 7 10 13 16 19 21 23 18 0 0 0 0 0 2 0 3
1
0 2
0 1
1
2
1i
0- 3i 3- 6i 2- 9i 1- 12i 0- 15i 4- 18i
m
1
m1- 24i
m
- 0i 2- 2i 0- 4i 1- 7i 0- 10i 3- 13i 2- 16i 1- 19i 0- 21i 4- 23i
@
2@
@
R i 4- i 1- i 2- i 4- i 3- i 0- i
m
5
v
Fail v
Out v
8
11
14
17
20
22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0 0 0 2 0 1 0 2 3 1 1 6 2 3 9 0 0 12 0 15 0 18 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0
Beispiel: DEA-Algorithmus
Konstruktion des DEA
1i
0- 3i 3- 6i 2- 9i 1- 12i 0- 15i 4- 18i
m
1
m1- 24i
m
- 0i 2- 2i 0- 4i 1- 7i 0- 10i 3- 13i 2- 16i 1- 19i 0- 21i 4- 23i
@
2@
@
R i 4- i 1- i 2- i 4- i 3- i 0- i
m
5
v
Fail v
0
1
2
3
4
8
11
14
17
20
22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0 0 0 2 0 1 0 2 3 1 1 6 2 3 9 0 0 12 0 15 0 18 1
0
0
1
2
0
0
1
3
1
2
0
0
2
4
1
5
0
0
3
0
1
2
6
0
4
0
7
2
0
0
5
4
1
5
0
8
6
0
1
9
0
0
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
10 0 4 0 3 15 0 2 0 4 0 0 21 22 0 0 0 3
1 11 12 1 1 1 1 1 1 19 1 1 1 1 1 1 24 1
2 2 5 2 14 2 16 5 2 5 2 2 2 2 2 2 2 2
0 0 0 13 0 0 0 0 6 0 20 0 0 0 6 0 0 0
0 0 0 0 0 0 0 17 18 0 0 0 0 0 23 0 0 0
Beispiel: DEA-Algorithmus
Zustandsfolge
1 0 0 2 2 1 2 0 1 0 3 2 1 0 4 2 1 3 0 4 4 2 1 0
0 1 3 0 2 5 1 2 4 7 10 13 16 19 21 23 2 1 0 0 0 0 2 1 3
1i
0- 3i 3- 6i 2- 9i 1- 12i 0- 15i 4- 18i
m
1
- 0i 2- 2i 0- 4i 1- 7i 0- 10i 3- 13i 2- 16i 1- 19i 0- 21i 4- 23i
m1- 24i
m
@
2@
@
R i 4- i 1- i 2- i 4- i 3- i 0- i
m
5
0
1
2
3
4
0
0
1
2
0
0
1
3
1
2
0
0
2
4
1
5
0
0
3
0
1
2
6
0
8
4
0
7
2
0
0
5
4
1
5
0
8
6
0
1
9
0
0
11
14
17
20
22
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
10 0 4 0 3 15 0 2 0 4 0 0 21 22 0 0 0 3
1 11 12 1 1 1 1 1 1 19 1 1 1 1 1 1 24 1
2 2 5 2 14 2 16 5 2 5 2 2 2 2 2 2 2 2
0 0 0 13 0 0 0 0 6 0 20 0 0 0 6 0 0 0
0 0 0 0 0 0 0 17 18 0 0 0 0 0 23 0 0 0

Download Report