Beispiel: Wu-Manber-Algorithmus
P = {1032104, 2010321041, 22412430}
Präprozessing: Bestimmung der Tabellen SHIFT und PAT
Hash 1(ab) = (5a + b) mod 16.
Block
Hash 1
SHIFT
00,31
01,32
02,33
03,34
04,40
10,41
11,42
12,43
13,44
0
6
1
3
2
6
3
4
4
0
5
0
6
6
7
1
8
6
14
9
6
20
10
6
21
11
2
22
12
6
23
13
6
24
14
2
30
15
0
Hash 2(ab) = (5a + b) mod 4.
Hash 2(P1) = Hash 2(04) = 0, Hash 2(P2) = Hash 2(41) = 1, Hash 2(P3) = Hash 2(30) = 3.
Hash 2
PAT
0
{1}
1
{2}
2
∅
R. Stiebe: Textalgorithmen, WS 2005/06
3
{3}
1
Wu-Manber-Algorithmus: Suche
1 0 0 2 2 1 2 0 1 0 3 2 1 0 4 2 1 3 0 4 4 2 1 0
1. Versuch:
Hash 1(12) = 7; SHIFT 7 = 1; Verschiebung: 1.
1 0 0 2 2 1 2 0 1 0 3 2 1 0 4 2 1 3 0 4 4 2 1 0
2. Versuch:
Hash 1(20) = 10; SHIFT 10 = 6; Verschiebung: 6.
Hash 1
SHIFT
0
6
1
3
2
6
3
4
4
0
R. Stiebe: Textalgorithmen, WS 2005/06
5
0
6
6
7
1
8
6
9
6
10
6
11
2
12
6
13
6
14
2
15
0
2
Wu-Manber-Algorithmus: Suche
1 0 0 2 2 1 2 0 1 0 3 2 1 0 4 2 1 3 0 4 4 2 1 0
3. Versuch:
Hash 1(10) = 5; SHIFT 5 = 0; Hash 2(10) = 1; PAT 1 = {2};
Test auf P2 = 2010321041: negativ; Verschiebung: 1.
1 0 0 2 2 1 2 0 1 0 3 2 1 0 4 2 1 3 0 4 4 2 1 0
4. Versuch:
Hash 1(04) = 4; SHIFT 4 = 0; Hash 2(04) = 0; PAT 0 = 1;
Test auf P1 = 1032104: positiv; Verschiebung: 1.
Hash 1
SHIFT
0
6
1
3
2
6
3
4
4
0
R. Stiebe: Textalgorithmen, WS 2005/06
5
0
6
6
7
1
8
6
9
6
10
6
11
2
12
6
13
6
14
2
15
0
3
Wu-Manber-Algorithmus: Suche
1 0 0 2 2 1 2 0 1 0 3 2 1 0 4 2 1 3 0 4 4 2 1 0
5. Versuch:
Hash 1(42) = 6; SHIFT 6 = 6; Verschiebung: 6.
1 0 0 2 2 1 2 0 1 0 3 2 1 0 4 2 1 3 0 4 4 2 1 0
6. Versuch:
Hash 1(42) = 6; SHIFT 6 = 6; Verschiebung: 6. Schluss.
Hash 1
SHIFT
0
6
1
3
2
6
3
4
4
0
R. Stiebe: Textalgorithmen, WS 2005/06
5
0
6
6
7
1
8
6
9
6
10
6
11
2
12
6
13
6
14
2
15
0
4

Z-Algorithmus – Beispiel