4.2 Verfahren von Knuth, Morris und Pratt

Bei der brute force-Methode muß man beim Auftreten eines Unterschieds wie eben beschrieben die Suche ein Zeichen hinter dem letzten Startpunkt im Text fortsetzen, weil man sonst möglicherweise ein Vorkommen des Musters übersieht.

Das ist bedauerlich, weil dadurch viele Zeichen aus text mehrfach betrachtet werden müssen.

Je nach Aufbau des Musters kann man allerdings auch weiter springen, bevor man mit erneutem Vergleichen beginnt, und spart sich dadurch einen Teil der Vergleiche.

Beispiel: falls das Muster folgenden Inhalt hat:
muster [0] [1] [2] [3] [4]
a b b b c

, dann kann bei einem bei c festgestellten Unterschied an der Musterposition [4] die Suche gleich an der aktuellen Stelle im Text fortgeführt werden; denn ein Vorkommen des Musters muß mit einem a beginnen; weil aber im Muster nach dem Anfang kein a mehr enthalten ist und bis zu muster[3] alle Zeichen übereinstimmten, kann im Text kein a stehen, soweit er bereits mit muster[1] bis muster[3] verglichen wurde.

Ist dagegen das Muster:
muster [0] [1] [2] [3] [4] [5]
a b c a b b

, und wird ein Unterschied an der Stelle des muster[5] festgestellt, dann kann die Suche an der Stelle im Text neu aufgesetzt werden, die mit dem zweiten a verglichen wurde (denn dort könnte das mit a beginnende Muster theoretisch neu starten).

Anstatt also die Suche jeweils beim Zeichen hinter dem letzten Start neu aufzusetzen, dürfte man unter Umständen auch gleich etwas weiter springen; wie weit hängt erstens vom Muster ab, und zweitens von der erreichten Position im Muster bis zum letzten Abbruch.

Diese Erkenntnis führt zu dem Verfahren von Knuth, Morris und Pratt.

Hier wird vor der eigentlichen Suche ein zusätzliches Feld geschaffen, anhand dessen zu jeder möglichen Abbruchposition eine erlaubte Sprungweite hinterlegt wird. Dieses Feld wird für jede Suche aufgrund des Musters einmal bestimmt; bei längeren Texten geht diese Vorabberechnung also nicht in die Laufzeit mit ein.

An jeder Position ist angegeben, wie viele Elemente vor dem aktuellen mit dem Stringanfang übereinstimmen (abgesehen davon, daß die unterste Sprungweite immer mit -1 eingetragen wird).

/* Time-stamp: "20.06.02 17:39 demo.c klaus@lap2.wachtler.de"
 *
 */

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>

/* liefert einen Index zurück, der die relative Position
 * von muster in text angibt (falls Muster in text enthalten ist);
 * sonst -1.
 * Die Länge von text ist n; die Länge von muster ist m.
 */

void init_sprweite( char muster[], int sprweite[], int m )
{
  int  i, j;
  sprweite[0] = -1;
  for( (i=0), (j=-1); i<m; i++, j++,  sprweite[i]=j)
  {
    while( (j>=0) && (muster[i]!=muster[j]) )
    {
      j = sprweite[j];
    }
  }
}


int sucheteilfeld_kmp( char text[], int n,
                       char muster[], int sprweite[], int m
                       )
{
  int index_text, index_muster;

  init_sprweite( muster, sprweite, m );

  for( (index_text=0), (index_muster=0);
       index_muster<m && index_text<n;
       index_text++, index_muster++
       )
  {
    while( index_muster>=0 && text[index_text]!=muster[index_muster] )
    {
      index_muster = sprweite[index_muster];
    }
  }

  if( index_muster==m )
  {
    return index_text - m;
  }
  else
  {
    return -1;
  }
}

int main( int nargs, char **args )
{
//  char text[] =
//  {
//    'e', 'h', 'n', 'e', ' ',
//    'm', 'e', 'h', 'm', 'e', 'm', 'm', 'e', 'h', 'm', 'e', 'm', 'a', ' ',
//    'm', 'u', 'h'
//  };
//
//  char  muster[] =
//  {
//    'm', 'e', 'h', 'm', 'e', 'm', 'm', 'e', 'h', 'm', 'e', 'm', 'a', ' ',
///* zugehörige Sprungweiten: */
///*   -1,   0,   0,   0,   1,   2,   1,   1,   2,   3,   4,   5,   6,   0,  0 */
//
//  };

//  char text[] =
//  {
//    'z', 'a', 'b', 'z', 'a', 'z', 'a',
//  };
//
//  char  muster[] =
//  {
//    'z', 'a', 'z', 'a',
///* zugehörige Sprungweiten: */
///*  -1,   0,   0,   1,   2  */
//
//  };

  char text[] =
  {
    'z', 'a', 'z', 'z', 'a', 'z', 'a',
  };

  char  muster[] =
  {
    'z', 'a', 'z', 'a',
/* zugehörige Sprungweiten: */
/*  -1,   0,   0,   1,   2  */

  };

  const int laenge_text = sizeof(text)/sizeof(text[0]);
  const int laenge_muster = sizeof(muster)/sizeof(muster[0]);

  int sprweite[laenge_muster+1];

  int position
    = sucheteilfeld_kmp( text, laenge_text,
                         muster, sprweite, laenge_muster );

  printf( "%d\n", position );

  return 0;

} /* main( int nargs, char **args ) */

www.wachtler.de