Direkte Adressierung anstatt Hashing?
-
Hallo!
Ich möchte anstatt eines Hashingverfahrens einen direkten Sprungmechanismus für eine Tabelle von Multibytezeichen (z.B. Kyrillisch) verwenden, welche in lateinische Buchstaben umgesetzt werden sollen. Leider ist Hashing nicht schnell genug wegen der Kollisionen, weil er in diesen Fällen suchen muss, bis er das richtige Zeichen in der Hashtabelle gefunden hat (bei Duplikaten unter den Hashwerten). Ich habe gehört, dass man direkt adressieren kann, aber weiß nicht wie das geht. Ich will keine for-Schleife oder while-Schleife verwenden, da dies sehr zeitaufwendig ist. Mit Hashingmechanismus brauche ich für 1 GB kyrillischen Text (nach Latein umsetzen: z.B. Tchaikovsky) etwa 50 sec, was einfach zuviel ist. Toll wenn jemand hier einen Tipp für einen direkten Sprung geben könnte.
Weihnachtliche Grüße
kjesse :xmas1:
-
Beim Hashing kommt es für Selektivität und Performanz sehr auf die jeweilige Implementierung an, dafür gibt es aber viele Bibliotheken passend für verschiedene Datenstrukturen (nicht nur String), dabei aber immer die Copyrights beachten. Welche verwendest du denn?
Ich habe mit libavl (LGPL) als Quasiersatz für ein Dictionary gute Erfahrungen gemacht, auch hinsichtlich der Performanz.
-
Ich benutze ein Hashing für Java und Strings:
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;return hashval % HASHSIZE;
Ich weiß leider nicht, wie das mit einem direkten Sprung über die Adresse und ohne Schleife gehen soll, wenn ich aus dem Text ein Zeichen in der Konvertierungstabelle suche. Ich dachte immer, Hashing wäre am schnellsten.
-
Ohoh, da scheinen mir aber doch einige Grundlagen zum Hashing zu fehlen. Mit so einer Hashfunktion sind deine Ergebnisse nicht überraschend. Gehe mal davon aus, dass sind schon sehr viele Leute mit deinen Anforderungen auseinandergesetzt und mehr oder weniger gute Lösungen mit ANSI C veröffentlicht haben (wenig Kollisionen,...).
Ich empfehle dir erstmal Grundlagen im Hashing zu erwerben, andernfalls müsstest du auf fertige Dictionary-Lösungen (im C++ Jargon auch map genannt) ohne Hashing zurückgreifen, wenn deine kompletten Datenstrukturen in den Hauptspeicher passen.
-
Was genau willst du eigentlich erreichen? Ein Wörterbuch oder nur eine Übersetzung von Buchstaben? Dein Problem liest sich eher wie letzteres. Die Umsetzung ist eigentlich ganz einfach. Du erstellst ein Feld, in das 16Bit an Zeichen passen (65536 Einträge), für deinen Unicode. Das wären bei einem Wert von 16Bit Breite dann 128K im Speicher (der Key braucht keinen Speicherplatz, weil er ja der Offset zur Adresse ist). Wenn du jetzt mit dem kyrillischen Zeichen als Key in die Map gehst, dann hast du deine direkte Adressierung.
