Boyer Moore Algorithmus

[Horst_]

Hallo,

ich habe mal himitsu's Version geändert, welche bei mir nicht übel abschneidet.

Delphi-Quellcode:

function CountString(const S, SubStr: string): integer; assembler;
// Leicht geändert, zählt nicht nur bis 65536
// Siehe www.delphipraxis.net/51284-teil-string-anderem-string-suchen-zaehlen.html
asm
         PUSH    ESI
         PUSH    EDI
         PUSH    EBX
         TEST    EAX, EAX
         JE      @Exit          // S nicht vorhanden
         TEST    EDX, EDX
         JE      @Exit0         // SubString nicht vorhanden
         MOV     ESI, EDX       // EDI Adresse SubString
         MOV     EDI, EAX       // EDI Adresse S

         MOV     ECX, [EDI - 4] // Laenge S
         MOV     EDX, [ESI - 4] // Laenge SubString
         DEC     EDX            // Restlaenge des Substrings, die untersucht werden muss
         JS      @Exit0         // Substring hatte Laenge = 0

         MOV     AL, [ESI]      // Erstes Zeichen des Substrings nach dem gesucht wird
         INC     ESI            // Startpos fuer dahinter weiter vergleichen
         SUB     ECX, EDX       // Differenz der Laengen
         JLE     @Exit0         // Substring laenger als S -> und tschuesz

         MOV     EBX, ECX
         PUSH    Dword 0        // Anzahl Vorkommen auf dem Stack an [ESP]
         @Loop:
         MOV     ECX, EBX
         REPNE   SCASB          // Suche erste Zeichen
         JNE     @Ready           // Suche abgeschlossen
         MOV     EBX, ECX       // Position merken
         PUSH    ESI             // Merken für den naechsten Such-Durchgang
         PUSH    EDI
         MOV     ECX, EDX       // Die noch zu vergleichende Anzahl
         REPE    CMPSB          // Vergleich des Restes des Substrings ab dort
         POP     EDI
         POP     ESI
         JNE     @Loop
         INC     [ESP]          //erhoehe Anzahl Vorkommen
         JMP     @Loop

         @Exit0:
         MOV     EAX,0
         JMP     @Exit
         @Ready:
         POP     EAX
         @Exit:
         POP     EBX
         POP     EDI
         POP     ESI
end;

Der Suchtext besteht aus 100000 Zeilen.Gesamtlänge 6.2 Mio Zeichen

Code:

"Taxi"
Asm        Count: 100000 in 544ms
BMH Count:        100000 in 321ms
SP Search Count: 100000 in 564ms
Std PosEx Count: 100000 in 340ms
himitsu Count:    100000 in 280ms   <---

" Taxi" // Ein häufiger Buchstabe vorne
Asm        Count: 100000 in 819ms
BMH Count:        100000 in 284ms <---
SP Search Count: 100000 in 544ms
Std PosEx Count: 100000 in 1021ms
himitsu Count:    100000 in 745ms

"XTaxi"  // Ein nicht vorhandener Buchstabe vorne
Asm        Count: 0 in 519ms
BMH Count:        0 in 244ms
SP Search Count: 0 in 471ms
Std PosEx Count: 0 in 212ms
himitsu Count:    0 in 210ms        <--

// Die fast längste Zeile #13#10 fehlt
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern."
Asm        Count: 100000 in 396ms  <---
BMH Count:        100000 in 534ms
SP Search Count: 100000 in 806ms
Std PosEx Count: 100000 in 453ms
himitsu Count:    100000 in 482ms

//Ein nicht vorhandener Buchstabe am Ende eines langen Textes
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern.X" 
Asm        Count: 0 in 1189ms
BMH Count:        0 in 69ms <--- auch nur 89 Mb/s
SP Search Count: 0 in 340ms
Std PosEx Count: 0 in 440ms
himitsu Count:    0 in 484ms

Gruß Horst