Beim Arbeiten mit grossen Datenmengen ist das Suchen nach Texten z.B. Namen, Adressen etc. oft eine sehr zeitkritische Angelegenheit. Mit der herkömmlichen Suchmethode, sie sei hier als âSingle-Stepâ bezeichnet, lassen sich bei kleineren Dateien und einmaligem Suchen gute Ergebnisse erreichen. Werden die zu bearbeitenden Dateien jedoch sehr groĂ, oder soll nach mehreren Strings nacheinander gesucht werden, treten schnell lĂ€stige Wartezeiten auf. In diesem Artikel wird ein fĂŒr solche FĂ€lle geeigneter schneller Suchalgorithmus vorgestellt.
Dazu betrachten wir zuerst einmal die Standard-Single-Step-Methode. Die Situation ist folgende: die zu durchsuchende Datei steht in einem Speicherblock, dessen Anfangsadresse und LĂ€nge bekannt sind. Vom zu suchenden String sind ebenfalls die Startadresse und LĂ€nge bekannt.
Nun werden die Zeichen der Datei mit dem ersten Zeichen des Strings verglichen; stimmt ein Zeichen ĂŒberein, werden die aktuellen Adressen von Datei und String gesichert und in eine Schleife gesprungen, in der die nĂ€chsten Zeichen ĂŒberprĂŒft werden. Sind alle Zeichen bis zum String-Ende identisch, ist der String gefunden. Ist dies nicht der Fall, wird die Schleife verlassen und ab der aktuellen Dateiadresse+1 weitergesucht. Die Dateiadresse wird also immer in Einer-Schritten erhöht und das neue Zeichen mit dem ersten Zeichen des Strings verglichen.
Das folgende Schema verdeutlicht den Single-Step-Algorithmus: Gesucht wird das Wort spÀt in dem Satz Wer reitet so spÀt durch Nacht und Wind? (siehe Bild 1).
Die Grundidee des Boyer-Moore-Algorithmus ist, die Datei-Adresse in gröĂeren Schritten als 1 zu erhöhen; dadurch lĂ€Ăt sich die Suchgeschwindigkeit erheblich steigern. Damit dabei der zu suchende Text nicht ĂŒbersprungen wird, findet vorher dessen Analyse statt. Dazu wird ein Feld (bzw. Speicherblock) angelegt, das 256 Elemente von jeweils 1 Byte LĂ€nge enthĂ€lt. Die Position eines Elements (0-255) entspricht dem ASCII-Code eines Zeichens. Dieses Feld fĂŒllt man im ersten Durchgang mit der LĂ€nge des gesuchten Strings. Hierzu darf die LĂ€nge max. 255 Zeichen betragen. was aber fĂŒr Bearbeitung von Texten ausreichen dĂŒrfte. Im zweiten Durchgang werden die einzelnen Zeichen des Strings von rechts (d.h. von hinten) gelesen und ihr Offset zum String-Ende in das dazugehörige Feldelement eingetragen. Bevor die Eintragung erfolgt, muĂ man noch ĂŒberprĂŒfen. ob das Feldelement bereits belegt ist, d.h. ob dort ein Wert steht, der ungleich der String-LĂ€nge ist. Dieser Fall tritt dann auf, wenn ein Zeichen im String mehrfach vorhanden ist; die Eintragung wird dann ausgelassen. Jetzt kann die eigentliche Suche beginnen. Zur Datei-Anfangs-Adresse wird die String-LĂ€nge-1 addiert, und das Zeichen an dieser Adresse wird mit dem letzten Zeichen des Strings verglichen. Sind die Zeichen verschieden, findet der ASCII-Code des Zeichens aus der Datei als Feld-Offset Verwendung. Der Wert wird aus dem entsprechenden Feldelement geholt und die Datei-Adresse um diesen Wert erhöht. Stimmen die Zeichen dagegen ĂŒberein, werden die aktuellen Adressen von String und Datei gesichert und in eine Schleife gesprungen, die die nĂ€chsten Zeichen zur linken Seite mit denen des gesuchten Textes vergleicht. In dieser Schleife kommt der Single-Step-Algorithmus zur Anwendung, allerdings erfolgt der Vergleich von rechts nach links, also rĂŒckwĂ€rts durch String und Datei.
Zur Verdeutlichung wieder das Schema. Das Feld enthÀlt die Verschiebe-Werte (siehe Bild 2).
Alle anderen Feldelemente erhalten den Verschiebe-Wert 4, da der String spÀt eine LÀnge von 4 hat (siehe Bild 3).
Beim Durchgang 2 wird der Buchstabe t als Ăbereinstimmung festgestellt. Dann erfolgt der Single-Step-Vergleich (rĂŒckwĂ€rts); das nĂ€chste Zeichen i stimmt nicht mehr ĂŒberein. Da zuletzt ein Einzelschritt erfolgte, darf die Datei-Adresse jetzt auch nur um 1 erhöht werden.
GegenĂŒber dem Single-Step-Algorithmus, bei dem 14 DurchgĂ€nge erforderlich waren, sind beim Boyer-Moore-Algorithmus nur 6 DurchgĂ€nge nötig - der Geschwindigkeitsvorteil ist offensichtlich.
Damit man die Geschwindigkeit auch richtig genieĂen kann, habe ich die auf dem Boyer-Moore-Algorithmus basierende Routine in Assembler geschrieben. Das hat auĂerdem den Vorteil, daĂ alle Programmierer davon profitieren, da Assembler-Einbindungen ja in (fast) allen Hochsprachen möglich sind. Zum Vergleich habe ich auch den einfachen Single-Step-Algorithmus programmiert. Beide Programme erwarten die ParameterĂŒbergabe ĂŒber den Stack und sollten deshalb ohne Ănderungen als Unterprogramme in die meisten Hochsprachen eingebunden werden können. Ăbergeben werden Pointer auf Dateianfang, Such-String und 256 Bytes Puffer sowie die LĂ€ngen von String und Datei; zurĂŒckgegeben wird die relative Position des Such-Strings zum Dateianfang oder -1, wenn der String in der Datei nicht gefunden wurde.
Zum Testen der Geschwindigkeit und zur Demonstration dient das Programm in GFA-BASIC. Dort wird ein 100 kB groĂer Speicherblock reserviert, der im folgenden eine geladene Textdatei darstellen soll. Dieser Bereich wird in einer Schleife mit dem gesuchten String OHNE das letzte Zeichen gefĂŒllt. Am Ende dieses Blocks steht dann (endlich!) der komplette zu suchende String. Diese Anordnung dĂŒrfte zum Suchen eines Strings so ziemlich die gemeinste sein (oder hat jemand noch eine fiesere Idee?). So, und jetzt kommen die Benchmarks (siehe Bild4)!
Erstaunlich ist auf den ersten Blick wohl die Tatsache, daĂ mit zunehmender LĂ€nge des Such-Strings die benötigte Zeit immer geringer wird. Aber das wird sofort klar, wenn man bedenkt, daĂ alle Zeichen, die nicht im String enthalten sind, die Datei-Adresse sofort um die komplette String-LĂ€nge erhöhen und damit die Suchroutine in groĂen Schritten durch die Datei springt. Dadurch wird im ersten Fall der Benchmarks eine Geschwindigkeitssteigerung um den Faktor 30 !!! erreicht. Aber auch bei kĂŒrzeren Strings kann sich die Suchzeit immer noch sehen lassen. Anhand dieser Benchmarks zeigt sich mal wieder, daĂ die Optimierung eines Programms auf Algorithmenebene in den meisten FĂ€llen einer Optimierung auf Befehlsebene ĂŒberlegen ist. Wie andere Algorithmen hat auch dieser seine SchwĂ€chen. Sucht man z.B. den String 01111111 in einer Datei, die nur Einsen enthĂ€lt (11111111), ist die Boyer-Moore- langsamer als die Single-Step-Methode, da die Datei-Adresse immer nur in Einzelschritten erhöht werden kann. Dieser Fall dĂŒrfte aber bei normalen Texten wohl kaum auftreten, so daĂ der Algorithmus fĂŒr diese Anwendung uneingeschrĂ€nkt empfohlen werden kann.
Durchgang Wer reitet so spÀt durch Nacht und Wind? Schritte
|||||||||||||||||
1 s|||||||||||||||| +1
2 s||||||||||||||| +1
3 s|||||||||||||| +1
4 s||||||||||||| +1
5 s|||||||||||| +1
6 s||||||||||| +1
7 s|||||||||| +1
8 s||||||||| +1
9 s|||||||| +1
10 s||||||| +1
11 s|||||| +1
12 sp|||| +1
13 s|||| +1
14 spÀt -> gefunden
Bild 1: Der Single-Step-Algorithmus
Zeichen ASCII-Wert Verschiebe-Wert
s 115 3
p 112 2
Ă€ 132 1
t 116 0
Bild 2.
Durchgang Wer reitet so spÀt durch Nacht und Wind? Schritte
| || | ||
1 spÀt || | || +4
2 spÀt| | || +1
3 spÀt | || +4
4 spÀt || +4
5 spÀt| +1
6 spÀt -> gefunden
Bild 3: So gehtâs mit der neuen Routine.
benötigte Zeit mit
Gesuchter String 'Single-Step' 'Boyer-Moore'
âWer reitet so spĂ€t durch Nacht und Wind ?" 0.905 s 0.030 s
âWer reitet so spĂ€t ?" 0.880 s 0.055 s
âWer reitet ?" 0.885 s 0.085 s
âWer ?" 0.890 s 0.210 s
Bild 4: Einige Benchmarks veranschaulichen, wie schnell es sein kann.
' ************************************************
' * 'Single-Step'- und 'Boyer-Moore'-Algorithmus *
' * zur Stringsuche *
' * Autor: Andreas Hollmann, Paderborn *
' * (c) MAXON Computer GmbH *
' * Sprache: GFA-Basic *
' ************************************************
RESERVE 16000 !16 kB sind genug
IF MALLOC(-1)>=128000 THEN !genug Platz ?
p_file%=MALLOC(128000) !RAM fĂŒr skew-buffer und file
p_buf%=p_file%+120000 !ab hier steht der skew-buffer
ELSE
PRINT AT(1,1);"Nicht genug Speicher frei !"
END
ENDIF
define_inl !Adressen der INLINEs holen
! ------------------------------------------------
search$="Wer reitet so spÀt durch Nacht und Wind ?" ! zu suchender String
search_len&=LEN(search$) ! StringlÀnge holen
search_cut$=LEFT$(search$,search_len&-1) ! String ohne letztes Zeichen
' 100 kB mit dem String ohne das letzte Zeichen fĂŒllen (ui, wie gemein...):
FOR adr%=p_file% TO p_file%+99999 STEP search_len&
CHAR{adr%}=search_cut$
NEXT adr%
' Ab der relativen Adresse 100000 steht endlich dann der gesuchte String:
CHAR{p_file%+100000{=search$
' jetzt kann die Zeit gemessen werden:
t1%=TIMER !Anfangszeit merken
' get_pos1(p_file%,100000,search$,pos%) !'Single-Step' oder
get_pos2(p_file%,100000,search$,p_buf%,pos%) !'Boyer-Moore' auswÀhlen
t2%=TIMER !Endzeit merken
PRINT AT(1,1);"Position: ";pos%,"Zeit: (t2%-t1%)/200;" s"
! ------------------------------------------------
~MFREE(p_file%) !Speicher an GEMDOS zurĂŒckgeben
RESERVE
END
' ================================================
PROCEDURE define_inl
' hier stehen die INLINE-Blöcke mit den Assembler-Routinen
' die Adressen sind GLOBAL !
INLINE p_sng_step_inl%,64
INLINE p_bo_moore_inl%,140
RETURN
! ------------------------------------------------
PROCEDURE get_pos1(p_file%,file_len%,search$,VAR pos%) ! Single-Step
' Stringsuche mit dem âSingle-Step'-Algorithmus:
LOCAL search_len&,p_search%
search_len&=LEN(search$) !LĂ€nge des Strings
p_search%=LONG{ARRPTR(search$)} !Pointer auf gesuchten String holen
pos%=C:p_sng_step_inl%(L:p_file%,L:file_len%,L:p_search%,W:search_len&)
RETURN
! ------------------------------------------------
PROCEDURE get_pos2(p_file%,file_len%,search$,p_buf%,VAR pos%) ! Boyer-Moore
' Stringsuche mit dem 'Boyer-Moore'-Algorithmus:
LOCAL search_len&,p_search%
search_len&=LEN(search$) !LĂ€nge des Strings
p_search%=LONG{ARRPTR(search$)} âPointer auf gesuchten String holen
pos%=C:p_bo_moore_inl%(L:p_file%,L:file_len%,L:p_search%,W:search_len&,L:p_buf%)
RETURN
Listing 1: Das Steuerprogramm in GFA-BASIC
;************************************************
;* 'Boyer-Moore'-Algorithmus zur String-Suche *
;* Autor: Andreas Hollmann, Paderborn *
;* (c) MAXON Computer GmbH 1990 *
;* Sprache: Assembler *
;************************************************
; Aufruf: pos%=C:adr%(L:p_file,L:file_len%,L:p_search%,W:search_len&,L:p_buf%)
; Stack-Offset: 4 8 12 16 18
;
; Parameter:
; p_file% = Pointer auf den zu durchsuchenden Speicherbereich
; file_len% = LĂ€nge des zu durchsuchenden Speicherbereichs
; p_search% = Pointer auf den zu suchenden Stng
; search_len& = LĂ€nge des auszugebenden Strings
; p_buf% = Pointer auf 256 Byte shift-buffer
; pos% = Position des Strings relativ zum Dateianfang
;-----------------------------------------------
move.w 16(sp),d7 ;StringlÀnge
;steht in d7
;shift-buffer mit StringlĂ€nge fĂŒllen:
movea.l 18(sp),a0 ;Pointer auf 256 Byte shift-buffer laden
move.w #255,d0 ;256 Byte mit StringlĂ€nge fĂŒllen
fill_buf: move.b d7,(a0)+ ;StringlÀnge eintragen
dbra d0,fill_buf ;bis zum End
;des shift-buffers
;String von rechts nach links scannen und Verschiebe-Werte eintragen:
movea.l 12(sp),a0 ;Pointer auf String laden
adda.w d7,a0 ;auf Stringende 'ASCII 0' setzen
movea.l 18(sp),a1 ;Pointer auf 256 Byte shift-buffer laden
moveq #0,d6 ;RĂŒckwĂ€rts-ZĂ€hler auf Position 0 setzen
shift_loop: move.b -(a0),d0 ;Zeichen laden
ext.w d0 ;auf Wortbreite erweitern
cmp.b 0(a1,d0.w),d7 ;shift-buffer-Position schon belegt?
bne.s inc_count ;ja: keinen Verschiebe-Wert eintragen
move.b d6,0(a1,d0.w) ;nein: Verschiebe-Wert eintragen
inc_count: addq.w #1,d6 ;RĂŒckwĂ€rtszĂ€hler inkrementieren
cmp.w d6,d7 ;Stringende erreicht?
bhi.s shift_loop ;immanonich ? -> weitershiften
;der shift-buffer ist jetzt mit den Verschiebe-
;Werten gefĂŒllt.
;jetzt gehts mit der eigentlichen Stringsuche los
movea.l 4(sp),a0 ;Pointer auf Datei-Anfang laden
move.l 8(sp),d6 ;Datei-LĂ€nge laden
lea -1(a0,d7.w),a0 ;Pointer auf letztes Zeichen setzen
movea.l 12(sp),a2 ;Pointer auf String-Anfang laden
lea -1(a2,d7.w),a2 ;Pointer auf letztes Zeichen setzen
movea.l 18(sp),a3 ;Pointer
;auf shift-buffer laden
cmp_loop: move.b (a0),d0 ;Zeichen aus Datei laden
move.b (a2),d1 ;Zeichen aus String laden
cmp.b d0,d1 ;beide Zeichen vergleichen
beq.s cmp_back ;Zeichen stimmen ĂŒberein -> ...hops...
ext.w d1 ;Zeichen stimmen nicht ĂŒberein (schade)
move.b 0(a3,d0.w),d1 ;entsprechenden shift-Wert laden
ext.w d1
adda.w d1,a0 ;Datei-Pointer um shift-Wert erhöhen
sub.l d1,d6 ;DateilÀngen-ZÀhler vermindern
bpl.s cmp_loop ;bis Dateiende weitersuchen!
moveq #-1,d0 ;String nicht in der Datei enthalten!
rts ;back to life...
;-----------------------------------------------
;String im RĂŒckwĂ€rtsgang untersuchen:
cmp_back: move.w d7,d5 ;LĂ€nge des Strings laden
subq.w #2,d5 ;wegen 'dbra' und predekrement
movea.l a0,a4 ;aktuelle Adressen sichern
movea.l a2,a5 ; "
cmp_b_loop: move.b -(a4),d0 ;nÀchstes Zeichen aus Datei laden
move.b -(a5),d1 ;nÀchstes Zeichen aus String laden
cmp.b d0,d1 ;sind beide Zeichen gleich?
beq.s continue ;Jawoll Herr Kaleu ! -> weitermachen
lea 1(a0),a0 ;sonst: Datei-Pointer inkrementieren...
bra.s cmp_loop ;...und zurĂŒckspringen
continue: dbra d5,cmp_b_loop ;aktuelle String-Position dekrementieren
cmpi.w #-1,d5 ;komplette Ăbereinstimmung der Strings?
bne.s cmp_loop ;zurĂŒck und weitersuchen
;Der String ist gefunden worden !
move.l a4,d0 ;absolute Position des Strings
sub.l 4(sp),d0 ;-Dateianfang = relative Position
rts ;relative Position zurĂŒckgeben
;-----------------------------------------------
END
Listing 2: Der Boyer-Moore-AIgorithmus in Assembler
;************************************************
;* 'Single-Step'-Algorithmus zur String-Suche *
;* Autor: Andreas Hollmann, Paderborn *
;* (c) MAXON Computer GmbH *
;* Sprache: Assembler *
;************************************************
; Aufruf: pos%=C:adr%(L:p_file,L:file_len%,L:p_search%,W:search_len&)
; Stack-Offset: 4 8 12 16
;
; Parameter:
; p_file% = Pointer auf den zu durchsuchenden Speicherbereich/Datei
; file_len% = LĂ€nge des zu durchsuchenden Speicherbereichs/Datei
; p_search% = Pointer auf zu suchenden String
; search_len& = LĂ€nge des zu suchenden Strings
; pos% = Position des Strings relativ zum Dateianfang
;-----------------------------------------------
movea.l 4(sp),a0 ;Pointer auf Datei laden
move.l 8(sp),d6 ;DateilÀnge laden
movea.l 12(sp),a2 ;Pointer auf String laden
move.w 16(sp),d7 ;StrglÀnge laden
subq.w #1,d7 ;...und dekrementieren
move.b (a2),d0 ;1.Zeichen des Strings laden
main_loop: cmp.b (a0)+,d0 ;mit Zeichen aus der Datei vergleichen
beq.s found1 ;1.Zeichen gefunden
subq.l #1,d6 ;ZĂ€hler fĂŒr DateilĂ€nge dekrementieren
bpl.s main_loop ;bis zum Dateiende suchen
moveq #-1,d0 ;String nicht in der Datei enthalten!
rts
;-----------------------------------------------
found1: movea.l a0,a3 ;aktuelle Datei-Adresse sichern
lea -1(a3),a3 ;wegen postinkrement
movea.l a2,a4 ;aktuelle String-Adresse sichern
move.w d7,d5 ;StringlÀnge kopieren
subq.l #1,d6 ;ZĂ€hler fĂŒr DateilĂ€nge dekrementieren
sub_loop: cmpm.b (a3)+,(a4)+ ;die beiden nÀchsten Zeichen vergleichen
bne.s main_loop ;ungleich, -> zurĂŒck und weitersuchen
dbra d5,sub_loop
lea -1(a0),a0 ;-1 wegen predekrement in
cmp_loop1
move.l a0,d0 ;absolute Position des Strings
sub.l 4(sp),d0 ;-Dateianfang = relative Position
rts
;-----------------------------------------------
END
Listing 3: So wird normalerweise gesucht