Thomas Kramer

IT-COW | All posts tagged 'rolling-hash-function'

Der Rabin-Karp-Algorithmus mit 32-Bit-Arithmetik

By Administrator at November 11, 2011 19:53
Filed Under: Algorithmen, Programmierung allgemein, Studium

Nachfolgend das 32-Bit-Pendant zum Rabin-Karp-Algorithmus. Da die Modulo-Funktion nun nach jeder einzelnen Potenzierung erfolgt ist die Gefahr von Überläufen nicht mehr gegeben, daher sollte die 32-Bit-Version vorgezogen werden - weil die 64-Bit-Version auf 32-Bit-Systemen deutlich langsamer ist.

 

Für die Programm-Historie siehe meinen Beitrag zur 64-Bit-Version.

 

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 (32-Bit) von Thomas Kramer
   Version 1.01 vom 01.12.2011 */


/* Konfiguration */
   /* Basis-Wert: 10 für Zahlensuche verwenden - außer bei Verwendung der bitweisen
      Modulo-Funktion sollte eine Zweierpotenz verwendet werden.
      (Anzahl Buchstaben des Alphabets) */

   int base=257;   
   /* Modulo-Wert für die Hash-Funktion - außer bei Verwendung der bitweisen
      Modulo-Funktion sollte eine Primzahl verwendet werden */

   int q=1024;  
   /* soll die bitweise Modulo-Operation verwendet werden? Erfordert als q eine
      Zweierpotenz - sinnvollerweise sollte dann keinesfalls auch eine Zweier-
      potenz als Basis verwendet werden! Vorgeschlagene Werte in dem Fall:
      Basis 257 und q=1024 */

   boolean useBitModulo = true;
  
   /* Anzahl der Suchdurchläufe */
   int runs = 10; 
   /* Modus bestimmen; true für Textsuche, false für Zahlensuche */
   boolean textSearch=true;     
   /* 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> (); 
/* wenn bitweise Modulo gerechnet werden soll muss q-1 nicht jedes Mal
   neu berechnet werden */

int reducedQ=q-1;

import java.lang.Math;
import java.util.concurrent.TimeUnit;

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

