Interessehalber habe ich einmal den RK-Algorithmus mit einer alternativen Hash-Funktion getestet - gemäß ntecs.de soll die SDBM-Hash-Funktion vergleichsweise schnell UND einfach zu implementieren sein.
Anschließend habe ich die Implementierung der General Purpose Hash Function Algorithms Library verwendet und damit Laufzeittests durchgeführt - auch wenn diese Hash-Funktion sicher vergleichsweise schnell ist, an die rollende Hash-Funktion im Standard-Rabin-Karp-Algorithmus kommt sie naturgemäß um Längen nicht heran - obwohl dort kostenintensives Modulo verwendet wird.
Für einen Durchlauf habe ich mit SDBM-Hash-Funktion ungefähr 10 Minuten benötigt, statt weniger als 10 Sekunden mit der rollenden RK-Hash-Funktion. Das liegt eben daran dass mit der rollenden RK-Hash-Funktion der Hash nicht jedesmal komplett neu berechnet, sondern das linkeste Zeichen herausgerechnet und das neue hinzugerechnet werden.
Ergänzung 13.12.2011: Es wird nur noch die randomisierte 32-Bit-Variante weiterentwickelt, siehe meinen entsprechenden Blog-Eintrag. Insbesondere beim RAM-Verbrauch wurden Fortschritte erzielt.
/* Rabin-Karp-Algorithmus mit SDBM-Hash-Funktion (64-Bit) von Thomas Kramer
Version 1.01 vom 05.12.2011 */
/* Konfiguration */
/* Anzahl der Suchdurchläufe */
int runs = 1;
/* Patterndatei verwenden für längere Suchmuster, auf "" setzen wenn Eingabe
von Hand gewünscht. Forwardslash / verwenden, gemäß
http://docs.oracle.com/javase/tutorial/essential/environment/sysprop.html
wird in Java plattformspezifisch eh automatisch umgewandelt */
// String patternFile="C:/Users/thomas/Downloads/m1.TXT";
String patternFile="";
/* StringBuilder fürs Laden verwenden (braucht weniger RAM) ja/nein */
boolean useStringBuilder=true;
color buttoncolor = color(102);
color highlight = color(51);
color c1 = color(0, 0, 0);
color c2 = color(255, 255, 255);
color c3 = color(193, 185, 185);
/* Konfiguration-Ende */
color currentcolor;
RectButton rect1,rect2,rect3;
boolean locked = false;
String loadPath="";
String completeString="";
String searchString="";
String searchedString="";
boolean fileSelected=false;
int shiftFactor=0;
int searchPosition=0;
String timeString="";
/* fm = false matches, Kollisionen */
int fm = 0;
long completeTimeDiff = 0;
/* generische Liste mit allen Zeiten für jeden einzelnen Durchlauf */
LinkedList <Long> times = new LinkedList <Long> ();
import java.lang.Math;
import java.util.concurrent.TimeUnit;
/*-----------------------------------------------------------------------------
* Initialisierungen
*-----------------------------------------------------------------------------*/
void setup()
{
/* Größe des Screens setzen */
size(screen.width-400, 300);
/* Bildschirm löschen */
background(c3);
/* Buttons instanziieren */
rect1 = new RectButton(((screen.width)/2)-400, 130, 50, 20, buttoncolor, highlight);
rect2 = new RectButton(((screen.width)/2)-400, 152, 380, 20, buttoncolor, highlight);
rect3 = new RectButton(((screen.width)/2)-400, 175, 50, 20, buttoncolor, highlight);
/*-----------------------------------------------------------------------------
* Patternfile laden
*-----------------------------------------------------------------------------*/
patternFile = trim(patternFile);
if (patternFile != "")
{
File f = new File(patternFile);
if (!f.exists())
throw new IllegalArgumentException("Fehler, Patterndatei ist angegeben und existiert nicht!");
String lines[] = loadStrings(patternFile);
searchString=trim(join(lines,"\r\n"));
lines = null;
}
}
/*-----------------------------------------------------------------------------
* Datei laden
*-----------------------------------------------------------------------------*/
void loadFile()
{
if (useStringBuilder)
{
StringBuilder sb = new StringBuilder();
try
{
String thisLine=null;
BufferedReader br = new BufferedReader(new FileReader(loadPath));
while ((thisLine = br.readLine()) != null)
{
/* eingelesene Zeile anhängen */
sb.append(thisLine);
/* Zeilenumbruch hinzufügen */
sb.append("\r\n");
}
} catch (IOException e)
{
println("Error: " + e);
}
completeString = sb.toString();
sb.setLength(0);
sb = null;
} else {
String lines[] = loadStrings(loadPath);
completeString=trim(join(lines,"\r\n"));
lines = null;
}
}
/*-----------------------------------------------------------------------------
* draw()-Funktion wird aufgerufen wenn der Bildschirm neu gezeichnet wird
*-----------------------------------------------------------------------------*/
void draw()
{
/*-----------------------------------------------------------------------------
* Hintergrundfarbe setzen, dabei wird auch der gesamte Bildschirm gelöscht
*-----------------------------------------------------------------------------*/
background(c3);
/*-----------------------------------------------------------------------------
* Überschriften setzen
*-----------------------------------------------------------------------------*/
fill(c2);
textSize(20);
text("Der Rabin-Karp-Algorithmus SDBM 64-Bit", ((screen.width)/2)-350, 50);
textSize(15);
text("von Thomas Kramer", ((screen.width)/2)-270, 80);
text("(ESC zum Abbrechen)", ((screen.width)/2)-275, 110);
textSize(13);
/*-----------------------------------------------------------------------------
* Buttons setzen und beschriften
*-----------------------------------------------------------------------------*/
rect1.display();
if (patternFile == "")
{
rect2.display();
} else {
fill(c2);
text(patternFile, ((screen.width)/2)-398, 167);
}
rect3.display();
update(mouseX, mouseY);
text("FileOpen: ", ((screen.width)/2)-485, 145);
text("SearchString: ", ((screen.width)/2)-485, 167);
text("Start ", ((screen.width)/2)-485, 190);
/*-----------------------------------------------------------------------------
* Eingabetexte, Statusmeldungen etc. setzen
*-----------------------------------------------------------------------------*/
/* weiße Schriftfarbe setzen */
fill(c2);
/* anzeigen des Suchstrings */
if ((patternFile == "") && (searchString != ""))
text(searchString, ((screen.width)/2)-398, 167);
text(searchString.length() + " Bytes Länge", ((screen.width)/2), 167);
/* ausgewählte Datei anzeigen */
if (loadPath!=null)
text(loadPath, ((screen.width)/2)-330, 145);
/* Suchstring anzeigen */
text(searchedString, ((screen.width)/2)-485, 230);
/* wenn Postion ungleich -1 ist der Algorithmus bereits einmal durchgelaufen */
if (searchPosition != -1)
{
fill(c1);
/* Suchposition anzeigen */
text("Pos " + (searchPosition + 1), ((screen.width)/2)-485, 243);
/* Ergebnis der Zeitmessung anzeigen */
text(timeString, ((screen.width)/2)-485, 265);
} else {
text("Pos " + searchPosition + " = nicht gefunden", ((screen.width)/2)-485, 243);
}
}
/* SDBM-Hash-Funktion
Quelle:
http://gphfa.googlecode.com/svn/trunk/GeneralHashFunctions_-_Java/GeneralHashFunctionLibrary.java */
public long SDBMHash(String str)
{
long hash = 0;
for(int i = 0; i < str.length(); i++)
{
hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
/*-----------------------------------------------------------------------------
* allgemeine Vorarbeiten
*-----------------------------------------------------------------------------*/
void praeProcessing()
{
if (loadPath=="" || searchString=="")
return;
long completeTimeBefore = 0;
long completeTimeAfter = 0;
/* Datei laden */
loadFile();
/* nimm die Vorher-Zeit für Gesamtdurchlauf */
completeTimeBefore = System.currentTimeMillis();
/* Algorithmus starten */
searchPosition = rabinKarp();
/* nimm die Danach-Zeit für Gesamtdurchlauf und bestimme Differenz */
completeTimeAfter = System.currentTimeMillis();
completeTimeDiff = completeTimeAfter - completeTimeBefore;
/* berechne den Median = Durchschnitt der errechneten Durchläufe */
long median = calcMedian();
/* Ausgabe für Gesamtdurchlauf formatieren */
timeString = String.format("Gesamtzeit: %02d min, %02d sec, %03d milliseconds, Median über %d-Durchläufe: %02d min, %02d sec, %03d milliseconds \n",
TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff),
TimeUnit.MILLISECONDS.toSeconds(completeTimeDiff) -
TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff)),
completeTimeDiff % 1000,
runs,
TimeUnit.MILLISECONDS.toMinutes(median),
TimeUnit.MILLISECONDS.toSeconds(median) -
TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(median)),
median % 1000
);
/* letztes Suchfenster für Anzeige festlegen */
int i = searchPosition;
boolean cutted = false;
if (i < 0)
{
/* nicht gefunden */
if (completeString.length()>100)
{
searchedString = completeString.substring(0,100);
cutted = true;
} else {
searchedString=completeString;
}
} else if ((completeString.length() -i + 1)>100)
{
/* ab der gefundenen Position folgen noch mehr als 100 Zeichen */
searchedString = completeString.substring(i,i+100);
cutted = true;
} else {
/* ab der gefundenen Position folgen weniger oder genau 100 Zeichen */
searchedString=completeString.substring(i);
}
/* Zeilenumbrüche entfernen */
searchedString = searchedString.replace("\r\n"," ");
if (cutted)
searchedString=searchedString + " [..]";
/* Konsolenausgaben */
/* die sind deswegen hier drin weil sie in draw() immer wieder aufgerufen werden würden */
println(fm + " false matches\n");
println("Alle Zeiten:\n");
for (long timeX: times)
{
println(String.format("%02d min, %02d sec, %03d milliseconds",
TimeUnit.MILLISECONDS.toMinutes(timeX),
TimeUnit.MILLISECONDS.toSeconds(timeX) -
TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(timeX)),
timeX % 1000));
}
/* bestimme maximale Zeitspanne zwischen Minimum und Maximum */
/* muß nach Median-Funktion aufgerufen werden, da sortierte Collection erforderlich */
long maxTimeDiff = (times.get(times.size()-1) - times.get(0));
println(String.format("Maximale Differenz: %02d min, %02d sec, %03d milliseconds",
TimeUnit.MILLISECONDS.toMinutes(maxTimeDiff),
TimeUnit.MILLISECONDS.toSeconds(maxTimeDiff) -
TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(maxTimeDiff)),
maxTimeDiff % 1000));
}
/*-----------------------------------------------------------------------------
* eigentlicher Suchalgorithmus
* - zurückgegeben wird die Suchposition
* oder -1 wenn nicht gefunden
*-----------------------------------------------------------------------------*/
int rabinKarp()
{
int result = -1;
long timeBefore = 0;
long timeAfter = 0;
long timeDiff = 0;
long hs = 0;
long hsub = 0;
int n = 0;
int m = 0;
int n_m = 0;
boolean found=false;
times.clear();
/* Algorithmus gemäß der Anzahl in der Variablen ´runs´ durchlaufen */
for (int counter=1; counter<=runs; counter++)
{
/* n=Länge des gesamten Textes, m=Länge des Musters */
n=completeString.length();
m=searchString.length();
n_m=n-m;
/* nimm Zeit vorher */
timeBefore = System.currentTimeMillis();
/* hs=hash-Wert der ersten Zeichen des gesamten Textes */
hs = SDBMHash(completeString.substring(0,m));
/* hsub=hash-Wert des Musters */
hsub = SDBMHash(searchString);
/* Variablen für erneute Durchläufe zurücksetzen */
result = -1;
/* in fm werden die Anzahl "False Matches" gespeichert,
also die Kollisionen */
fm=0;
found=false;
int i=0;
/* solange Text noch nicht komplett durchlaufen... */
for (i=0; i<=n_m; i++)
{
/* wenn Hashwert des Musters mit dem Hashwert des Textausschnittes übereinstimmt... */
if (hs == hsub)
{
/* ... und die Strings an der Stelle auch übereinstimmen ... */
if (completeString.substring(i,i+m).equals(searchString))
{
/* Übereinstimmung gefunden */
found=true;
break;
} else {
fm += 1;
}
}
/* Bereichsüberlaufsfehler abfangen */
if ((i + m + 1) > n)
break;
/* nächsten Hashwert bestimmen */
hs=SDBMHash(completeString.substring(i+1,i+1+m));
}
if (found)
result = i;
/* nimm Zeit danach und bestimme Differenz */
timeAfter = System.currentTimeMillis();
timeDiff = timeAfter - timeBefore;
/* Zeiten der Gesamttabelle hinzufügen */
times.add(timeDiff);
}
return result;
}
/*-----------------------------------------------------------------------------
* Berechnung des Medians, Erklärung siehe hier:
* http://www.mathe-lexikon.at/statistik/lagemasse/median.html
*-----------------------------------------------------------------------------*/
long calcMedian()
{
long result=0;
/* um den Median zu berechnen muß die generische Liste sortiert sein */
Collections.sort(times);
/* testen, ob Anzahl ungerade... */
if (times.size()%2 != 0)
{
/* (da /2 und nicht /2.0 ist es eine Integer-Division) */
result = times.get((times.size() / 2));
} else {
/* für den Feld-Index wird natürlich eine gerade Zahl benötigt.
Der errechnete Wert soll natürlich nicht abgeschnitten, sondern aufgerundet werden */
result = Math.round((times.get((times.size()/2)-1) + times.get(times.size()/2)) / 2.0);
}
return result;
}
/*-----------------------------------------------------------------------------
* nachfolgend der Code für die Button-Implementierung, denn Buttons gibt es
* standardmäßig nicht in Processing
*-----------------------------------------------------------------------------*/
void update(int x, int y)
{
if(locked == false) {
rect1.update();
rect3.update();
}
else {
locked = false;
}
if(mousePressed) {
if(rect1.pressed()) {
currentcolor = rect1.basecolor;
if (!fileSelected)
{
loadPath = selectInput();
fileSelected = true;
}
}
if (rect3.pressed()) {
/* Suche starten */
if ((fileSelected) && (searchString!=""))
{ praeProcessing(); }
}
}
}
class Button
{
int x, y;
int i_width,i_height;
color basecolor, highlightcolor;
color currentcolor;
boolean over = false;
boolean pressed = false;
void update()
{
if(over()) {
currentcolor = highlightcolor;
}
else {
currentcolor = basecolor;
}
}
boolean pressed()
{
if(over) {
locked = true;
return true;
}
else {
locked = false;
return false;
}
}
boolean over()
{
return true;
}
boolean overRect(int x, int y, int width, int height)
{
if (mouseX >= x && mouseX <= x+width &&
mouseY >= y && mouseY <= y+height) {
return true;
}
else {
return false;
}
}
}
class RectButton extends Button
{
RectButton(int ix, int iy, int iwidth, int iheight, color icolor, color ihighlight)
{
x = ix;
y = iy;
i_width = iwidth;
i_height = iheight;
basecolor = icolor;
highlightcolor = ihighlight;
currentcolor = basecolor;
}
boolean over()
{
if( overRect(x, y, i_width, i_height) ) {
over = true;
return true;
}
else {
over = false;
return false;
}
}
void display()
{
stroke(255);
fill(currentcolor);
rect(x, y, i_width, i_height);
}
}
void keyPressed()
{
if (patternFile != "")
return;
if (key!=CODED)
{
searchedString="";
searchPosition=0;
if (keyCode==DELETE)
{
searchString="";
} else if (keyCode==BACKSPACE)
{
if (searchString.length()>0)
searchString=searchString.substring(0,searchString.length()-1);
} else if (keyCode==ENTER)
{
praeProcessing();
} else {
searchString+=key;
}
}
}