Thomas Kramer

IT-COW | All posts tagged 'Knuth-Morris-Pratt-Algorithmus'

Der KMP-Algorithmus mit minimaler Datenpufferung

By Administrator at Dezember 13, 2011 23:06
Filed Under: Algorithmen, Java, Programmierung allgemein, Studium

Allen meinen bisherigen Suchalgorithmus-Implementierungen ist gemein dass sie die zu durchsuchende Datei immer vollständig im Arbeitsspeicher zwischenspeichern. Das ist für Laufzeitanalysen sinnvoll weil man die I/O-Leistung des Massenspeichers nicht mittesten will, kann aber bei großen Dateien hinderlich sein.

 

Der KMP-Algorithmus bietet sich für eine Suche mit minimaler Datenpufferung an weil er immer nur sequentiell eine Datei durchsucht, insofern habe ich ihn einmal darauf angepasst. Für die Arbeitsweise dieses Algorithmus muss die aktuelle absolute Position in der Datei modulo der Puffergröße genommen werden.

 

Da bitweise Modulo-Berechnung schneller als die gewöhnliche ist habe ich die Puffergröße auf 2^10 = 1024 gesetzt, weil sie nur mit Zweierpotenzen als Divisor funktioniert. Da ein Suchpattern größer als der Puffer sein kann wird bei dieser Variante das aktuelle Suchfenster nicht mehr angezeigt und nur noch die Position bei einem Fund zurückgegeben. Für einen Vergleich empfehle ich Notepad++, mit dem eine Cursorposition direkt angesprungen werden kann.

 

Alle meine bisherigen Implementierungen von Suchalgorithmen mit zeilenweisem Einlesen haben übrigens eine teilweise falsche Position bei einem Fund zurückgegeben, wegen des Overheads beim zeilenweisen Einlesen - bei dieser Einleseart werden eben Ein- und Zwei-Zeichen-Zeilenumbrüche gleich behandelt, wobei eine einzelne Datei aber grundsätzlich beide Zeilenumbruchsarten gleichzeitig enthalten kann.

 

Das führt im Zusammenhang mit String-Matching-Algorithmen nicht nur zu teilweise falschen Suchpositionen sondern kann auch zu einem signifikanten Plus an RAM-Verbrauch führen, weil der Stringbuilder u. U. nicht mehr mit der korrekten Größe initialisiert wird.

 

Diese Variante und meine Implementierung des randomisierten Rabin-Karp-Algorithmus arbeiten nun jedenfalls korrekt und mit blockweisem Einlesen. Bei der KMP-Variante unten ist der RAM-Verbrauch zudem nur noch minimal.

 

Update 22.12.2011: In der Diplomarbeit von Gausi.de (frei herunterladbar) gibt es eine optimierte Variante vom KMP-Algorithmus, die sich dort unrolled_KMP nennt. Eine der Optimierungsideen ist nicht nur im Muster weiterzuspringen, sondern zuerst auch im gesamten String auf die erste übereinstimmende Position zu gehen statt dort linear fortzuschreiten.

 

Allerdings wird bei ihm in dieser KMP-Variante mit GOTOs gearbeitet, welche es unter Java nicht gibt und in der IT-Welt auch eher verpönt sind (können u. U. aber auch schneller sein). Leider hat Herr Gaußmann zahlreiche Algorithmen, nur leider nicht den Rabin-Karp implementiert. Ansonsten ist seine Arbeit weit fortgeschrittener als meine und auch schön visualisiert.

 

Seine Arbeit ist in Delphi 7 geschrieben und dazu fiel mir noch ein dass Pascal/Delphi mit dieser Indizierungs-Methode auf Strings (String[x]) bei 1 anfängt zu zählen (Link), was recht gefährlich ist wenn man es auf andere Sprachen übersetzen will - weil man normalerweise bei 0 anfängt zu zählen. Außerdem ist Pascal/Delphi noch fehlertoleranter gewesen was Bereichsüberschreitungen bei Strings anging (ich denke gerade speziell an die substring-Funktion) und gab in so einem Falle einfach einen Leerstring zurück - Java wirft dagegen Exceptions bei den kleinsten Überschreitungsfehlern.

 

Insofern würde ich Delphi als Referenzplattform für Implementierungen von String-Matching-Algorithmen als eher schlechte Wahl ansehen, aber das soll keine Kritik sein. Er hat auf jeden Fall weit mehr Algorithmen abgehandelt als ich. Im Quellcode zu seiner Routine Search_BM_Unrolled findet sich übrigens ein witziger Kommentar:

 

