Thomas Kramer

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

Der randomisierte Rabin-Karp-Algorithmus mit bitweiser Modulo-Operation

By Administrator at Dezember 05, 2011 13:38
Filed Under: Algorithmen, Java, Programmierung allgemein, Studium

Nachfolgend mein Quellcode zur randomisierten Rabin-Karp-Variante - es wird nur noch die schnellere bitweise Modulo-Operation und entsprechend als q eine zufällige Zweierpotenz zwischen 2^10 und 2^31 (int-Maximum) gewählt - der Threshold (nach wievielen false matches soll q neu gewählt werden) kann frei festgelegt werden.

 

Die Bandbreiten der Zufallszahlen sind durch die Zweierpotenzen natürlich gering.

 

Für das Potenzieren wird nicht pow() benutzt sondern die Java-Schiebeoperatoren, welche schneller sind - diesbezüglich wollte ich mir auch mal dieses Zitat der FH Flensburg vermerken, dass ich damals gefunden hatte:

 

"Die Multiplikation mit 2 wird durch eine Linksschiebe-Operation realisiert. Die Multiplikation mit 2m-1 kann nicht durch Linksschieben um m-1 realisiert werden, jedenfalls nicht, wenn m>=32 ist. In der 32-Bit-Arithmetik von Java werden Schiebe­distanzen modulo 32 gerechnet. Statt z.B. um 34 würde also um 2 geschoben werden. Es wird daher eine Variable h = 2m-1 mod 232 benötigt. Die Operation mod 232 wird implizit durch die 32-Bit-Zahlen­darstellung bewirkt."

 

Quelle: Link. Im Skript der Technischen Universität München steht zum RK-Algorithmus auf Seite 75 außerdem:

 

„Die Zahl, durch welche modulo gerechnet wird, sollte teilerfremd zu |Σ| sein, da ansonsten Anomalien auftreten können. Wählt man beispielsweise eine Zweierpotenz, so werden nur die ersten Zeichen des Suchwortes berücksichtigt, wo hingegen die letzten Zeichen des Suchwortes bei dieser Suche überhaupt keine Relevanz haben. Um unabhängig von der Alphabetgröße die Teilerfremdheit garantieren zu können, wählt man p als eine Primzahl."

 

Wenn man entsprechend dem Link der Harvard-Universität als q eine Zweierpotenz nimmt (damit man mittels bitweiser &-Operation Modulo berechnen kann) darf als Basis=|Σ| keinesfalls ebenfalls eine Zweierpotenz genommen werden - der Link empfiehlt als Basis dann 257 statt 256. Bei den Einstellungen sollte man das berücksichtigen.

 

Update 07.12.2011: Diese Variante ermittelt nun auch die Zeit die es zum Laden benötigt. Dazu hatte ich gemäß den Quellen 1 und 2 damit experimentiert ob es einen Unterschied macht ob man den Stringbuilder mit einem passenden Längen-Wert initialisiert. Außerdem wird nun der Separator ausgelesen aus den System-Eigenschaften.

 

Update 08.12.2011: Unten war noch ein Fehler enthalten, der Stringbuilder wurde mit der Größe der Patterndatei statt der Gesamtdatei initialisiert.

 

Update 09.12.2011: Den StringBuilder mit der genauen Dateigröße zu initialisieren reicht (beim zeilenweisen Einlesen) leider nicht aus um RAM-intensive Umkopieraktionen zu vermeiden, siehe meine Tests im Blog-Eintrag bezüglich eines Vergleiches von vier Varianten zum Datei-Laden.

 

Ich habe nun die Variante mit dem blockweisen Einlesen in diese Rabin-Karp-Implementierung übernommen, der Vorteil ist neben einem geringeren RAM-Verbrauch auch dass die Suchposition des Musters immer korrekt angegeben wird – unabhängig davon ob in einer Ein-Zeichen-Zeilenumbruchsdatei oder einer Zwei-Zeichen-Zeilenumbruchsdatei gesucht wird. Schließlich hatte ich vorher beim zeilenweisen Einlesen IMMER einen Zwei-Zeichen-Zeilenumbruch im RAM ergänzt, egal wie es in der Datei selbst gemanagt wurde.

 

