Boyer-Moore: Schneller Algorithmus zur String-Suche
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
Andreas Hollmann