Hi, ich bin derzeit auf der Suche nach einem Algorithmus zum Erstellen einer einfachen Hashsumme. Dabei sollte die Summe eine Ganzzahl sein (32bit). Ich möchte diese gern verwenden um Indizes zu erstellen zum einfachen wiederauffinden von Datensätzen in einer Datei (Quasi wie das indizieren in einer Datenbanken). Jetzt sind mir natürlich Algorithmen wie SHA1, MD5 usw. gut bekannt, allerdings sind die, so denke ich zumindestens, viel zu komplex für das was ich erreichen will. Ich möchte aus einem String/Byte-Array eben diesen Index generieren. Das ganze müsste jedoch auf einem 32-bit Toshiba CMOS mit 40MhZ und 2MB Flash laufen. Kann mir dazu jemand etwas empfehlen? Links oder Namen der entsprechenden Algorithmen reichen mir vollkommen aus, den Rest wie Implementierung etc. mache ich dann selbst. Ich hoffe nur das gerade hier im Forum jemand effiziente Algorithmen kennt womit man auf solchen Controllern arbeiten kann. Vielen Dank schonmal Christian
Ok, mir fiel gerade ein das man das ja ggf. ganz einfach lösen könnte. Da die Bezeichnung aus der ich einen Index generieren möchte nur aus ASCII-Zeichen besteht und die Zeichenkette nie länger als 25 Zeichen besteht, könnte man den ASCII-Wert multipliziert mit dem Index in der Zeichenkette (jedoch beginnend bei 1) aufsummieren und man erhält eine eindeutige Zahl. Worst-Case bei einer Zeichenkette bestehend nur aus 'z' und einer länge von 25, läge der Index somit bei 991250 was noch gemütlich in ein 32bit integer passt. Sollte jemand die Erfahrung gemacht haben das mein Denkansatz nicht funktioniert der möge sich bitte melden, Danke! Grüße Christian
Christian S. schrieb: > den ASCII-Wert multipliziert mit dem Index in der > Zeichenkette (jedoch beginnend bei 1) aufsummieren und man erhält eine > eindeutige Zahl. Eindeutig ist die nicht:
1 | 'z' = 1 * 122 = 122 |
und
1 | ' -' = 1 * 32 + 2 * 45 = 122 |
Tschuldigung, wenn das harsch klingt: Da braucht man keine Erfahrung sondern nur Mathematik. Nehmen wir es sind Gross-, Kleinbuchstaben und Ziffern verwendet. Das gäbe 27+27+10 verschieden Zeichen, also 64 zu deren Kodierung 7 Bit benötigt werden. Bei 25 solcher Zeichen sind das 175 Bit die nötig sind. Nach welchem Verfahren Du auch rechnest: Jedes, das weniger als 175 Bit Summe ergibt, ergibt auf gar keinen Fall eine eindeutige Summe . Das geht garnicht. Kannst Du auch sorum denken. Wenn ein String nur dadurch eindeutig darstellbar ist, dass 8-Bit für das Zeichen, sukzessive mit 2^0, 2^8, 2^16, 2^24 etc. multipliziert werden, wie kann dann eine Multiplikation mit 1, 2, 3, 4, 5 etc, auch eine eindeutige Darstellung ergeben?
Sven P. schrieb: > Christian S. schrieb: >> den ASCII-Wert multipliziert mit dem Index in der >> Zeichenkette (jedoch beginnend bei 1) aufsummieren und man erhält eine >> eindeutige Zahl. > Eindeutig ist die nicht: >
1 | > 'z' = 1 * 122 = 122 |
2 | > |
> und >
1 | > ' -' = 1 * 32 + 2 * 45 = 122 |
2 | > |
Ok, da hast Du recht, dann müsste man an der Stelle noch mit der Länge arbeiten, Summe mit länge des Strings multiplizieren bspw.? -- Christian
Weder dein Algorithmus noch eine andere Hashfunktion ergeben eine
eindeutige Zuordnung.
Bei dir sind Kollisionen sogar sehr einfach zu erzeugen (auch bei
gleichlangen Strings):
"BB", "DA" = 198
"BBBB", "BDBA", "FBBA" = 660
Also musst du überlegen wie du mit Kollisionen umgehst. Je besser die
Hashfunktion, um so seltener sind Kollisionen, vermeidbar sind sie aber
prinzipbedingt nie.
Den Prozessor kenne ich zwar nicht, aber er klingt erstmal locker
schnell genug für eine der üblichen Hashfunktionen.
Gruß,
Manuel
Huch schrieb: > Tschuldigung, wenn das harsch klingt: Da braucht man keine Erfahrung > sondern nur Mathematik. > > Nehmen wir es sind Gross-, Kleinbuchstaben und Ziffern verwendet. Das > gäbe 27+27+10 verschieden Zeichen, also 64 zu deren Kodierung 7 Bit > benötigt werden. Bei 25 solcher Zeichen sind das 175 Bit die nötig sind. > > Nach welchem Verfahren Du auch rechnest: Jedes, das weniger als 175 Bit > Summe ergibt, ergibt auf gar keinen Fall eine eindeutige Summe . Das > geht garnicht. > > Kannst Du auch sorum denken. Wenn ein String nur dadurch eindeutig > darstellbar ist, dass 8-Bit für das Zeichen, sukzessive mit 2^0, 2^8, > 2^16, 2^24 etc. multipliziert werden, wie kann dann eine Multiplikation > mit 1, 2, 3, 4, 5 etc, auch eine eindeutige Darstellung ergeben? Ok, von der Seite habe ich das noch nicht betrachtet. Ich fand meinen Denkansatz auch nicht wirklich ausgereift aber meine Beispiel-Rechnungen hatten funktioniert :) Was haltet Ihr von Adler-32? Schneller als CRC32 ist auch recht kompakt. -- Christian
Christian S. schrieb: > Ok, da hast Du recht, dann müsste man an der Stelle noch mit der Länge > arbeiten, Summe mit länge des Strings multiplizieren bspw.? Oder das tun, was man beim Hashen immer tun muss: Eine Kollisionsstrategie entwickeln. Eine einfache Strategie ist es zb: Hsahcode ausrechnen. Datensatz von dort lesen. a) Ist es der gewünschte? Wenn ja -> fertig Wenn nein -> nächsten Datensatz holen Ist er leer? Wenn ja, dann gibt es den Suchbegriff nicht Wenn nein weiter bei a) Wie du allerdings einen Hashcode als Index in eine Datei nehmen willst, noch dazu mit 32 Bit, ist mir nicht ganz geheuer. Vielleicht solltest du dir überlegen, was du mit dem Hashcode überhaupt machen willst, ehe du jetzt Verfahren erfindest. Wenn es nur darum geht, einen schnelle Variante von "ist es der gewünschte" zu haben, dann ist es auch nicht weiter schlimm wenn der Code nicht eindeutig ist. Du kannst deinen Hashcode sowieso maximal als Vortest nehmen. Wenn der Hashcode eine Übereinstimmung anzeigt, musst du dann sowieso immer noch den kompletten Vergleich machen um festzustellen ob es auch wirklich der richtige ist. Dein Hashcode ist also ein abweisender Vortest. Wenn er sagt, dass es keine Übereinstimmung im Hashcode gibt, dann kann es auch nicht der richtige Datensatz sein. Im anderen Fall könnte er es sein, aber nix genaues weiß man nicht, ehe man nicht den ausfürlichen Test gemacht hat. (Das ist nämlich ein häufig gemachter Denkfehler: Da ein Hashcode prinzipbedingt nicht eindeutig sein kann, darf man sich auch nicht darauf verlassen, dass ein übereinstimmender Hashcode auch übereinstimmende Daten bedeutet.)
Kollisionen sind ja auch nicht böse. Du musst für deinen Anwendungsfall entscheiden, wie viele Kollisionen am effizientesten sind. Wenn sämtliche Eingabeworte kollidieren und dasselbe Code(Hash)wort liefern, ist das in der Praxis genauso ineffizient, wie wenn kein Wort kollidiert und du dafür eine Tabelle mit 4 Millionen Einträgen brauchst, von denen 2/3 leer sind. Irgendwo dazwischen liegt die Wahrheit :-) Karl-heinz Buchegger hat schon eine gängige Mechanik angesprochen: Per Hash (der bewusst Kollisionen liefert) in eine Tabelle von Listen greifen.
Karl heinz Buchegger schrieb: > Vielleicht solltest du dir überlegen, was du mit dem Hashcode überhaupt > machen willst, ehe du jetzt Verfahren erfindest. Meine Idee war es eigentlich meine Datensätze die ich zwischenspeichern muss (in meinem Fall ein Scanner mit proprietären System) zu indizieren um sie später schneller wiederfinden zu können. Beim Schlüssel handelt es sich um einen max. 25 Zeichen langen String. Dieser String ist eindeutig da wie gesagt Schlüssel. Jetzt wird der Barcode gescannt und ich bekomme diesen max. 25 Zeichen langen String. Um nun den passenden Datensatz dazu zu finden (mit weiteren Infos wie Bezeichnungen etc.) Wollte ich nun ein Array aufbauen wo der erzeugte index ein index in einem Array mit relativen Dateipositionen ist. Wenn ich dann in der Datei an die Dateiposition springe und meinen Datensatz auslese habe ich meinen Datensatz gefunden. Wenne es keine Position dafür im Index-Array gibt dann gibt es auch nicht diesen Datensatz. Ich weiß das ist alles recht primitiv aber für den Fall wo ich es benötige wäre es eine gängige Alternative. Statt einem linearen Array könnte man auch noch über einen einfachen Baum nachdenken aber dazu müsste ich den Baum erst implementieren und deswegen erschien mir die "Lösung", mit dem linearen Array aus Dateipositionen dessen index der index/hash des Schlüssels vom Datensatz ist, am einfachsten. Jetzt wo ich das aber gerade mit dem Baum schrieb scheint es mir fast schon die bessere Lösung zu sein ... hmmm -- Christian
Selbst-ausbalancierende Binärbäume sind bereits erfunden :-) Schau mal: - AVL-Baum - Rot-Schwarz-Baum - GNU libavl
Sven P. schrieb: > Selbst-ausbalancierende Binärbäume sind bereits erfunden :-) > > Schau mal: > - AVL-Baum > - Rot-Schwarz-Baum > - GNU libavl Jap, das weiß ich schon, mir ging es um die Implementierung. Eine Fremd-Lib wird auf dem CMOS nicht/kaum gehen, selbst der Compiler von Toshiba bietet gerade mal die grundlegensde Standard-Bibliothek an, und das noch nicht mal vollständig. -- Christian
Christian S. schrieb: > ich bekomme diesen max. 25 Zeichen langen String. Um nun den passenden > Datensatz dazu zu finden (mit weiteren Infos wie Bezeichnungen etc.) > Wollte ich nun ein Array aufbauen wo der erzeugte index ein index in > einem Array mit relativen Dateipositionen ist. Überleg einfach mal wie groß dein Array sein muss, wenn du 32 Bit als Index haben willst und jeder Index prinzipiell möglich ist :-) Aber abgesehen davon: Ja du kannst das schon so machen. Nur brauchst du eben eine Kollisionsstrategie. Die einfachst mögliche: Beim Einfügen eines neuen Satzes: Wenn der Slot schon belegt ist, dann einfach den nächsten freien Slot nehmen Beim Suchen: Über den Index aufsuchen und wenn das der falsche war, dann mit dem nächsten Eintrag im Array weitermachen und so quasi von der Hashposition aus linear weitersuchen, bis man entweder den gesuchten Satz hat oder eben feststeht, dass er nicht drinnen ist, weil der Index- eintrag (der Slot) leer ist. Das ist eine gängige Kollisionsstrategie. Es gibt auch noch andere. Aber für den Hausgebrauch reicht das schon. Du musst dich einfach nur von der Vorstellung trennen, dass der Hashcode eindeutig ist. Alles andere folgt dann daraus. Sowas ist doch schnell implementiert und war früher gang und gäbe als die Festplatten und Magnetbänder noch das Laufen lernten. Bei IBM hies sowas eine "ISAM-Datei" wenn ich mich recht erinnere (wenn auch die Kollisionsstrategie eine andere war)
Mach das was Karl Heinz sagt, er hat das perfekt erklärt. Einzig hinzuzufügen wäre, daß das natürlich nur solange effizient funktioniert wie dein Index(Array) deutlich größer ist als die maximale Anzahl von Einträgen, damit es bei der Kollisionserkennung genügend leere Einträge gibt. Ich würde einen max. Füllgrad von 0,2 bis 0,4 vorschlagen.
U.R. Schmitt schrieb: > Ich würde einen max. Füllgrad von 0,2 bis 0,4 vorschlagen. Klingt nicht schlecht. Was man auch nicht vergessen darf: Die Datei (und damit der Index) muss reorganisiert werden, wenn die Größe des Index höher gestellt wird. D.h. da muss man ev. ein Hilfsprogramm vorsehen. Was noch nicht erwähnt wurde: Der Index wird selbstverständlich mit in die Datei gespeichert und beim Öffnen der Datei von dort in den Speicher geholt. Das alles klingt jetzt vielleicht furchtbar kompliziert. Es ist aber im Grunde genommen furchtbar einfach. Muss es auch sein, sonst hätten es die Mainframes aus dem letzten Jahrhundert nicht gepackt :-)
Ändert sich die Liste der zu durchsuchenden Schlüssel zur Laufzeit? Wenn nicht, dann ist es evtl. einfacher, statt dem Baum ein sortiertes Array mit binärer Suche zu durchsuchen. http://en.wikipedia.org/wiki/Bsearch
sebastians schrieb: > Ändert sich die Liste der zu durchsuchenden Schlüssel zur Laufzeit? > Wenn nicht, dann ist es evtl. einfacher, statt dem Baum ein sortiertes > Array mit binärer Suche zu durchsuchen. > > http://en.wikipedia.org/wiki/Bsearch Ja das muss ich vorsehen das weitere Datensätze hinzukommen. Daher tendiere ich momentan zu einem binären Baum. -- Christian
Hallo Christian, sagt Dir Constant Data Base (CDB) was? Schau mal hier: http://cr.yp.to/cdb.html Vielleicht könnte das auch was für Dich sein. Gruß, Michael
Christian S. schrieb: > sebastians schrieb: >> Ändert sich die Liste der zu durchsuchenden Schlüssel zur Laufzeit? >> Wenn nicht, dann ist es evtl. einfacher, statt dem Baum ein sortiertes >> Array mit binärer Suche zu durchsuchen. >> >> http://en.wikipedia.org/wiki/Bsearch > > Ja das muss ich vorsehen das weitere Datensätze hinzukommen. Über wieviele Datensätze reden wir eigentlich? > Daher > tendiere ich momentan zu einem binären Baum. Kann man auch machen. Ist verwaltungstechnisch aber auch nicht unaufwändiger. Haben dich die Kollisionen abgeschreckt? Mach da jetzt kein Totschlagargument draus! Wenn deine Hashfunktion nicht allzu primitiv ist, dann ist das in der Praxis überhaupt kein Problem. Du brauchst auch keine 'ausgefuchste' Hash-Funktion. Schau dir deine Schlüssel an. Die ersten 4 Bytes nehmen, das ganze Modulo der Tabellenlänge - fertig ist eine einfache Hashfunktion. Solange sich deine Schlüssel in den ersten 4 Buchstaben unterscheiden, wirst du nicht allzuviele Kollisionen bekommen und wenn, sind sie einfach zu behandeln. Und wenn deine Artikelnummern in den ersten 4 Buchstaben alle gleich sind, dann nimmt man eben andere. Zb eine Kombination aus den ersten 2 und den letzten 2. Irgendwas. Hauptsache die Chancen stehen gut, dass nicht allzuviele Artikel mit diesem Buchstabenextrakt zu gleichen Ergebnissen führen. Das ist nichts, woraus man jetzt ein Drama machen müsste. Und eine Verwaltung der Records auf dem File kriegst du damit gratis noch mit dazu.
Hashfunktionen sind durchaus eindeutig. Egal, wie oft Du den Hash machst, es kommt immer dasselbe raus. Eineindeutig hingegen sind sie nicht, weil eben der umgekehrte Weg nicht mehr funktioniert. Ein Hash-Code kann von unzähligen Eingaben erzeugt worden sein.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.