Thomas Kramer

IT-COW | All posts tagged 'Delphi'

Der naive String-Matching-Algorithmus

By Administrator at Oktober 18, 2011 21:00
Filed Under: Algorithmen, Programmierung allgemein, Studium

Für die Fachhochschule sollte ich den naiven String-Matching-Algorithmus implementieren; bezüglich der Funktionsweise und den Laufzeiten gemäß der O-Notation siehe diesen Beitrag der FH Flensburg sowie der Wikipedia, oder auch allgemein meinen älteren Beitrag.

 

Die Implementierung habe ich wieder in Processing vorgenommen - wobei dieses System für richtige GUIs eher ungeeignet ist, da Elemente wie Buttons u. ä. nicht direkt verfügbar sind. Die Frage ist daher, ob ich die anderen String-Matching-Algorithmen auch noch in Processing implementieren werde.

 

Es gibt zwei Buttons, den FileOpen- und den Start-Button; das zu suchende String-Pattern kann eingegeben werden sobald das Processing-Fenster den Fokus hat. Zeilenumbrüche werden allgemein herausgefiltert und zu Leerzeichen umgewandelt, so das die gesamte Textdatei in einen einzelnen String aufgenommen wird.

 

Das Search-Pattern kann mit Druck auf die Entfernen-Taste zurückgesetzt werden.

 

Bezüglich des Algorithmus noch eine Ergänzung in Bezug auf ältere Lehrbücher. Speziell in Delphi/Pascal fängt der Index von Strings bei 1 statt 0 an zu zählen, ich zitiere:

 

We can use any string variable as an array of characters, the second character in s has the index 2. The following code s[2]:='T'; assigns T to the second character of the s variable.

 

Quelle: Link. Da es einige Lehrbücher gibt die auf Pascal setzen sollte man hierbei aufpassen, denn in Java oder C ist das anders.

 

Update 02.11.2011: Für erneute Suchdurchläufe müssen natürlich die Variablen completeString und searchedString zunächst zurückgesetzt werden; außerdem kann bei der substring-Zuweisung an searchedString nun kein Bereichsüberschreitungsfehler mehr auftreten da ich nur noch den BeginIndex-Parameter benutze und danach erst abschneide.

 

Wenn das SearchPattern nicht gefunden wird, wird das nun auch konkret angezeigt.

 

Update 03.11.2011: Statt den eingelesenen Text aus dem Array über eine Schleife in einen einzigen String zu überführen benutze ich nun die Join-Funktion join(lines,"\r\n"). Für die Anzeige des aktuellen Suchausschnittes werden die Zeilenumbrüche über die Methode String.replace("\r\n"," ") wieder entfernt.

 

Update 05.11.2011: Laufzeitmessung eingebaut. Außerdem habe ich nun den Grund für die Langsamkeit behoben, die Stringmanipulationen in der Schleife verlangsamten die Routine um mehr als das 50-fache.

 

Update 12.11.2011: Wegen besserer Vergleichbarkeit zum Rabin-Karp-Algorithmus werden nun auch hier mehrere Suchdurchläufe gestartet und der Median aus den Ergebnissen gebildet.

 

Update 13.11.2011: Für den Fall dass das Suchpattern gefunden wurde zeigt das Programm die ersten 100 nachfolgenden Zeichen ab der Suchposition an. Dafür hatte ich zuerst dem searchedString den kompletten Text zugewiesen und dann abgeschnitten, was natürlich unvernünftig ist weil damit unnötig Speicher alloziert wird der gar nicht benötigt wird.

 

Dies habe ich nun geändert, außerdem gab es an der Stelle noch einen Fehler wenn das Suchpattern gar nicht gefunden wurde. Die eigentliche RK-Routine gab Suchposition +1 zurück damit er für die Anzeige ab 1 anfängt zu zählen, aber das ist ebenfalls unvernünftig denn dann muß man für die interne Bearbeitung immer mit –1 rechnen. Beides geändert.

 

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 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.

 

/* Naiver Textsuch-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;   
/* 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;      
  }
}

/*-----------------------------------------------------------------------------
 *  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 naive String-Matching-Algorithmus", ((screen.width)/2)-400, 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 = naiveSearch(); 
 
  /* 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));      
}

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

int naiveSearch()
{
  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();              
   
    /* Variablen für erneute Durchläufe zurücksetzen */ 
    result = -1;   
    found = false;
    int i=0;   
    int j=0;   
   
    /* solange Text noch nicht komplett durchlaufen... */   
    for (i=0; i<=n_m; i+=1)
    {    
      /* inkrementiere j solange j<m und das Zeichen im Suchstring an der Stelle j ungleich dem
         Zeichen im Gesamtstring an Stelle i+j */

      j=0;
      while ((j < m) && ((int) searchString.charAt(j) == (int) completeString.charAt(i+j)))
        j+=1;

      /* Übereinstimmung gefunden */     
      if (j == m)
      {
        found=true;
        break;
      }
    }    
   
    if (found)
      result = i;  
   
    /* 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="";
    } else if (keyCode==BACKSPACE)
    {
      if (searchString.length()>0)
        searchString=searchString.substring(0,searchString.length()-1);     
    } else if (keyCode==ENTER)
    {
      praeProcessing();    
    } else {
      searchString+=key;
    }      
  }
}

 

Monats-Liste