// ACHTUNG: DEN HIER NOCHMAL TESTEN; OB DER ÜBERHAUPT FUNKTIONIERT ;-)

 

Update 06.03.2012:  Ich verwende nun den überladenen append-Befehl des StringBuilders mit drei Parametern, wodurch das Einlesen weniger Quellcodezeilen benötigt.

 

Speziell zum Thema Loop Unrolling bitte außerdem meinen eigenen Blog-Eintrag beachten.

 

/* KMP-Algorithmus mit minimaler Datenpufferung von Thomas Kramer
   Version 1.2 vom 06.03.2012 */


/* Konfiguration */
   /* Patterndatei verwenden für längere Suchmuster, auf "" setzen wenn Eingabe
      von Hand gewünscht. Forwardslash / verwenden, gemäß
      http://docs.oracle.com/javase/tutorial/essential/environment/sysprop.html
      wird in Java plattformspezifisch eh automatisch umgewandelt */

//   String patternFile="C:/Users/thomas/Downloads/m10.TXT";
    String patternFile="";

   color buttoncolor = color(102);
   color highlight = color(51);
   color c1 = color(0, 0, 0);
   color c2 = color(255, 255, 255);   
   color c3 = color(193, 185, 185);
/* Konfiguration-Ende */

color currentcolor;
RectButton rect1,rect2,rect3;
boolean locked = false;
String loadPath="";
StringBuilder searchString = new StringBuilder(0);
String searchedString="";
int searchPosition=0;
char[] ioBuf;
boolean file_selected=false;
String timeString="";
int readed = 0;
/* enthält die Analyse des Musters */
int[] next;

import java.util.concurrent.TimeUnit;

/*-----------------------------------------------------------------------------
 *  Initialisierungen
 *-----------------------------------------------------------------------------*/

void setup()
{
   /* Größe des Screens setzen */
  size(screen.width-400, 300);
 
  /* Bildschirm löschen */
  background(c3);
 
  /* Buttons instanziieren */
  rect1 = new RectButton(((screen.width)/2)-400, 130, 50, 20, buttoncolor, highlight); 
  rect2 = new RectButton(((screen.width)/2)-400, 152, 380, 20, buttoncolor, highlight);   
  rect3 = new RectButton(((screen.width)/2)-400, 175, 50, 20, buttoncolor, highlight);     

  /*-----------------------------------------------------------------------------
   *  Patternfile laden
   *-----------------------------------------------------------------------------*/
 
  patternFile = trim(patternFile);
  if (patternFile != "")
  {
    File f = new File(patternFile);
    if (!f.exists())
      throw new IllegalArgumentException("Fehler, Patterndatei ist angegeben und existiert nicht!");
    int fileLength = (int) f.length();        
    f = null;
   
    BufferedReader br = null;
    int buffer;
    searchString = new StringBuilder(fileLength);
     
    try
    {
      br = new BufferedReader(new FileReader(patternFile));           
      ioBuf = new char[1024];           
      while ((buffer = br.read(ioBuf,0,1024)) != -1)
      {
        /* eingelesene Zeile anhängen */
        searchString.append(ioBuf,0,buffer);
      }     
    } catch (IOException e)
    {
      println("Pattern-Datei kann nicht geöffnet werden!");
    } finally {
      try
      {
        if (br != null)
          br.close();
      } catch (IOException e) {}   
    }    
   
    next = new int[searchString.length()+1];               
  }
}

/*-----------------------------------------------------------------------------
 *  draw()-Funktion wird aufgerufen wenn der Bildschirm neu gezeichnet wird
 *-----------------------------------------------------------------------------*/

