← ST-Computer 12 / 1990

Boyer-Moore: Schneller Algorithmus zur String-Suche

Programmierpraxis

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