Thomas Kramer

IT-COW | Der Rabin-Karp-Algorithmus mit 64-Bit-Arithmetik

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

By Administrator at November 02, 2011 21:10
Filed Under: Algorithmen, Programmierung allgemein, Studium, Java

Wegen des Studiums habe ich nun auch den String-Matching-Algorithmus von Rabin und Karp in Processing implementiert, mit zwei Modi im Programm – einmal für die Suche in Zahlen und einmal für die Suche in Texten.

 

Der Zahlensuchmodus nimmt einfach den numerischen Wert einer Zahl im Text, der Textsuchmodus berechnet den Hashwert von z. B. dem Text “hi” folgendermaßen: 104 * basis^1 + 105 * basis^0, wobei der Wert 104 dem ASCII-Wert des Kleinbuchstabens “h” entspricht.

 

Beide Verfahren berechnen das Ergebnis dann Modulo einer Primzahl. Der Algorithmus benötigt eine modifizierte Modulo-Funktion, denn die Standard-Funktion von Processing/Java liefert einen anderen Wert bei negativen Zahlen. Bei einem negativen Ergebnis der Modulo-Funktion wird daher einfach der Divisor hinzuaddiert.

 

Als Basis-Wert nimmt man bei Dezimalzahlen natürlich 10, bei Texten die Anzahl der Buchstaben des Alphabets – bei ASCII demnach 256. Der Divisor für die Modulo-Funktion sollte eine möglichst hohe Primzahl sein.

 

Der Hashwert der aktuellen Position im Suchtext wird nicht immer neu berechnet sondern eine Formel mit einem vorberechneten Verschiebefaktor auf den vorherigen Hashwert angewandt, so dass Rechenzeit gespart werden kann. Das passende Stichwort dafür lautet rolling hash function. Wenn der Hashwert im Suchtext mit dem des Musters übereinstimmt wird zusätzlich noch der tatsächliche Text an der aktuellen Position verglichen, um Sicherheit zu gewährleisten.

 

Wenn man die erwähnte Vorgehensweise bei Suchen in Texten berücksichtigt ist nachvollziehbar, das schnell an die Grenzen der (32-Bit-) Integerarithmetik gestoßen werden kann. Bei meinen Versuchen mit der verringerten Basis 10 auf Texte kam ich bereits bei einer Patternlänge von genau 11 Zeichen an die Grenzen. Die Signatur/Hashfunktion innerhalb des Rabin-Karp-Algorithmus ist jedoch nicht standardisiert, da gibt es je nach Quelle Unterschiede.

 

Das Wort “development” mit 11 Zeichen konnte ich noch erfolgreich suchen lassen, bei “introduction” mit 12 Zeichen funktionierte es trotz 64-Bit-Integerarithmetik (Datentyp long) bereits nicht mehr (siehe Ergänzung unten vom 05.11.2011). Mittlerweile weiß ich aber einen Trick mit dem auch ein längerer String gesucht werden kann, siehe weiter unten.

 

In Processing/Java gibt es übrigens auch den BigInteger-Datentyp, um diesen in Processing verwenden zu können muss man zuerst die entsprechende Bibliothek mit import java.math.BigInteger; inkludieren – das Syntax-Highlighting von Processing erkennt diesen Datentyp übrigens selbst dann nicht. Ich hatte vorhin damit einmal versuchsweise getestet, aber die Tatsache das die normalen arithmetischen Zeichen */+- nicht darauf angewandt werden können sondern mit Methodenaufrufen wie multiply und divide gearbeitet werden muss macht die Verwendung dieses Datentyps ziemlich umständlich (ein direktes Casten funktioniert übrigens auch nicht).

 

Eine Eigenheit von Processing die mich vorhin etwas Zeit gekostet hat ist das int-Werte (32-Bit-Integer) bei der Funktion println in Festpunktdarstellung ausgegeben werden, long-Werte (64-Bit-Integer) dagegen in Gleitpunktdarstellung – ich dachte zuerst das wären (echte) Fließkommazahlen.

 

Update 03.11.2011: Ich habe noch einige Fehler beseitigt, so wurde zunächst der Hashwert im Suchtext immer komplett neu berechnet statt die andere Routine mit dem Verschiebefaktor zu benutzen, was wegen der Überladung nicht gleich aufgefallen ist.

 

