Thomas Kramer

IT-COW | All posts tagged 'Modulo'

Der Rabin-Karp-Algorithmus mit 64-Bit-SDBM-Hash-Funktion

By Administrator at Dezember 05, 2011 11:47
Filed Under: Algorithmen, Programmierung allgemein, Studium

Interessehalber habe ich einmal den RK-Algorithmus mit einer alternativen Hash-Funktion getestet - gemäß ntecs.de soll die SDBM-Hash-Funktion vergleichsweise schnell UND einfach zu implementieren sein.

 

Anschließend habe ich die Implementierung der General Purpose Hash Function Algorithms Library verwendet und damit Laufzeittests durchgeführt - auch wenn diese Hash-Funktion sicher vergleichsweise schnell ist, an die rollende Hash-Funktion im Standard-Rabin-Karp-Algorithmus kommt sie naturgemäß um Längen nicht heran - obwohl dort kostenintensives Modulo verwendet wird.

 

Für einen Durchlauf habe ich mit SDBM-Hash-Funktion ungefähr 10 Minuten benötigt, statt weniger als 10 Sekunden mit der rollenden RK-Hash-Funktion. Das liegt eben daran dass mit der rollenden RK-Hash-Funktion der Hash nicht jedesmal komplett neu berechnet, sondern das linkeste Zeichen herausgerechnet und das neue hinzugerechnet werden.

 

Ergänzung 13.12.2011: Es wird nur noch die randomisierte 32-Bit-Variante weiterentwickelt, siehe meinen entsprechenden Blog-Eintrag. Insbesondere beim RAM-Verbrauch wurden Fortschritte erzielt.

 

/* Rabin-Karp-Algorithmus mit SDBM-Hash-Funktion (64-Bit) von Thomas Kramer
   Version 1.01 vom 05.12.2011 */


/* Konfiguration */
   /* Anzahl der Suchdurchläufe */
   int runs = 1; 
   /* 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 completeString="";
String searchString="";
String searchedString="";
boolean fileSelected=false;
int shiftFactor=0;
int searchPosition=0;
String timeString="";
/* fm = false matches, Kollisionen */
int fm = 0; 
long completeTimeDiff   = 0;   
/* generische Liste mit allen Zeiten für jeden einzelnen Durchlauf */
LinkedList <Long> times = new LinkedList <Long> (); 

import java.lang.Math;
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 Rabin-Karp-Algorithmus SDBM 64-Bit", ((screen.width)/2)-350, 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);                       
  }

}

/* SDBM-Hash-Funktion
   Quelle:
   http://gphfa.googlecode.com/svn/trunk/GeneralHashFunctions_-_Java/GeneralHashFunctionLibrary.java */

public long SDBMHash(String str)
{
  long hash = 0;
 
  for(int i = 0; i < str.length(); i++)
  {
    hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
  }

  return hash;
}

/*-----------------------------------------------------------------------------
 *  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 = rabinKarp();   
 
  /* 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(fm + " false matches\n"); 
  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 rabinKarp()
{
  int result = -1; 
  long timeBefore = 0;
  long timeAfter  = 0;
  long timeDiff   = 0; 
  long hs = 0;
  long hsub = 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=Länge des gesamten Textes, m=Länge des Musters */
    n=completeString.length();
    m=searchString.length();  
    n_m=n-m;
   
    /* nimm Zeit vorher */   
    timeBefore = System.currentTimeMillis();   
         
    /* hs=hash-Wert der ersten Zeichen des gesamten Textes */
    hs   = SDBMHash(completeString.substring(0,m));   
    /* hsub=hash-Wert des Musters */
    hsub = SDBMHash(searchString);   

    /* Variablen für erneute Durchläufe zurücksetzen */ 
    result = -1;
    /* in fm werden die Anzahl "False Matches" gespeichert,
       also die Kollisionen */

    fm=0;
    found=false;     
    int i=0;   

    /* solange Text noch nicht komplett durchlaufen... */       
    for (i=0; i<=n_m; i++)
    {        
      /* wenn Hashwert des Musters mit dem Hashwert des Textausschnittes übereinstimmt... */
      if (hs == hsub)
      {
        /* ... und die Strings an der Stelle auch übereinstimmen ... */
        if (completeString.substring(i,i+m).equals(searchString)) 
        {  
          /* Übereinstimmung gefunden */           
          found=true;
          break;  
        } else {
          fm += 1;
        }
      }
           
      /* Bereichsüberlaufsfehler abfangen */
      if ((i + m + 1) > n)
        break;   
      /* nächsten Hashwert bestimmen */
      hs=SDBMHash(completeString.substring(i+1,i+1+m));
    }     
   
    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 (!fileSelected)
      {       
        loadPath = selectInput();      
        fileSelected = true;
      }
    }
   
    if (rect3.pressed()) {
      /* Suche starten */
     if ((fileSelected) && (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;
    }      
  }
}

 

Tag-Wolke

Monats-Liste