Thomas Kramer

IT-COW | All posts tagged 'String-Matching'

Der Knuth-Morris-Pratt-Algorithmus

By Administrator at November 13, 2011 21:45
Filed Under: Algorithmen, Programmierung allgemein, Studium

Nachfolgend der Knuth-Morris-Pratt-Algorithmus. Für weitere Ausführungen, insbesondere der Arbeitsweise des KMP-Algorithmus, siehe meine Projektarbeit zum Thema String-Matching.

 

Update 30.11.2011: Für längere Suchmuster kann nun eine Patterndatei angegeben werden. Außerdem wurden für das Datei-Laden nun zwei verschiedene Methoden implementiert (umschaltbar), einmal mit StringBuilder (BufferedReader) und dann noch mit der loadStrings-Methode.

 

Gemäß meiner Tests benötigt die StringBuilder-Methode reproduzierbar ungefähr 150 MB weniger RAM bei der gleichen Testdatei, von der Geschwindigkeit gibt es keinen Unterschied zwischen den beiden Varianten.

 

Update 13.12.2011: Diese Variante habe ich noch nicht auf das blockweise Einlesen angepasst, daher besser meine neuere Variante mit minimaler Datenpufferung benutzen. Außerdem habe ich bei der Variante unten vergessen den BufferedReader nach dem Einlesen wieder zu schliessen.

 

/* Knuth-Morris-Pratt-Algorithmus von Thomas Kramer
   Version 1.0 vom 30.11.2011 */


/* Konfiguration */
   /* Anzahl der Suchdurchläufe */
   int runs = 10; 
   /* 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/m1.TXT";
//   String patternFile="";  
   /* StringBuilder fürs Laden verwenden (braucht weniger RAM) ja/nein */
   boolean useStringBuilder=true;  

   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="";
String searchString="";
String searchedString="";
int searchPosition=0;
String completeString="";
boolean file_selected=false;
String timeString="";
long completeTimeDiff   = 0;   
/* enthält die Analyse des Musters */
int[] next;
/* generische Liste mit allen Zeiten für jeden einzelnen Durchlauf */
LinkedList <Long> times = new LinkedList <Long> (); 

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!");
    String lines[] = loadStrings(patternFile);
    searchString=trim(join(lines,"\r\n")); 
    lines = null;      
   
    next = new int[searchString.length()+1];               
  }
}

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

void loadFile()
{
  if (useStringBuilder)
  { 
    StringBuilder sb = new StringBuilder();        
    try
    {
      String thisLine=null;
      BufferedReader br = new BufferedReader(new FileReader(loadPath));
      while ((thisLine = br.readLine()) != null)
      {
        /* eingelesene Zeile anhängen */
        sb.append(thisLine);
        /* Zeilenumbruch hinzufügen */
        sb.append("\r\n");
      }
    } catch (IOException e)
    {
      println("Error: " + e);    
    }        
    completeString = sb.toString();
    sb.setLength(0);
    sb = null;
  } else {
    String lines[] = loadStrings(loadPath);
    completeString=trim(join(lines,"\r\n")); 
    lines = null;   
  } 
}

/*-----------------------------------------------------------------------------
 *  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 != ""))
      text(searchString, ((screen.width)/2)-398, 167);               
  text(searchString.length() + " Bytes 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=="")
    return;
   
  long completeTimeBefore = 0;
  long completeTimeAfter  = 0;   
   
  /* Datei laden */
  loadFile();

  /* 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;   
 
  /* berechne den Median = Durchschnitt der errechneten Durchläufe */
  long median = calcMedian();       
 
  /* Ausgabe für Gesamtdurchlauf formatieren */
  timeString = String.format("Gesamtzeit: %02d min, %02d sec, %03d milliseconds, Median über %d-Durchläufe: %02d min, %02d sec, %03d milliseconds \n",
    TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff),
    TimeUnit.MILLISECONDS.toSeconds(completeTimeDiff) -
      TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff)),
    completeTimeDiff % 1000,   
    runs,
    TimeUnit.MILLISECONDS.toMinutes(median),
    TimeUnit.MILLISECONDS.toSeconds(median) -
      TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(median)),
    median % 1000
  );
 
  /* letztes Suchfenster für Anzeige festlegen */
  int i = searchPosition;  
  boolean cutted = false
  if (i < 0)
  {
    /* nicht gefunden */
    if (completeString.length()>100)   
    {
      searchedString = completeString.substring(0,100);                             
      cutted = true;
    } else {
      searchedString=completeString;               
    }
  } else if ((completeString.length() -i + 1)>100)
  {
    /* ab der gefundenen Position folgen noch mehr als 100 Zeichen */
    searchedString = completeString.substring(i,i+100);                 
    cutted = true;
  } else {
    /* ab der gefundenen Position folgen weniger oder genau 100 Zeichen */
    searchedString=completeString.substring(i);
  }
  /* Zeilenumbrüche entfernen */
  searchedString = searchedString.replace("\r\n"," ");
  if (cutted)
    searchedString=searchedString + " [..]";                               
   
  /* Konsolenausgaben */
  /* die sind deswegen hier drin weil sie in draw() immer wieder aufgerufen werden würden */
  println("Alle Zeiten:\n");
  for (long timeX: times)
  {
    println(String.format("%02d min, %02d sec, %03d milliseconds",
                   TimeUnit.MILLISECONDS.toMinutes(timeX),
                   TimeUnit.MILLISECONDS.toSeconds(timeX) -
                   TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(timeX)),
                   timeX % 1000));
  }   
 
  /* bestimme maximale Zeitspanne zwischen Minimum und Maximum */
  /* muß nach Median-Funktion aufgerufen werden, da sortierte Collection erforderlich */
  long maxTimeDiff = (times.get(times.size()-1) - times.get(0)); 
  println(String.format("Maximale Differenz: %02d min, %02d sec, %03d milliseconds",
                 TimeUnit.MILLISECONDS.toMinutes(maxTimeDiff),
                 TimeUnit.MILLISECONDS.toSeconds(maxTimeDiff) -
                 TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(maxTimeDiff)),
                 maxTimeDiff % 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]); */

}

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