Außerdem muss natürlich die Berechnung des Verschiebefaktors neu erfolgen wenn ein anderes Muster eingegeben wird. Statt die einzelnen Strings in einer Schleife zusammenzufügen benutze ich nun die Funktion join mit dem Trennzeichen \r\n für einen Zeilenumbruch.

 

Bei der Ausgabe der aktuellen Suchposition im Text werden die Zeilenumbrüche mit String.replace(“\r\n”,” “) wieder entfernt und durch Leerzeichen ersetzt.

 

Update 05.11.2011: Die vorherige Grenze von 11 Zeichen für die Patternlänge im Textsuchmodus ließ mich eher auf einen Überlauf innerhalb einer 32-Bit-Arithmetik schließen, trotz durchgängiger Verwendung des 64-Bit long-Datentyps (Integer).

 

Tatsächlich arbeiten sowohl die pow()- also auch die %(Modulo)-Funktion in Processing/Java mit float-Datentypen, also 32-bittig – double wäre der 64-Bit-Datentyp für Fließkommazahlen.

 

Bei meinen Recherchen stieß ich zunächst auf diese alternative Implementierung der pow()-Funktion, die viel schneller sein soll aber bei mir im Test nicht-nachvollziehbare Werte ausgab. Aber es gibt auch eine 64-Bit-Implementierung von pow() in Java, in der java.lang.Math-Bibliothek. Dort ist auch eine alternative Modulo-Funktion für double-Datentypen, IEEEremainder(), definiert.

 

Eine Ganzzahl potenziert mit einer Ganzahl ergibt wieder eine Ganzzahl, so dass ich das Ergebnis von pow() ruhig nach long casten kann.

 

Mit diesen Funktionen arbeitet meine Routine im Textsuchmodus immerhin bis zu einer Patternlänge von 14-15 Zeichen einwandfrei – bei einer Basis von 10. Ich habe nun auch den Grund für die Langsamkeit gefunden, die Stringmanipulationen in der Schleife verlangsamten die Routine um mehr als das 50-fache - diese finden nun danach statt.

 

Weitere Änderungen: Routine nimmt nun die Zeit für eine Laufzeitmessung, für diese musste ich zusätzlich die Bibliothek java.util.concurrent.TimeUnit inkludieren. Für erweiterte Messungen wollte ich mir noch diesen Verweis auf Stopwatch vermerken.

 

Update 06.11.2011: Es wird jetzt die Länge des Suchmusters angezeigt, außerdem wird jetzt auch auf die ENTER und BACKSPACE-Tasten reagiert.

 

Update 07.11.2011: Der Dozent hat uns heute einen Trick verraten mit dem der Hash-Algorithmus mit Patterns beliebiger Länge funktioniert, dafür wird nach jeder einzelnen Potenzierung eine Modulo-Operation durchgeführt, und danach erst multipliziert. Demnach musste ich die Zeilen

 

for (int i=0;i<(patternLength);i++)       
      result += ((long) searchText.charAt(i)) * ((long) java.lang.Math.pow(base,patternLength-i-1));

 

durch

 

long reducedBase=1;
    for (int i=(patternLength-1); i>=0; i--)
    {
      if (i != (patternLength-1))
        reducedBase = customModulo(reducedBase * base, q); 
       
      result += reducedBase * (long) searchText.charAt(i);
    }

 

ersetzen - die rollende Hash-Funktion musste ich dagegen nicht mehr ändern. Als weitere Änderung habe ich außerdem die Funktion testHashFunction() eingebaut, um die Hashwerte der initialen Hash-Funktion und der rollenden Hash-Funktion zu vergleichen.

 

Update 08.11.2011: Damit die Laufzeit des Rabin-Karp-Algorithmus nicht O(n*m) wie bei der naiven Suche erreicht (im Worst Case) hat der Dozent heute die zufällige Verwendung einer Primzahl q gefordert, welche unter q<=8m^2 * log(e,m^2) liegen sollte. Eine Mindestgröße für q hat er nicht genannt, aber nachdem was ich gelesen habe sollte sie zumindest größer als das Muster m sein. Ergänzung 13.11.2011: In dieser Schrift der technischen Universität München wurde auf Seite 77 der Beweis geführt das die Primzahl q größer als n*m sein sollte.

 

