GEHNIO
Gesamtschule Duisburg-Hamborn/Neumühl
Informatik in der Oberstufe

> Home
> Algorithmen
> Datenstrukturen
> Maschinenmodelle
> Probleme
> Themen
> Mindmaps
> Aufgaben
> Facharbeit
> Abitur
> Projekte
> Informatik-AG
> News
> Impressum
> email
  


String Matching

Beim Suchen von W�rtern in Texten unterscheidet man zwischen zwei verschiedenen Arten von Texten. Sogenannte statische Texte sind Texte, die sich nur sehr selten und geringf�gig ver�ndern. Bei solchen Texten ist es sinnvoll, ein Verfahren zu entwickeln, mit dem eine schnelle Suche nach W�rtern im Text m�glich ist. Bei einem W�rterbuch zum Beispiel ist es �blich, dieses in Abschnitte A..Z zu unterteilen und die Stichworte alphabetisch anzuordnen. In einem derart aufbereiteten Text ist die Suche einfach und kann entsprechend schnell durchgef�hrt werden.
Ganz anders verh�lt es sich bei dynamischen Texten, also Texten, die schnellen Ver�nderungen unterliegen. Ein typisches Beispiel f�r einen dynamischen Text ist der Text im Editor eines Textverarbeitungsprogramms oder der Entwicklungsumgebung eines Compilers. Zum Suchen in solchen Texten werden Algorithmen ben�tigt, die m�glichst schnell durch Vergleich des Suchmusters mit dem Text das zu suchende Muster findet, bzw. Mi�erfolg meldet. Hier kommen Sting-Matching-Algorithmen zum Einsatz.
Beim String Matching geht man von folgender Problemstellung aus:
Gegeben sei ein Text T[1..n] der Länge n (Codierung als Array) und ein Muster (engl. pattern) P[1..m] der Länge m, wobei m<=n gelten soll. Die Arrayeinträge von T und P sind aus dem selben Alphabet.

Beim String Matching ist man daran interessiert, das Muster P im Text T zu finden, bzw. die Anzahl der Zeichen anzugeben, um die das Muster über dem Text verschoben werden muss, um mit der gleichen Zeichenkette im Text deckungsgleich zu sein. Bei dieser Verschiebung spricht man von einem shift .
Das Muster P kommt im Text T mit shift s vor, falls gilt

Gesucht T[s+1,...,s+m] = P[1,...,m].

Betrachten wir einmal folgendes Beispiel:
In dem Textarray T[1..15]

3

5

8

1

2

3

4

5

8

2

5

6

9

1

2

kommt die Zeichenkette 1 2 3 4 5 mit einem shift von 3 vor.
Die Aufgaben beim String Matching können natürlich variieren. So besteht die Möglichkeit...

  • nur den ersten shift eines Musters P im Text T zu finden,
  • alle shifts eines Musters P im Text T zu finden,
  • nicht shifts zu bestimmen, sondern nur deren Anzahl.

Ein naiver Algorithmus

Sehr hilfreich ist es, wenn wir das Problem, ob zwei Zeichenketten gleich sind zunächst gesondert betrachten. Die folgende einfache Funktion ermöglicht den Vergleich zweier Zeichenketten A[1..m] und B[1..m]:

function test(array A[1..m], array B[1..m]):returns boolean
begin
equal := true
for i from 1 to m do
   begin
   if A[i] <> B[i] then equal:= false
   end
return equal
end

Diesen Algorithmus können wir so abwandeln, dass er für global definierte Zeichenketten T[1..n] und P[1..m] einen zulässigen shift bestimmt.

function test(int s):returns boolean
begin
feasible := true
for i from 1 to m do
   begin
   if P[i] <> T[i+s] then feasible:= false
   end
return feasible
end

Damit es es nun möglich, einen naiven Algorithmus für das String Matching zu formulieren, wobei wir nach allen zulässigen shifts suchen und diese ausgeben wollen.

algorithmus string_matching
for s from 0 to n-m do
      begin
      if test(s) then write(s)
      end
end

Da das m Zeichen lange Muster P n-m+1 mal mit dem Text verglichen werden muss. beträgt die Komplexität dieses einfachen Algorithmus O((n-m+1)*n)=O(n*m).
Natürlich sucht man für das String Matching Problem schnellere Algorithmen. Im Folgenden sollen einige Ansätze dazu vorgestellt werden.

Der Rabin-Karp-Algorithmus - Matching mit Fingerprint

Grundlegende Idee dieses Algorithmus ist es, nicht das Muster P selbst (zeichenweise) mit dem Text zu vergleichen, sondern statt dessen eine wesentlich kleinere Information, gewissermaßen den Fingerabdruck (engl. fingerprint) des Musters mit dem Text zu vergleichen. Der Finderabdruck des Musters wird mittels einer Funktion berechnet, die als Hashfunktion bezeichnet wird. Die Hashfunktion soll das Muster auf einen Fingerabdruck abbilden, der so klein ist, dass seine Information in einer Speicherstelle gespeichert werden kann, also mit einer Komplexität von O(1) verarbeitet werden kann.

Der Algorithmus vergleicht also den Fingerabdruck des Musters mit dem Hashfunktionswert von entsprechenden Textabschnitten. Stimmen die Hashwerte von Muster und Textabschnitt nicht überein, so kann sofort weitergeschoben werden, ansonsten muss ein Vergleich zeigen, dass tatsächlich Gleichkeit bei Muster und Textabschnitt besteht. Der tatsächliche Vergleich ist in diesem Fall notwendig, da es sein kann, dass die Hashfunktion auch ungleiche Zeichenketten auf den gleichen Hashwert abbilden kann.

Wichtig ist es, dass die Berechnung des Hashwertes einer Zeichenkette in O(1) geschehen kann. Dies ist möglich, wenn man eine Hashfunktion nach der Kongruenzmethode (modulo q) einsetzt.

Betrachten wir das obige Beispiel mit einem Alphabet A = { 0 , ... , 9 }. Soll bei einem Text von ...12345678... das Vergleichsfenster von der Länge m=6 von 123456  auf 234567 weitergeschoben werden, so kann der Hashwert h' für 234567 aus dem Hashwert h für 123456 berechnet werden aus

h' = ( ( h - 1* u)* |A| + 7)

wobei u = 10 m-1 modulo q und |A| = Anzahl der Zeichen im Alphabet A sind. Alle Berechnungen werden dabei modulo q durchgeführt. q sei dabei eine Primzahl, wobei q größer als die Musterlänge von m sein sollte.

algorithmus Rabin_Karp
begin
q Primzahl
fingerprintp:=0
fingerprintt:=0
u:=|A|m-1 mod q
for i from 1 to m do
 begin
  fingerprintp:=(|A|*p+P[i])mod q
  fingerprintt:=(|A|*t+T[i])mod q
 end;
  for shift from 0 to n-m do
     begin
     if fingerprintp=fingerprintt
      then if test(shift) then write(shift)
     if shift < n-m then
     fingerprintt:=((fingerprintt-T[shift+1]*u)*|A|+T[shift+m+1]) mod q
     end
end

Im schlechtesten Fall hat der Rabin-Karp-Algorithmus allerdings dieselbe Komplexität wie der oben beschriebene naive Algorithmus. Wenn zum Beispiel T=zn und P=zm, dann sind die fingerprints selbstverständlich immer gleich und es wird im Prinzip der naive Algorithmus ausgeführt, da ja bei gleichen fingerprints die test-Funktion ausgeführt wird.

 

 

  
  � 2002 Gesamtschule Duisburg-Hamborn/Neumühl.  
Hosted by www.Geocities.ws

1