Schnellster Stringmatching-Algorithmus in ASM übersetzen

[alzaimar]

Hi ASM profis,

Ich habe hier einen wirklich schnellen Stringmatching-Algorithmus (also, sowas wie 'POS'), der aber wesentlich schneller als POS ist (2-20x).

Ich möchte gerne testen, ob dieser Algorithmus in Assembler noch (und vor allen Dingen, um wieviel) schneller ist. Er ist relativ simpel. Er basiert auf dem QuickSearch-Algorithmus von Daniel Sunday, mit einer Optimierung von mir. Diese wurde von Timo Raita (University of Turku) angeregt. Seine Arbeit behandelt diese Optimierung im Rahmen des Boyer-Moore Algorithmus.

Hier der Algorithmus. Er verwendet eine Sprungtabelle, die pro Substring nur einmal angelegt werden muss. Dieses Optimierungspotential interessiert mich aber jetzt nicht...

Hier der Algorithmus;

Delphi-Quellcode:

Function QSSearch(Const sSubStr, sText: String): Integer;
Var
  j, i, k, iTextLength: Cardinal;
  n, n1, n2: Cardinal;
  c1, cp: Char;
  Skip: Array[Char] Of Cardinal;
  c: Char;
  pPtr: Pointer;

Begin
  n := Length(sSubStr);
  c1 := sSubStr[1];
  cp := sSubStr[n];
  n1 := n - 1;
  n2 := n - 2;
  pPtr := @sSubStr[2];

  For c := Low(Char) To High(Char) Do
    Skip[c] := n + 1;
  For i := 1 To n Do
    Skip[sSubStr[i]] := n - i + 1;

  i := 1;
  j := 1;
  iTextLength := Length(sText);
  k := iTextLength - n + 1;
  While i < k Do Begin // Bei PChar: i <= k
    If (c1 = sText[i]) And (cp = sText[i + n1]) Then
      If (n < 3) Or CompareMem(@sText[i + 1], pPtr, n2) Then Begin
        Result := i;
        Exit;
      End;
    inc(i, Skip[sText[i + n]]); // Bei PChar und i=k ist sText[i+n] = #0, bei Strings erfolgt ein Überlauf
  End;

// Wegen o.g. Kommentare (PChar vs. String) Muss man hier eine extra Abfrage einbauen, ob
// der String nicht ganz am Ende auftaucht...
  Result := 0;
  If i = k Then
    If (c1 = sText[i]) And (cp = sText[i + n1]) Then
      If (n < 3) Or CompareMem(@sText[i + 1], pPtr, n2) Then
        Result := i;
End;

Im Prinzip geht es darum: Sei ABCDE (=T) mein Text, und ich suche nach 'CDE' (=S)
Ich fange an, und vergleiche die letze Stelle von S mit der 3.Stelle von T (weil len(S)=3). Wenn die beiden ungleich sin, und T[3] gar nicht in S vorkommt, kann ich gleich 3(!) Stellen nach rechts hüpfen. Kommt T[3] in S vor, dann entsprechend weniger. Das wird durch die 'Skip'-Tabelle festgelegt. Wenn die beiden Zeichen jedoch gleich sind, vergleiche ich T[1] mit S[1]. Stimmt das auch, vergleiche ich den Rest (das ist übrigens die Optimierung von Timo Raita: Kleine Ursache, riesen Wirkung)

Je länger der zu suchende Text, desto schneller (im Mittel) der Algorithmus.

Man kann natürlich noch die Startposition mit übergeben (das wäre dann die Zeile mit dem '***')

Ach, er klappt sowieso nur für Suchstrings mit mehr als einem Zeichen...

Also, hat Jemand Bock, das Teil in ASM zu übersetzen (oder sonstwie schneller zu machen)? Haben ja schließlich alle was davon....

Bin mal gespannt....

[Edit]Fehlerhafte Version rausgeschmissen. Kommt davon, wenn man aus einer PChar in Strings umwandelt und ungenügend testet...[/edit]

[edit]
hier der Code von Sunday aus Charras & Lecroq

Code:

void preQsBc(char *x, int m, int qsBc[]) {
   int i;

   for (i = 0; i < ASIZE; ++i)
      qsBc[i] = m + 1;
   for (i = 0; i < m; ++i)
      qsBc[x[i]] = m - i;
}


void QS(char *x, int m, char *y, int n) {
   int j, qsBc[ASIZE];

   /* Preprocessing */
   preQsBc(x, m, qsBc);
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      if (memcmp(x, y + j, m) == 0)
         OUTPUT(j);
      j += qsBc[y[j + m]];               /* shift */
   }
}

[/edit]