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