Das nennt sich dann "Randomisierter Rabin-Karp-Algorithmus", wie in der Quelle der Harvard-Universität erläutert. q sollte dann bei zuvielen "false matches" oder bei jedem n-ten Schleifendurchlauf neu erzeugt werden, wobei die Erzeugung von Primzahlen natürlich auch Zeit kostet. Die Laufzeit der randomisierten Variante beträgt gemäß Dozent O(m + n + 1/m * m * n).

 

Andere Variante: Ich habe nun - wie in der Harvard-Quelle erläutert - als Basis 257 genommen und für q 1024, sowie die customModulo-Funktion anders realisiert: Wenn q eine Zweierpotenz ist kann die Modulo-Funktion über eine bitweise &-Verknüpfung realisiert werden, was wesentlich schneller ist - die Basis darf dann aber keinesfalls auch eine Zweierpotenz sein.

 

Siehe hier, mod(16, 4) kann eben auch durch

 

int a=16;

int b=a & (4-1);

 

erreicht werden. Dahingehend angepasst habe ich vorhin Performance-Tests vorgenommen - angewandt auf das Buch Krieg und Frieden von Tolstoy, welches ich 5x untereinander in die gleiche Datei kopiert habe - und mit einem eindeutigen Muster am Ende dieser Datei. Ergebnisse meiner Laufzeittests:

 

  • mit 32-Bit-Modulo-Funktion (%): ca. 2,5 Sekunden im Schnitt
  • mit 64-Bit-Modulo-Funktion (IEEEremainder): ca. 9 Sekunden im Schnitt
  • mit bitweise Modulo-Funktion: 0,8 - 1,1 Sekunden im Schnitt

 

Testsystem ist ein Turion 64x2 mit 1,6 GHZ - die starken Geschwindigkeitsunterschiede liegen hauptsächlich darin begründet das auf diesem System lediglich ein 32-Bit-Betriebssystem läuft.

 

Update 11.11.2011: Die Testfunktion am Anfang, die die Ergebnisse der initialen und rollenden Hash-Funktionen miteinander vergleicht, gibt nun eine Exception aus wenn die Werte voneinander abweichen und verhindert so einen Start des Programms. Auf diese Weise wird auch sichergestellt dass bei Verwendung der bitweisen Modulo-Operation nur eine Zweierpotenz als Divisor übergeben werden kann.

 

Außerdem wird die Laufzeitmessung nun nicht nur einmal, sondern x-mal gemäß der Parameter-Konfiguration am Anfang des Programms vorgenommen und in einer generischen Liste gespeichert – anschließend wird der Median als Mittelwert gebildet, welcher gegenüber dem normalen arithmetischen Mittel Extremwerte ausschließt.

 

Als weitere Konsolenausgaben werden nun die maximale Zeitdifferenz zwischen Minimum und Maximum sowie die Anzahl der false Matches ausgegeben - der Kollisionen, bei denen eine Übereinstimmung zwischen den Hash-Werten, aber nicht dem eigentlichen Text besteht.

 

Eine separate Funktion zur Berechnung des Verschiebefaktors ist nun auch nicht mehr nötig, dies passiert nun bereits in der initialen Hash-Funktion. Dort wird nun nach jeder Rechenoperation eine Modulo-Operation durchgeführt, um die Gefahr von Überläufen noch weiter zu minimieren – im Präprozessing ist dies performancetechnisch irrelevant, nur die rollende Hash-Funktion ist performancekritisch.

 

Im Allgemeinen halte ich nun übrigens diese 64-Bit-Variante für überflüssig, es besteht auch sonst sogut wie keine Gefahr von Überläufen mehr – und auf 32-Bit-Systemen sorgt sie für eine deutlich längere Verarbeitungszeit. Ich habe auch recherchiert ob man Überläufe wohl generell abfangen kann - hier gibt es dazu zwei interessante Ansätze, aber regulär ist das nicht möglich.

 