Außerdem wird um eine weitere Umkopieraktion zu vermeiden nun nicht mehr vom StringBuilder auf einen String mit der Methode .tostring() zugewiesen, was gemäß meiner Tests ebenfalls RAM-intensiv war.

 

Generelles zum RAM-Verbrauch: Da Java intern 16-Bit-Unicode (UTF-16) verwendet ist der Verbrauch im RAM mindestens 2x so hoch wie die eigentliche Datei, wenn die Datei nur eine 8-Bit-Codierung verwendet.

 

Außerdem wollte ich mir die Links von wsoftware.de bezüglich Verwendung von Character-Sets und der Angabe des Encodings bei StreamReadern in Java vermerken. Vielleicht ist auch diese generelle Übersicht über Encodings hilfreich. Zeichensatzkonvertierungen kann man unter Linux übrigens mit dem iconv-Befehl durchführen.

 

Übrigens hatte ich in bisher jeder Variante das Schliessen des BufferedReaders nach dem Einlesen vergessen, das ist hier nun auch enthalten.

 

Update 13.12.2011: Die Zufallszahlenroutine war potenziell langsam, daher habe ich sie durch eine andere ohne explizitem int-Cast ersetzt - siehe meinen Vergleichstest. Außerdem wird nun auch die Anzahl der q-Wechsel angezeigt.

 

Update 25.02.2012: Bezüglich des nachfolgenden Code-Fragments:

 

/* wähle q neu - eine Zweierpotenz zwischen 2^minQ bis 2^maxQ */
randomNumber = randomNumbers.nextInt(qDiff) + minQ;
/* Schiebeoperatoren sind schneller */                         
q = minQResult << (randomNumber - minQ)

 

Einmal +minQ, einmal -minQ und die Variable randomNumber wird sonst nicht weiter verwendet - das hebt sich natürlich gegenseitig auf und ist überflüssig.

 

/* randomisierter Rabin-Karp-Algorithmus (32-Bit) von Thomas Kramer
   Version 1.21 vom 13.12.2011 */


/* Konfiguration */
   /* Basis-Wert: 10 für Zahlensuche verwenden
      (Anzahl Buchstaben des Alphabets) */

   int base = 257;   
   /* initialer Modulo-Wert für die Hash-Funktion */
   int q = 1024;    
   /* ab wievielen false matches soll q neu gewählt werden?
      0 = Zufallsmodus ausschalten */

   int fmThreshold = 1000;
   /* Unter- und Obergrenze von q festlegen, z. b. 2^10 - 2^31
      2^31 ist bereits das Maximum für einen int */
  
   int minQ = 10;
   int maxQ = 31;  
  
   /* 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="";     
  
   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 */

// systemeigenes Zeilenumbruchszeichen ermitteln
String sep = System.getProperty("line.separator");       
color currentcolor;
RectButton rect1,rect2,rect3;
boolean locked = false;
String loadPath="";
StringBuilder completeString=new StringBuilder(0);
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;   
int minQResult = 0;
int qDiff=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;
int qChanges = 0;

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

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

void setup()
{   
  /* Test der Hashfunktionen selbst */
  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);     
 
  /* Minimum für q berechnen, pow ist relativ rechenzeitintensiv */ 
  minQResult = (int) pow(2, minQ); 
  qDiff = maxQ - minQ + 1;

  /*-----------------------------------------------------------------------------
   *  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!");
     
    searchString = loadFile(patternFile).toString();
  }
}

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

StringBuilder loadFile(String fileName)
{       
  /* nimm die Vorher-Zeit für Gesamtdurchlauf */   
  long completeTimeBefore = System.currentTimeMillis();       
 
  File file = new File(fileName);
  int fileLength = (int) file.length();  
  file = null;
 
  StringBuilder result = new StringBuilder(fileLength);            
  try
  {
    char[] ioBuf = new char[1000];     
    /* buffer liefert Anzahl gelesener Zeichen zurück, siehe auch
       http://www.dpunkt.de/java/Referenz/Das_Paket_java.io/4.html#read%28%29 */
 
    int buffer = 0;   
   
    BufferedReader br = new BufferedReader(new FileReader(fileName));     
    while ((buffer = br.read(ioBuf,0,1000)) == 1000)      
    {
      /* eingelesene Zeile anhängen */
      result.append(ioBuf);
      /* Array wieder leeren falls nur weniger Zeichen eingelesen werden können */
      ioBuf = new char[1000];             
    }
    /* die letzten gelesenen Zeichen müssen auch hinzugefügt werden */
    /* -1 wäre wenn von vornherein gar kein Zeichen eingelesen werden konnte */
    if (buffer != -1)
    {
      for (int i=0;i<buffer;i++)
        result.append(ioBuf[i]);
    }
    br.close();
  } catch (IOException e)
  {
    println("Datei konnte nicht (vollständig) eingelesen werden!");
  }            
 
  /* nimm die Danach-Zeit für Gesamtdurchlauf und bestimme Differenz */   
  long completeTimeAfter = System.currentTimeMillis();     
  long completeTimeDiff   = completeTimeAfter - completeTimeBefore;       
  println(completeTimeDiff + " ms Zeit benötigt zum Datei-Laden.\n"); 
 
  return result;
}

