4.1 Mustersuche brute force

Mit brute force (rohe Gewalt) bezeichnet man Methoden, die ohne viel Nachdenken den direktesten Weg gehen, und dabei gnadenlos Rechenzeit verbraten; beispielsweise um ein Passwort zu knacken einfach alle möglichen Kombinationen durchprobieren.

Bei der Mustersuche in Feldern sieht das folgendermaßen aus: Man geht an die erste Stelle des Textes, und vergleicht ab hier alle Zeichen des Musters paarweise mit der ersten Stelle und den folgenden im Text. Falls bis zum Ende des Musters alle Feldelemente paarweise gleich sind, hat man die gesuchte Stelle gefunden. Ansonsten geht man im Text eine Position weiter, und vergleicht wieder paarweise alle Stellen des Musters mit fortlaufenden Stellen im Text. Dies wird wiederholt, bis man kurz vor dem Ende des Textes ist: hinter der Position N-M kann das Muster nicht mehr beginnen und vollständig enthalten sein.

An jeder Position des Textes kann man abbrechen, wenn eine Stelle nicht zum Muster paßt. Je nach Text und Muster kann das im Schnitt eher oder später der Fall sein.

Das Laufzeitverhalten ist dementsprechend $O((\mbox{N}-\mbox{M})\times\mbox{M})$ für den worst case (wenn immer das ganze Muster verglichen werden muß) bis herunter zu $O(\mbox{N}-\mbox{M})$ im best case, wenn bereits immer das erste Zeichen aus dem Muster nicht zutrifft. Wo genau dazwischen der durchschnittliche Fall liegt, hängt stark vom Text und vom Muster ab.

Falls N im Vergleich zu M sehr groß ist, wird die tatsächliche Laufzeit also etwa zwischen $O(\mbox{N})$ und $O(\mbox{N}\times\mbox{M})$ liegen.

Der ungünstigste Fall tritt dann ein, wenn der Text ebenso wie das Muster aus lauter gleichen Zeichen besteht, außer dem jeweils letzten Zeichen. Dann sind alle Kombinationen zu prüfen, um dann an der letzten möglichen Position festzustellen, ob das Muster hier enthalten ist:

text	[0]	[1]	[2]	...	[N-3]	[N-2]	[N-1]
	a	a	a	...	a	a	b

Muster:

muster	[0]	[1]	[2]	...	[M-3]	[M-2]	[M-1]
	a	a	a	...	a	a	b

In C (und sehr ähnlich in Java) könnte die brute force-Suche so aussehen:

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

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


/* sucheteilfeld <brute force>
 * +-----------------------------------------------------+
 * |                                                     |
 * | < alle Positionen in text[]: >                      |
 * |                                                     |
 * +-----------------------------------------------------+
 * |                                                     |
 * | itext = 0 ... (n-m-1)                               |
 * |  +--------------------------------------------------+
 * |  |                                                  |
 * |  | < alle Positionen im Muster: >                   |
 * |  |                                                  |
 * |  +--------------------------------------------------+
 * |  |                                                  |
 * |  | imuster = 0 ... (m-1)                            |
 * |  |  +-----------------------------------------------+
 * |  |  |                                               |
 * |  |  |     text[itext+imuster] != muster[imuster]    |
 * |  |  |                                |              |
 * |  |  +------------- ja ---------------+----- nein ---+
 * |  |  |                                |              |
 * |  |  | <- alle Positionen im Muster   |              |
 * |  |  |                                |              |
 * |  |--+--------------------------------+--------------+
 * |  |                                                  |
 * |  |  Muster gefunden, Lösung ist itext               |
 * |  |                                                  |
 * |  +--------------------------------------------------+
 * |  |                                                  |
 * |  |  <- sucheteilfeld <brute force>                  |
 * |  |                                                  |
 * |--+--------------------------------------------------+
 * |                                                     |
 * | Muster nicht gefunden                               |
 * |                                                     |
 * +-----------------------------------------------------+
 */

/* 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 m; die Länge von muster ist n.
 */
int sucheteilfeld_brute_force( char text[],
                               int m,
                               char muster[],
                               int n
                               )
{
  int itext, imuster;

  /* Schleife über alle Positionen von text[]: */
  for( itext=0; itext<m-n; itext++ )
  {
    /* zeichenweise text mit muster vergleichen: */
    for( imuster=0; imuster<n; imuster++ )
    {
      if( text[itext+imuster]!=muster[imuster] )
      {
        /* Unterschied gefunden! */
        break;
      }
    }

    if( imuster==n )
    {
      /* innere Schleife bis zum Ende durchlaufen,
       * also Übereinstimmung von text und Muster
       * ab text[itext] gefunden!
       */
      return itext;
    }
  }

  /* nichts gefunden! */
  return -1;
}

int main( int nargs, char **args )
{
  char text[] =
  {
    'e', 'h', 'n', 'e', ' ',
    'm', 'e', 'h', 'n', 'e', ' ',
    'm', 'u', 'h'
  };

  char  muster[] =
  {
    'm', 'e', 'h', 'n', 'e'
  };

  int position
    = sucheteilfeld_brute_force( text,
                                 sizeof(text)/sizeof(text[0]),
                                 muster,
                                 sizeof(muster)/sizeof(muster[0])
                                 );

  printf( "%d\n", position );
  return 0;
} /* main( int nargs, char **args ) */

Achtung! Man ist vielleicht versucht, bei einem festgestellten Unterschied die Suche nicht ein Element nach dem letzten Startpunkt im Text fortzusetzen, sondern aus Geschwindigkeitsgründen hinter der zuletzt verglichenen Stelle (,,soweit habe ich schon verglichen, also kann ich dahinter weitermachen``).

Dies kann aber dazu führen, daß man ein Vorkommen des Musters übersieht!

Beispiel: Der Text sei:

text	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
	a	a	b	a	a	b	a	b	y	z

und das Muster sei:

muster	[0]	[1]	[2]	[3]	[4]
	a	a	b	a	b

Dann werden erst die Elemente text[0] bis text[3] erfolgreich auf Gleichheit mit dem jeweils zugehörigen Element in muster getestet; bei text[4] wird ein Unterschied zu muster[4] festgestellt. Würde man jetzt die Suche fortsetzen, indem man text[4] und die folgenden Elemente mit muster[0] und seinen Nachfolgern vergleicht, übersieht man das Vorkommen des Musters ab text[3]. Solange man keine weiteren Maßnahmen trifft, muß man also sicherheitshalber nach der erfolglosen Suche ab text[i] als nächstes das Muster ab text[i+1] suchen.