Übrigens ist der zuvor beschriebene naive Algorithmus bis jetzt immer schneller als der (64 Bit- und 32 Bit-) Rabin-Karp-Algorithmus gewesen, obwohl man gemäß der Wikipedia-Übersicht davon ausgehen müsste das der RK-Algorithmus im Mittel dominiert - das müsste an der teuren Modulo-Funktion im rollenden Hash-Algorithmus liegen, der Performance-Gewinn bei der bitweisen Modulo-Operation beweist das sie große Einflüsse auf die Performance nimmt.

 

Mit größeren Suchpatterns müsste der nicht-randomisierte RK-Algorithmus im Vergleich zur naiven Variante vorneliegen, da die durchschnittliche Anzahl der Operationen O(n+m) statt O(n*m) wie beim naiven Algorithmus beträgt. Interessant wäre noch herauszufinden, ab welcher Länge der Suchpatterns und in welcher Art Texten (false matches) der RK-Algorithmus regelmäßig vorne liegt.

 

Mittlerweile stört mich doch etwas der fehlende Komfort von Processing, vor allem eine Befehlsvervollständigung fehlt mir – deswegen notiere ich mir an dieser Stelle auch einmal die Seite bei Oracle für Listen; der allgemeine Einstiegspunkt für die Java-API-Dokumentation befindet sich auf dieser Seite. Hilfreich waren mir auch diese und diese Seiten über Generics in Java, außerdem bin ich zufällig darauf gestoßen das die LinkedList in Java ca. 33x schneller sein soll als die ArrayList, gemäß dem Frickelblog.

 

Bezüglich des Quellcodes versuche ich mich nun durchgängig an PascalCase für Klassennamen und CamelCase für sonstige Bezeichner zu halten, gemäß den Java-Coding Style Guidelines. Bei den Einrückungsstilen bevorzuge ich den Allman-Stil, mit einer Ausnahme: Bei den else-Zweigen einer if-Abfrage fände ich drei Zeilen schon etwas verschwenderisch.

 

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.

 

Die eigentliche RK-Routine gab immer 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 muss man für die interne Bearbeitung immer mit –1 rechnen. Der Algorithmus gibt nun außerdem -1 zurück für den Fall dass das Suchpattern nicht gefunden wurde, damit verfolge ich nun das Konzept der Magic Numbers.

 

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 01.12.2011: Ich habe noch einen Fehler gefunden der aber irrelevant war weil er niemals auftrat. Bei der customModulo-Funktion (%) hatte ich bei einem Ergebnis<0 immer q auf das Ergebnis draufaddiert und diese Arbeitsweise auch auf die bitModulo-Funktion übernommen - bei dieser kann aber kein negatives Ergebnis herauskommen. Jedenfalls hätte ich dort bei einem negativen Ergebnis q und nicht q-1 draufaddieren müssen, aber diesen Block habe ich nun entfernt da er eh nie ausgeführt werden würde.

 

Außerdem ist nun ein weiterer Test im Quellcode enthalten, der die beiden Modulo-Funktionen auf Übereinstimmung testet - welcher aber nur ausgeführt wird wenn bitweise-Modulo-Operation aktiviert ist, weil ansonsten IMMER eine Zweierpotenz als q übergeben werden muss.

 

Update 08.22.2011: In der Version unten habe ich es noch nicht drin, aber der Speicherverbrauch kann noch etwas optimiert werden indem der Stringbuilder bereits mit der finalen Größe initialisiert wird:

 

