Meine Explode-Funktion optimieren

[alzaimar]

Hier mal eine Version (eben schnell geschrieben), die auf einem stark vereinfachten String-Matching-Algorithmus von Boyer-Moore basiert. Anstatt die gefundene Position zurückzuliefern, wird der Text extrahiert und in eine TStringlist geschrieben

Delphi-Quellcode:

Procedure AlzExplode(Const aText, aPattern: String; aItems: TStrings);
(*-----------------------------------------------------------------------------
 * Spaltet Textteile in aText, die durch aPattern getrennt sind auf, und 
 * füllt die einzelnen Texte in aItems.
 * <del>abc<del>xyz => ('abc','xyz')
 * Basiert auf der QuickSearch-Implementierung von 
 * Christian Charras und Thierry Lecroq, Université de Rouen, 
 * 76821 Mont-Saint-Aignan Cedex
 * Frankreich
 *)
Var
  i0, i, k, n, m: Cardinal;
  c: Char;
  Skip: Array[Char] Of Integer;

Begin
  aitems.clear;
  m := Length(aPattern);
  If m = 0 Then Exit;
// Sprungtabelle für nicht übereinstimmende Zeichen erstellen
  For c := Low(Char) To High(Char) Do
    Skip[c] := m + 1;

  For i := 1 To m Do
    Skip[aPattern[i]] := m - i + 1;

  i := 1;
  i0 := 1;
  n := Length(aText);
  k := n - m + 1;
  While i <= k Do Begin
    If (aPattern[1] = aText[i]) And (aPattern[m] = aText[i + m - 1]) Then // <<--- von DJ-SPM 
      If CompareMem(@aText[i], @aPattern[1], m) Then Begin
        aItems.Add(Copy(aText, i0, i - i0));
        inc(i, m);
        i0 := i;
        Continue;
      End;
    inc(i, Skip[aText[i + m]]);
  End;

  If i0 <= n Then
    aItems.Add(Copy(aText, i0, n - i0 + 1));

End;

Interessant ist, das hier nicht jedes Zeichen des Textes geprüft wird. Wenn man z.B. nach 'ABC' sucht, und der 3.Buchstabe ist kein 'C', kann man ja gleich um 3 Zeichen nach vorne gehen. Je länger der Suchtext ist, desto besser die Performance. Natürlich kann man ihn reinlegen (aPattern = 'aaaaaaaa').

Sicherlich gibt es noch bessere Algorithmen (Boyer-Moore, Raita, etc.) aber der o.g. ist schön kompakt und wirklich flott.

Die Abfrage nach dem ersten und letzten Buchstaben des Patterns, vor dem eigentlichen CompareMem, ist von DJ-SPM übernommen. Das scheint enorm viel zu bringen.

Diese Version ist nochmal 50% schneller als die von DJ-SPM. Allerdings hatte ich nicht seine Original-Version genommen (die ja nicht ganz korrekt ist), sondern noch ein 'CompareMem' eingebaut.

Wer hat Lust, hier weiter zu optimieren? Derzeit ist es ja schon eine echte Gemeinschaftsarbeit von DJ-SPM und den Franzosen (ok, ein wenig auch von mir). Das wäre dann die ultimative Explode-Funktion...

Kleiner Nachtrag: Die Version schlägt die CodeLib-Version um den Faktor 1,5-16. Die CodeLib-Version degeneriert zudem bei kurzen SuchStrings (Delimiter bzw. Pattern).