String matching WS13-14

Aus ProgrammingWiki

Archivierte Version vom 2014-01-10T23:22:43+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Allgemein/Festlegungen
2 Naiver Algorithmus
3 Weitere Algorithmen
4 Der Boyer-Moore-Horspool Algorithmus

Allgemein/Festlegungen

String matching befasst sich allgemein mit dem Finden eines Wortes in einem Text.
Beim Text handelt es sich um eine Aneinanderreihung von Zeichen (der normalen ASCII-Tabelle) und wird mit t abgekürzt. Das Wort setzt sich ebenfalls aus den selben Zeichen zusammen, hat jedoch (in dem Fall) stets eine geringere länge als der Text. Abgekürzt wird es mit w und kann auch aus mehreren Wörtern bestehen, wird aber im Folgenden nur als "Wort" bezeichnet.

Naiver Algorithmus

Der Algorithmus sucht und vergleicht Zeichen für Zeichen im Text.

void nativeSuche(String text, String wort){
  int laengeText = text.length();
  int laengeWort = wort.length();
  char[] cWort = wort.toCharArray();
  char[] cText = wort.toCharArray();		  
  int position = 0;
  int aktZeichen;
  while (position <= laengeText-laengeWort){
  aktZeichen = 0;
    while (aktZeichen < laengeWort && wort.charAt(aktZeichen)==text.charAt(position+aktZeichen)){
      aktZeichen++;
    }
    if (aktZeichen == laengeWort){
      System.out.println("Wort an der Stelle " + (position+1) + " im Text gefunden.");
    }
    position++;
  }
}

nativeSuche("Das ist das Haus vom Nikolaus","Maus");

Weitere Algorithmen

Einige weitere Algorithmen.

Der Boyer-Moore-Horspool Algorithmus

Ein sehr bekannter Algorithmus für das String-Matching-Problem.