void setup()
{
  /* teste Modulo-Funktionen */ 
  testModulo();
  
  /* Test der Hashfunktionen selbst */
  println("\n");
  testHashFunction();
 
   /* 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 32-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);                       
  }

}

/*-----------------------------------------------------------------------------
 *  teste Modulo-Funktionen
 *-----------------------------------------------------------------------------*/

void testModulo()
{
  /* wenn ich nicht auf bitweise-Modulo-Modus einschränke muss IMMER eine
     Zweierpotenz als Divisor übergeben werden */

  if (useBitModulo)
  {
    /* Modulo-Funktionen testen */
    int cm = customModulo(-14942132);
    int bm = bitModulo(-14942132);
 
    /* Ausgabe */
    System.out.printf("\ncustomModulo bei -14942132 mod %d : %d" ,q, cm);
    System.out.printf("\nbitModulo bei -14942132 mod %d: %d" ,q, bm); 
    if (cm != bm)
    {
      throw new IllegalArgumentException("Fehler, die beiden Modulo-Funktionen ergeben unterschiedliche Werte!");   
    } else {
      println("\nModulo-Funktionalität bei negativen Zahlen ok!");
    }
  }
}

/*-----------------------------------------------------------------------------
 *  Test-Funktion um Übereinstimmung zwischen initialer und rollender Hash-Funktion
 *  sicherzustellen. Stellt vor allem auch sicher dass bei Nutzung der bitweisen
 *  Modulo-Funktion keine Zahl als q übergeben werden kann, die keine Zweierpotenz
 *  darstellt.
 *-----------------------------------------------------------------------------*/

void testHashFunction()
{
  if (textSearch)
  {
    completeString = "WAR and Peace von Leo Tolstoi"
    searchString   = "toi"
  } else {
    completeString = "2359023141526739921"
    searchString   = "39921"
  }

  println("Text:   " + "'" + completeString + "'");
  println("Muster: " + "'" + searchString + "'"); 
     
  /* berechne Hashwert der letzten Zeichen mit der initialen Hash-Funktion */
  int hs1   = hashFirst(completeString.substring(completeString.length()-searchString.length()),
                        searchString.length());   
  /* berechne Hashwert der letzten Zeichen mit der rollenden Hash-Funktion,
     ausgehend vom ersten Hashwert der initialen Hash-Funktion */

  int hs2   = hashFirst(completeString,
                        searchString.length()); 
  for (int i=1;i<=(completeString.length()-searchString.length());i++)
    hs2 = hash(hs2,i,searchString.length());
   
  println("initiale Hash-Funktion: " + hs1);       
  println("rollende Hash-Funktion: " + hs2);  
 
  if (hs1 != hs2)
  {
    throw new IllegalArgumentException("Fehler, initiale- und rollende Hashfunktion ergeben unterschiedliche Werte!");
  } else {
    println("Hash-Funktionalität ok!\n");
    searchString="";
    completeString="";
  }
}

/*-----------------------------------------------------------------------------
 *  initiale Hash-Funktion
 *-----------------------------------------------------------------------------*/

int hashFirst(String searchText, int patternLength)
{
  int result=0;
  if (textSearch)
  {
    int reducedBase=1;
    for (int i=(patternLength-1); i>=0; i--)
    {
      if (i != (patternLength-1))
        reducedBase = customModulo(reducedBase * base); 
        
      result += customModulo(reducedBase * (int) searchText.charAt(i));
      result = customModulo(result);
    }   
    shiftFactor=reducedBase;    
  } else {
    /* für den Zahlensuchmodus wird natürlich eine Basis von 10 benötigt */
   
    /* Verschiebe-Faktor berechnen */
    shiftFactor=1;     
    for (int i=1;i<patternLength;i++)
      shiftFactor=(shiftFactor * base) % q;
   
    /* Zahl ausschneiden */
    result = Integer.parseInt(searchText.substring(0,patternLength)); 
  }    
  return customModulo(result);   
}

/*-----------------------------------------------------------------------------
 *  benutzerdefinierte Modulo-Funktion, um Divisor bei negativem Ergebnis
 *  aufzuaddieren.
 *  Diese Variante arbeitet mit dem Standard-Modulo-Operator (%)
 *-----------------------------------------------------------------------------*/

int customModulo(int x)
{
   int result = x % q;
   if (result < 0)
     result += q;  
   return result;
 
   /* Anmerkung: Es gibt auch noch eine 64-Bit-Modulofunktion:
      64-bit-modulo-> long result = (long) java.lang.Math.IEEEremainder(x, m);
   */

}

/*-----------------------------------------------------------------------------
 *  Diese Modulo-Variante arbeitet bitweise mit dem &-Operator und benötigt daher
 *  als q eine Zweierpotenz
 *-----------------------------------------------------------------------------*/

int bitModulo(int x)
{
  if (!useBitModulo)
    return customModulo(x);
 
   return (x & reducedQ);
}

/*-----------------------------------------------------------------------------
 *  rollende Hash-Funktion
 *-----------------------------------------------------------------------------*/

int hash(int oldHashValue, int startPos, int patternLength)
{
  /* wenn die gesamte Stringlänge kleiner als die des Musters ist, kann das Muster
     nicht vorkommen */

  if (completeString.length() < patternLength)
    return 0;
 
  int result=0;
 
  int intValue;
  int intValue2;
  if (textSearch)
  {
    /* das erste Zeichen von links bestimmen, das wegfällt */
    intValue  = (int) completeString.charAt(startPos-1);
    /* das hinzukommende Zeichen von rechts bestimmen */
    intValue2 = (int) completeString.charAt(startPos+patternLength-1);   
  } else {
    /* das erste Zeichen von links bestimmen, das wegfällt */
    intValue  = Integer.parseInt(completeString.substring(startPos-1,startPos)); 
    /* das hinzukommende Zeichen von rechts bestimmen */
    intValue2 = Integer.parseInt(completeString.substring(startPos+patternLength-1,startPos+patternLength));
  }

//  println(oldHashValue + "-" + intValue + "-" + shiftFactor + "-" + base + "-" + intValue2);   
  result = ((oldHashValue - (intValue * shiftFactor)) * base) + intValue2;
  result = bitModulo(result);
 
  return result; 
}

/*-----------------------------------------------------------------------------
 *  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; 
  int hs = 0;
  int 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   = hashFirst(completeString, m);
    /* hsub=hash-Wert des Musters */
    hsub = hashFirst(searchString, m); 

    /* 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
         (Aufruf der rollenden Hashfunktion */
       
      hs = hash(hs, 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;
    }      
  }
}

 

Monats-Liste