/*-----------------------------------------------------------------------------
 *  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 rand. Rabin-Karp-Algorithmus 32-Bit", ((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);                       
  }

}

/*-----------------------------------------------------------------------------
 *  Test-Funktion um Übereinstimmung zwischen initialer und rollender Hash-Funktion
 *  sicherzustellen.
 *-----------------------------------------------------------------------------*/

void testHashFunction()
{
  completeString.setLength(0); 
  if (textSearch)
  {
    completeString.append("WAR and Peace von Leo Tolstoi"); 
    searchString   = "toi"
  } else {
    completeString.append("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.substring(0,searchString.length()),
                        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.setLength(0);
  }
}

/*-----------------------------------------------------------------------------
 *  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 = bitModulo(reducedBase * base); 
        
      result += bitModulo(reducedBase * (int) searchText.charAt(i));
      result = bitModulo(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=bitModulo(shiftFactor * base);
   
    /* Zahl ausschneiden */
    result = Integer.parseInt(searchText.substring(0,patternLength)); 
  }    
  return bitModulo(result);   
}

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

int bitModulo(int 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 */
  completeString.setLength(0);
  completeString = loadFile(loadPath);
 
  /* 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.substring(0);               
    }
  } 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"," ");
  searchedString = searchedString.replace("\n"," "); 
  if (cutted)
    searchedString=searchedString + " [..]";                
   
  /* Konsolenausgaben */
  /* die sind deswegen hier drin weil sie in draw() immer wieder aufgerufen werden würden */
  println("q-Wechsel: " + qChanges);     
  println(fm + " false matches nach letztem q-Wechsel\n"); 
  println("\nAlle 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));  
                
  /* aktuelles q ausgeben */
  println("aktuelles q: " + q); 
}

/*-----------------------------------------------------------------------------
 *  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 randomNumber = 0;
  int hs = 0;
  int hsub = 0;
  int n = 0;
  int m = 0;
  int n_m = 0;
  qChanges = 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.substring(0, m), m);
    /* hsub=hash-Wert des Musters */
    hsub = hashFirst(searchString, m); 

    /* da die Zufallszahlenerzeugung für die rand. RK-Algorithmus essentiell ist,
       messen wir die Instanziierung des Random-Objekts natürlich jeweils mit */

    Random randomNumbers = new Random();
    /* 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;
          if (fmThreshold != 0)
          {
            if (fm == fmThreshold)
            {
              /* wähle q neu - eine Zweierpotenz zwischen 2^minQ bis 2^maxQ */
              randomNumber = randomNumbers.nextInt(qDiff) + minQ;
              /* Schiebeoperatoren sind schneller */                          
              q = minQResult << (randomNumber - minQ);
              reducedQ = q - 1;                                         
              /* false matches zurücksetzen */
              fm = 0;
              qChanges++;

              /* mit neuem q muss Hash für Muster und Gesamtstring auch neu berechnet werden */             
              hsub = hashFirst(searchString, m);              
              hs   = hashFirst(completeString.substring(i, i + m), m);            
            }
          }
        }
      }
           
      /* Bereichsüberlaufsfehler abfangen */
      if ((i + m + 1) > n)
        break;   
      /* nächsten Hashwert bestimmen */       
      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;
    }      
  }
}

 

Tag-Wolke

Monats-Liste