File file = new File(loadPath);
  int fileLength = (int) file.length();  
  file = null;
 
  if (useStringBuilder)
  {     
    StringBuilder sb = new StringBuilder(fileLength); 

 

Außerdem habe ich für die Anzeige des Suchfensters jeweils die Zeilenumbrüche entfernen lassen, denn diese sind natürlich je nach System unterschiedlich. So wäre es vollständig:

 

searchedString = searchedString.replace("\r\n"," ");
searchedString = searchedString.replace("\n"," "); 

 

Die Reihenfolge ist hierbei wichtig.

 

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.

 

Literaturverweise

 

Bei der FH Flensburg haben sie den Rabin-Karp-Algorithmus über zwei separate Methoden implementiert; einmal in Präprozessing und eigentlichem Suchalgorithmus separiert und Multiplikationen mit den Java-Schiebeoperatoren durchgeführt.

 

Im Buch Algorithmen - Eine Einführung haben sie dagegen diese beiden Teile in die gleiche Routine programmiert - diese müsste auf Seite 1005 aufgelistet sein, online wird sie leider nicht angezeigt - bei meiner Auflage ist es auf Seite 917.

 

Ein Beispiel für den randomisierten Rabin-Karp-Algorithmus gibt es hier auf der Seite der Hochschule der angewandten Wissenschaften Hamburg. Interessant auch dieser Vortrag über randomisierte Algorithmen der Uni Dortmund.

 

In diesem Link der Harvard-Universität wird ein Weg aufgezeigt den Algorithmus zu verschnellern. Man lese dazu den Abschnitt "Speeding Up Rabin-Karp - Avoiding the Modulo-Operation", in der vorgeschlagen wird als Basis den Wert 257 und als Divisor eine hohe Zweierpotenz zu nehmen und anschließend den Modulo bitweise zu berechnen, wie weiter oben beschrieben.

 

Eine Übersicht der Laufzeiten der verschiedenen Suchalgorithmen - inklusive des Rabin-Karp-Algorithmus - gemäß der O-Notation ist auf der Wikipedia-Seite zum Stichwort String-Matching-Algorithmus zu finden.

 

Auf ntecs.de gibt es auch eine interessante Übersicht über verschiedene Hash-Funktionen - in der General Purpose Hash Function Algorithms Library sind weitere Varianten im Java-Code vorliegend. Speziell die rollende Hash-Funktion im RK-Algorithmus ist aber schon sehr schnell.

 

Weitere Links:

 

  • Wikipedia: Link
  • Buch Algorithmen – Eine Einführung: Link
  • Vortrag der Uni Bielefeld dazu: Link
  • Erklärung der Hochschule Karlsruhe inkl. Visualisierung: Link
  • Weitere Binär-Tricks: Link
  • Skript zur Vorlesung Algorithmische Bioinformatik der TU München: Link

 

/* Rabin-Karp-Algorithmus (64-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;
long 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 */

long 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 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);                       
  }
}

/*-----------------------------------------------------------------------------
 *  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 */
    long cm = customModulo(-14942132);
    long 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 */
  long 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 */

  long 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
 *-----------------------------------------------------------------------------*/

long hashFirst(String searchText, int patternLength)
{
  long result=0;
  if (textSearch)
  {
    long reducedBase=1;
    for (int i=(patternLength-1); i>=0; i--)
    {
      if (i != (patternLength-1))
        reducedBase = customModulo(reducedBase * base); 
       
      result += customModulo(reducedBase * (long) 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 = Long.parseLong(searchText.substring(0,patternLength)); 
  }
  return customModulo(result);   
}

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

long customModulo(long x)
{
   /* int result = x % q; */
   long result = (long) java.lang.Math.IEEEremainder(x, q);
   if (result < 0)
     result += q;  
   return result;
}

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

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

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

long hash(long 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;
 
  long result=0;
 
  long longValue;
  long longValue2;
  if (textSearch)
  {
    /* das erste Zeichen von links bestimmen, das wegfällt */
    longValue  = (long) completeString.charAt(startPos-1);
    /* das hinzukommende Zeichen von rechts bestimmen */
    longValue2 = (long) completeString.charAt(startPos+patternLength-1);   
  } else {
    /* das erste Zeichen von links bestimmen, das wegfällt */
    longValue  = Long.parseLong(completeString.substring(startPos-1,startPos)); 
    /* das hinzukommende Zeichen von rechts bestimmen */
    longValue2 = Long.parseLong(completeString.substring(startPos+patternLength-1,startPos+patternLength));
  }

  //  println(oldHashValue + "-" + intValue + "-" + shiftFactor + "-" + base + "-" + intValue2);       
  result = ((oldHashValue - (longValue * shiftFactor)) * base + longValue2);
  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; 
  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   = 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;
    }      
  }
}

 

Pingbacks and trackbacks (1)+

Kommentar schreiben




  Country flag
biuquote
  • Kommentar
  • Live Vorschau
Loading


Monats-Liste