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
Aus: ST-Computer 12 / 1990, Seite 74

Links

Copyright-Bestimmungen: siehe Über diese Seite