void draw()
{
  /*-----------------------------------------------------------------------------
   *  Hintergrundfarbe setzen, dabei wird auch der gesamte Bildschirm gelöscht
   *-----------------------------------------------------------------------------*/

  background(c3);   
 
  /*-----------------------------------------------------------------------------
   *  Überschriften setzen
   *-----------------------------------------------------------------------------*/

  fill(c2);
  textSize(20);
  text("Der Knuth-Morris-Pratt-Algorithmus", ((screen.width)/2)-370, 50);
  textSize(15);
  text("von Thomas Kramer", ((screen.width)/2)-270, 80);
  text("(ESC zum Abbrechen)", ((screen.width)/2)-275, 110);
  textSize(13);

  /*-----------------------------------------------------------------------------
   *  Buttons setzen und beschriften
   *-----------------------------------------------------------------------------*/
   
  rect1.display();
  if (patternFile == ""
  {
    rect2.display();           
  } else {
    fill(c2);
    text(patternFile, ((screen.width)/2)-398, 167);                   
  }
  rect3.display();                  
  update(mouseX, mouseY);    
  text("FileOpen: ", ((screen.width)/2)-485, 145);
  text("SearchString: ", ((screen.width)/2)-485, 167); 
  text("Start ", ((screen.width)/2)-485, 190);   
 
  /*-----------------------------------------------------------------------------
   *  Eingabetexte, Statusmeldungen etc. setzen
   *-----------------------------------------------------------------------------*/

  /* weiße Schriftfarbe setzen */
  fill(c2); 
  /* anzeigen des Suchstrings */
  if ((patternFile == "") && (searchString.length() > 0))
      text(searchString.toString(), ((screen.width)/2)-398, 167);               
  text(searchString.length() + " Zeichen Länge", ((screen.width)/2), 167);       

  /* ausgewählte Datei anzeigen */ 
  if (loadPath!=null)
    text(loadPath, ((screen.width)/2)-330, 145);                          

  /* Suchstring anzeigen */ 
  text(searchedString, ((screen.width)/2)-485, 230);  

  /* wenn Postion ungleich -1 ist der Algorithmus bereits einmal durchgelaufen */
  if (searchPosition != -1)
  {
    fill(c1);   
   
    /* Suchposition anzeigen */
    text("Pos " + (searchPosition + 1), ((screen.width)/2)-485, 243);             
   
    /* Ergebnis der Zeitmessung anzeigen */
    text(timeString, ((screen.width)/2)-485, 265);
 
  } else {
    text("Pos " + searchPosition + " = nicht gefunden", ((screen.width)/2)-485, 243);                       
  }
 
}

/*-----------------------------------------------------------------------------
 *  allgemeine Vorarbeiten
 *-----------------------------------------------------------------------------*/

void praeProcessing()
{
  if  ((loadPath == "") || (searchString.length() == 0))
    return;
   
  long completeTimeBefore = 0;
  long completeTimeAfter  = 0;   
  long completeTimeDiff = 0;

  /* nimm die Vorher-Zeit für Gesamtdurchlauf */   
  completeTimeBefore = System.currentTimeMillis();   
 
  /* Algorithmus starten */
  searchPosition = kmpSearch(); 
 
  /* nimm die Danach-Zeit für Gesamtdurchlauf und bestimme Differenz */   
  completeTimeAfter = System.currentTimeMillis();     
  completeTimeDiff   = completeTimeAfter - completeTimeBefore;   
   
  /* Ausgabe für Gesamtdurchlauf formatieren */
  timeString = String.format("Gesamtzeit: %02d min, %02d sec, %03d milliseconds\n",
    TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff),
    TimeUnit.MILLISECONDS.toSeconds(completeTimeDiff) -
      TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff)),
    completeTimeDiff % 1000);                            
}

/*-----------------------------------------------------------------------------
 *  Präfix-Analyse des Muster, gehört zum Präprocessing für den KMP-Algorithmus
 *-----------------------------------------------------------------------------*/

void kmpPraeprocess()
{
  int i = 0;    
  int j = -1;     
  next[i] = j;

  while (i < searchString.length())
  {
     while ((j >= 0) && (searchString.charAt(j) != searchString.charAt(i)))                            
       j = next[j];                     
  
     i++;
     j++;
     next[i] = j;
  }

  /* Debug-Ausgabe */ 
  /* for (int x=0;x<=next.length-1;x++)
     println(next[x]); */

}

/*-----------------------------------------------------------------------------
 *  Datei-Fragment laden
 *-----------------------------------------------------------------------------*/

int loadFileFragment(BufferedReader br)
{   
  int result = 0; 
 
  try
  {
    ioBuf = new char[1024];     
    /* readed liefert Anzahl gelesener Zeichen zurück, siehe auch
       http://www.dpunkt.de/java/Referenz/Das_Paket_java.io/4.html#read%28%29 */
 
    readed = br.read(ioBuf,0,1024);
  } catch (IOException e)
  {
    println("Datei konnte nicht oder nicht vollständig eingelesen werden!");
    result = -1;   
  }
 
  return result;
}

/*-----------------------------------------------------------------------------
 *  eigentlicher Suchalgorithmus
 *  - zurückgegeben wird die Suchposition
 *    oder -1 wenn nicht gefunden
 *-----------------------------------------------------------------------------*/