int kmpSearch()
{
  int result = -1;
  long timeBefore = 0;
  long timeAfter  = 0;
  long timeDiff   = 0; 
  int n = 0; 
  int m = 0;
  int n_m = 0; 
  boolean found=false;  
  times.clear(); 
 
  /* Algorithmus gemäß der Anzahl in der Variablen ´runs´ durchlaufen */ 
  for (int counter=1; counter<=runs; counter++)
  {   
    n=completeString.length();
    m=searchString.length();   
    n_m=n-m;   
   
    /* nimm Zeit vorher */
    timeBefore = System.currentTimeMillis();              
   
    /* Präfix-Analyse für KMP */
    /* gehört zum Algorithmus, insofern muss er für die Laufzeitanalyse
       auch so oft aufgerufen werden */

    kmpPraeprocess();       
   
    /* Variablen für erneute Durchläufe zurücksetzen */ 
    result = -1;   
    found = false;
   
    /* eigentlicher KMP-Algorithmus */
    int i=0;
    int j=0;

    /* solange Text noch nicht komplett durchlaufen... */
    while (i < n)
    {
      /* setze j auf das nächste Element im Nextarray,
         solange j>=0 und das Zeichen im Gesamtstring an Stelle i ungleich dem Zeichen
         im Suchstring an Stelle j */

      while ((j >= 0) && (completeString.charAt(i) != 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]; */
      }
    }
   
    if (found)
      result = (i - j);  
   
    /* nimm Zeit danach und bestimme Differenz */
    timeAfter = System.currentTimeMillis();    
    timeDiff  = timeAfter - timeBefore;
   
    /* Zeiten der Gesamttabelle hinzufügen */   
    times.add(timeDiff);
  }      
   
  return result;
}

/*-----------------------------------------------------------------------------
 *  Berechnung des Medians, Erklärung siehe hier:
 *  http://www.mathe-lexikon.at/statistik/lagemasse/median.html
 *-----------------------------------------------------------------------------*/

long calcMedian()
{
  long result=0;
 
  /* um den Median zu berechnen muß die generische Liste sortiert sein */
  Collections.sort(times);
    
  /* testen, ob Anzahl ungerade... */
  if (times.size()%2 != 0)
  {
    /* (da /2 und nicht /2.0 ist es eine Integer-Division) */
    result = times.get((times.size() / 2));
  } else {
    /* für den Feld-Index wird natürlich eine gerade Zahl benötigt.
       Der errechnete Wert soll natürlich nicht abgeschnitten, sondern aufgerundet werden */

    result = Math.round((times.get((times.size()/2)-1) + times.get(times.size()/2)) / 2.0);     
  } 
 
  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!=""))
      { 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="";
      next = new int[0];     
    } else if (keyCode==BACKSPACE)
    {
      if (searchString.length()>0)
      {
        searchString=searchString.substring(0,searchString.length()-1);     
        next = new int[searchString.length()+1];
      }
    } else if (keyCode==ENTER)
    {
      praeProcessing();    
    } else {
      searchString+=key;
      next = new int[searchString.length()+1];           
    }      
  }
}

 

Tag-Wolke

Monats-Liste