1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
| Boyer-Moore (Suche)
Dieser Algorithmus ist besonders schön, da er sehr wenig Vergleiche braucht
und damit extrem schnell ist.
Der Witz an ihm ist, ist daß wir nicht mehr jeden Buchstaben einzeln ver-
gleichen, sondern wortweise immer nur den letzten Buchstaben. Man spart sich
so einiges an IFs bzw. CMPs.
Aber am besten versteht man ihn wohl an einem Beispiel.
Unser Text, in dem wir einen String suchen wollen, waere dieser Satz (<g>).
Und darin suchen wir nun das Wort "String".
Der Trick ist nun, daß wir uns ein 256-Char (Byte) großes Array anlegen und
es mit der Länge des Wortes (6) initialisieren. Anschließend gehen wir nun
unseren Suchstring durch und schreiben an die Stelle im Array, dessen ASCII-
Wert dem Zeichen entspricht, die Zahl (Länge-Pos) rein, wobei Pos die Posi-
tion des Zeichens in unserem Suchstring ist und bei 1 beginnt.
Der ASCII-Wert von 'S' ist 83. Also schreiben wir bei Array[83] (6-1) rein.
't' wäre 116. Also kommt bei Array[116] (6-2) hinein ... und schließlich bei
'g': Array[103] (6-6).
Jetzt fangen wir beim 6. Zeichen (nicht beim ersten) an und vergleichen es
mit dem letzten (6.) Zeichen des Suchstrings.
' ' == 'g' ? Nicht wahr!
Also nehmen wir array[' '] und addieren es auf unseren Zähler (der uns das
Vergleichs-Char im Suchtext anzeigt) drauf.
' ' == 'g' ? s.o.
'm' == 'g' ? s.o.
'e' == 'g' ? s.o.
'S' == 'g' ? Nicht wahr, s.o.
Es fällt aber auf, daß wir nicht mehr 6 weitergehen, sondern dieses Mal nur
5 Schritte (Array['S'] = 6-1).
'g'=='g' ? Jo.
Nun triumphieren wir nicht gleich, sondern gehen mit Zeiger eins zurück und
vergleichen, ob dort auch ein 'n' steht, wie wir es erwarten. Trifft zu. Und
so weiter mit i,r,t,S. Falls das letzte auch richtig ist, haben wir unseren
String gefunden.
Das Ganze nochmal etwas visueller:
Unser' 'Text, in dem wir einen String suchen wollen, waere dieser Satz (<g>).
Strin'g'
Unser Text,' 'in dem wir einen String suchen wollen, waere dieser Satz (<g>).
Strin'g'
Unser Text, in de'm' wir einen String suchen wollen, waere dieser Satz (<g>).
Strin'g'
Unser Text, in dem wir 'e'inen String suchen wollen, waere dieser Satz (<g>).
Strin'g'
Unser Text, in dem wir einen 'S'tring suchen wollen, waere dieser Satz (<g>).
Strin'g'
Unser Text, in dem wir einen Strin'g' suchen wollen, waere dieser Satz (<g>).
Strin'g'
Unser Text, in dem wir einen Stri'n'g suchen wollen, waere dieser Satz (<g>).
Stri'n'g
.
.
.
Unser Text, in dem wir einen 'S'tring suchen wollen, waere dieser Satz (<g>).
'S'tring
fertig.
Was wäre, wenn da ein 'g' schon vorher im Satz gewesen wäre? Dann hätte er
den vorherigen Buchstaben mit dem 'n' verglichen. Wäre wohl fehlgeschlagen.
Er würde um 6-Pos(n)+1 weitergehen und weiterfahren.
Was wäre, wenn zwei gleiche Buchstaben im Suchstring vorkommen? Also wenn
wir "essen" suchen. Was schreiben wir bei Array['e'] rein? Auf jeden Fall
den kleineren Wert, also das 'e' möglichst weit am Ende des Wortes, in die-
sem Fall also eine 5-4=1 und nicht eine 5-1=4 !
Nun der Algorithmus in einer C-Umsetzung. Bei mir schafft dieser ein Mbyte
Text in einer Sekunde nach einem beliebigen Text zu durchsuchen (wird etwas
langsamer, je größer der Suchstring, da ja dann mehr Doppelbuchstaben vor-
kommen) auf einem 486DX40.
search : Suchstring
text : Suchtext
chars : Ist das Array mit Sprüngen aus len-Pos(em)
len : Länge des Suchstrings
em : Ist der "Zeiger" auf unser Suchstringfeld
i : Ist der "Zeiger" auf unser Suchtextfeld
stelle : Merkt sich bei Treffer ('g'=='g'), wo wir waren, um später an die
Stelle zurückgehen zu können und so leichter weiterzukommen. Ist im
Prinzip unnötig. S.o.: len-pos+1 tut es auch.
groesse: Ist die Größe von text
{
printf("Suchstring: ");
scanf("%s",search);
len=strlen(search);
em=len-1; /* zeigt auf unser Sucharray /*
for(l=0;l<256;l++)
chars[l]=len;
for(l=0;l<len;l++)
chars[(unsigned char)(search[l])]=em-l;
i=em; /* zeigt auf unseren Suchtext */
do
{
if (search[em]!=text[i])
{
i+=chars[(unsigned char)text[i]];
if (em<len-1)
i=stelle+1;
em=len-1;
}
else
{
if (em==0)
printf("Suchstring gefunden !");
else
{
if (em==len-1)
stelle=i;
em--;
i--;
}
}
} while (i<groesse);
}
Sehen wir uns den Code mal an.
1. Suchstring abfragen
2. Länge bestimmen und Zeiger setzen
3. Das Array mit den Sprüngen einsetzen (man sieht, daß man sich bei zwei-
malig vorkommendem 'e' keine Sorgen machen muß, da die alte Position au-
tomatisch von der möglichst nahe bei len liegenden überschrieben wird).
4. i auf Länge des Suchstrings und los geht der Spass.
5. Ist es gleich? Wenn nicht, erhöhen wir i um die Zahl aus dem Sprungarray
(Der Rest ist zur Rückstellung, falls wir vorher auf ein 'g' trafen, der
Buchstabe davor aber kein 'n' war ... <g>)
6. Falls es gleich ist, dann schauen wir, ob wir schon beim ersten Buchsta-
ben des Suchstrings und damit am Ende angekommen sind. Falls nicht, wird
em dekrementiert (Stichwort: nicht nur 'g'=='g', sondern auch 'n'=='n',
usw.). Außerdem merken wir uns die Stelle des 'g', damit wir später ein-
facher weiterspringen können.
7. und zu 5, falls wir noch nicht am Ende des Sucharrays sind. |
)
Gausi