int kmpSearch()
{
  println("Start Suche");
 
  int result = -1;
  int n = 0; 
  int m = 0;
  int i = 0;
  int j = 0; 
  boolean found = false;  
  readed = 0;
 
  /* Präfix-Analyse für KMP */
  kmpPraeprocess();         
 
  File file = new File(loadPath);
  int fileLength = (int) file.length();  
  file = null;
 
  n = fileLength;
  m = searchString.length();       
  BufferedReader br = null;
 
  try
  {
    br = new BufferedReader(new FileReader(loadPath));           
    if (loadFileFragment(br) != -1)
    {
      /* solange Text noch nicht komplett durchlaufen... */
      while (i < n)
      {       
        while ((j >= 0) && (ioBuf[i & 1023] != searchString.charAt(j)))
          j = next[j];                             
 
        i++;
        j++;
       
        /* Übereinstimmung gefunden */
        if (j == m)
        {
           found = true;
           break;
        
           /* Muster weiterverschieben, aber wir suchen ja nur das erste Vorkommen */
           /*j = next[j]; */
        }
       
        /* beim letzten Zeichen angelangt? Wenn ja nächsten Block laden */
        if ((i & 1023) == 0)
        {
          if (loadFileFragment(br) == -1)
            break;
        }                        
      }
    }
  } catch (IOException e)
  {
    println("Datei kann nicht geöffnet werden!");
  } finally {
    try
    {
      if (br != null)
        br.close();
    } catch (IOException e) {}   
  }  
 
  if (found)
    result = (i - j);  
   
  return result;
}

/*-----------------------------------------------------------------------------
 *  nachfolgend der Code für die Button-Implementierung, denn Buttons gibt es
 *  standardmäßig nicht in Processing
 *-----------------------------------------------------------------------------*/

void update(int x, int y)
{
  if(locked == false) {
    rect1.update();
    rect3.update();
  }
  else {
    locked = false;
  }

  if(mousePressed) {
    if(rect1.pressed()) {
      currentcolor = rect1.basecolor;
      if (!file_selected)
      {       
        loadPath = selectInput();           
        file_selected = true;
      }
    }
   
    if (rect3.pressed()) {
      /* Suche starten */
     if ((file_selected) && (searchString.length() > 0))
      {
        praeProcessing();
      }     
    }
  }
}

class Button
{
  int x, y;
  int i_width,i_height;
  color basecolor, highlightcolor;
  color currentcolor;
  boolean over = false;
  boolean pressed = false;  

  void update()
  {
    if(over()) {
      currentcolor = highlightcolor;
    }
    else {
      currentcolor = basecolor;
    }
  }

  boolean pressed()
  {
    if(over) {
      locked = true;   
      return true;
    }
    else {
      locked = false;           
      return false;
    }   
  }

  boolean over()
  {
    return true;
  }

  boolean overRect(int x, int y, int width, int height)
  {
    if (mouseX >= x && mouseX <= x+width &&
      mouseY >= y && mouseY <= y+height) {
      return true;
    }
    else {
      return false;
    }
  }
}

class RectButton extends Button
{
  RectButton(int ix, int iy, int iwidth, int iheight, color icolor, color ihighlight)
  {
    x = ix;
    y = iy;
    i_width = iwidth;
    i_height = iheight;
    basecolor = icolor;
    highlightcolor = ihighlight;
    currentcolor = basecolor;
  }

  boolean over()
  {
    if( overRect(x, y, i_width, i_height) ) {
      over = true;
      return true;
    }
    else {
      over = false;
      return false;
    }
  }

  void display()
  {
    stroke(255);
    fill(currentcolor);
    rect(x, y, i_width, i_height);
  }
}

void keyPressed()
{
  if (patternFile != "")
    return;
   
  if (key!=CODED)
  {   
    searchedString="";     
    searchPosition=0;   
   
    if (keyCode==DELETE)
    {
      searchString.setLength(0);
      next = new int[0];     
    } else if (keyCode==BACKSPACE)
    {
      if (searchString.length()>0)
      {
        /* in Bezug auf Speicherverbrauch suboptimal, aber für die Patterndatei akzeptabel.
           Außerdem sollte man nach Datei-Laden nicht mehr im Suchprogramm editieren, nur
           wenn das Suchmuster komplett von Hand eingegeben wurde. */

        String temp = searchString.toString().substring(0,searchString.length()-1);     
        searchString.setLength(0);
        searchString.append(temp);
        temp = "";
       
        /* Next-Array passend setzen */
        next = new int[searchString.length()+1];
      }
    } else if (keyCode==ENTER)
    {
      praeProcessing();    
    } else {
      searchString.append(key);
      next = new int[searchString.length()+1];           
    }      
  }
}

 

Monats-Liste