Eindeutiger Zahlenwert für einen String

[musicman56]

Hallo,

ich muss in eine meiner Datenbanken Daten aus externen Anwendungen (Kontoauszüge aus Banking-Programmen) einlesen, die teilweise keine eindeutige Kennung haben. Also war der Gedanke aus den Daten Auszug-Nr, Konto, BLZ, Verwendungszweck(e) usw. einen String zu bilden, und daraus einen eindeutigen Hash-Wert.

In einem anderen Beitrag in diesem Forum bin ich auch fündig geworden:

Delphi-Quellcode:

// This is a pretty good general purpose string hash function. It is derived
// from the PJWHash and is used inside the UNIX OS

Function HashFromStr(Const Value: String): Cardinal; // ELF-Hash
Var
  i: Integer;
  x: Cardinal;

Begin
  Result := 0;
  For i := 1 To Length(Value) Do Begin
    Result := (Result Shl 4) + Ord(Value[i]);
    x := Result And $F0000000;
    If (x <> 0) Then
      Result := Result Xor (x Shr 24);
    Result := Result And (Not x);
  End;
End;

Dachte ich zumindest...:oops: Es kommen doppelte Hash-Werte heraus. Hat jemand eine andere oder bessere Idee / Routine / Tipp ?

Natürlich könnte ich aus einigen Feldern ein Datenfeld zusammensetzen und indizieren, aber das möchte ich nicht, weil das nur unnötig die Datenbank aufbläht.

[mkinzler]

Ein Hash ist nunmal nicht ein-eindeutig, wie wäre es mit einer GUID?

[DeddyH]

Falls der Zweck des Hashs lediglich die Eindeutigkeit sein soll, wieso dann nicht einen Unique Index über die relevanten Felder bilden?

[mjustin]

Ein Unique Index über alle Felder frisst entsprechend viele Resourcen. Eine synthetische ID (Generator / AutoInc oder die vorgeschlagene GUID) ist sparsamer im Verbrauch.

[DeddyH]

Damit sichert man aber keine Eindeutigkeit der Kombination der Feldwerte, deshalb mein "Falls...".

[himitsu]

Zitat:

Zitat von mkinzler (Beitrag 1116442)

Ein Hash ist nunmal nicht ein-eindeutig, wie wäre es mit einer GUID?

Eine GUID ist es aber auch nicht.

Mit den 128 Bit ist es, im Gegensatz zum ELF-Hash oder CRC32 mit ihren 32 Bit, einfach nur "etwas" unwahrscheinlicher daß sich Werte/Hashs gleichen können.



Um es kurz zu machen:
100%ig eindeutig wäre nur ein vollständiger Binärvergleich, bzw. ein Unique-Index über alles.
Oder du legst dir eine neue Spalte an, welche als Unique-Index entweder fortlaufende (einfacher) oder zufällige Werte (z.B. aus der Einfügezeit und den Daten berechnet, gibt es den wert schon, wird ein anderer zufällig gewählt).

Wenn keine der Daten (der anderen Felder) doppelt sein dürfen und du keinen Index willst, dann wirst du wohl beim einfügen vorher prüfen müssen, ob es das nicht schon gibt.

[stahli]

Schau mal, ob Dich das weiter bringt (insb. #8).

[DeddyH]

Nochmal: welche Absicht steckt dahinter? Geht es lediglich darum, ein eindeutiges Feld zu haben? Dann würde ja ein künstlicher Schlüssel (AutoInc oder derartige Geschichten) vollkommen ausreichen. Soll aber sichergestellt sein, dass ein Hans Meier mit der KtoNr 123546 und BLZ 11122233 nur einmal vorkommen kann, ist IMO ein Unique Index über die 3 Spalten die beste Variante.

[musicman56]

Hallo,

@stahli

Vielen Dank für den "adler"-Tipp. Bei 10.000 Testdatensätzen immer noch 7 Doubletten. Mit der ersten Methode waren es 11. Aber, der Weg scheint erfolgversprechender zu sein. Werde mal weiter testen.

@DeddyH

Zitat:

Soll aber sichergestellt sein, dass ein Hans Meier mit der KtoNr 123546 und BLZ 11122233 nur einmal vorkommen kann, ist IMO ein Unique Index über die 3 Spalten die beste Variante.

Das ist das Ziel. Aber, er (der Hans Meier) kommt natürlich öfter vor, auch eventuell mehrmals am Tag. Darum: Konto-Nr + Bankleitzahl + Verwendungszweck alleine reichen eben nicht aus. Brauche mindestens noch das Datum + Betrag + Auszug-Nummer + Auszug-Seite + Datum/Zeit der Importdatei + Importdatei-Zeilen-Nummer bzw. Datensatz-Nummer dazu. Weil...könnte ja beispielsweise sein, dass eine Auszahlung an einem Geldautomaten am selben Tag zweimal mit demselben Betrag enthalten ist.

Diese Variante würde einen ziemlich großen/langen Unique-Index ergeben, und das möchte ich nach Möglichkeit vermeiden.

[Bernhard Geyer]

Es gibt keine 100% Lösung dafür soviel Infos in 4 oder 8 oder 16 Bytes eindeutig "komprimiert" zu speichern.

Du benötigst mindestens eine Umsetztabelle In der du für jede "Quellfelder" eine selbst generierte (GUID oder AutoInc-Feld) vergiebst du du dann in deinem weitern DB-Modells als Schlüsssel verwendest.

[s.h.a.r.k]

Zu Not Hashes mit zwei verschiedenen Algorithmen machen, oder Hash + GUID. Wenn bei verschiedenen Daten beide Hashes auch noch gleich sind, na dann Prost :stupid:

[rollstuhlfahrer]

Reicht denn nicht ein AutoInc-Feld? - Das ist auf jeden Fall für die nächsten 2 Millionen Einträge eindeutig. Je nachdem wie viele Bits die Datenbank dem INT-Feld spendiert, sind das auch wesentlich mehr Einträge.
Und ganz nebenbei braucht so ein Feld keine Rechenleistung, um einen Hash zu berechnen, der dann vielleicht doch eine Dublette hat, weil eine Überweisung 2x vorkam. Je nachdem, was die Überweisung denn war, ist es durchaus sogar normal, dass über das Jahr verschiedene Posten 12x vorkommen, sei es Miete, Lohn, Gehalt, ... .

Bernhard

[musicman56]

Hallo zusammen,

bin fündig geworden. Der Link von "stahli" hat mich auf die richtige Spur gebracht. :-D

MD5-Hash ist die Lösung. Mit 16 Bytes ist die Datenmenge noch erträglich und auch noch effektiv zu indizieren :-D

Wen's interessiert, einfach nach "delphi hash md5.pas" googeln.

@Bernhard
Es geht ja nicht darum, dass ich "intern" in der Datenbank ein eindeutiges Kriterium habe. Die Daten stammen von externen Banking-Programmen, in den unterschiedlichsten Formaten (csv,txt,dbf...). Ein User kann ein und die selbe Datei ja mehrfach "versuchen" einzulesen und ich kann das nicht verhindern. Da hilft auch nix, wenn ich die Datei nach dem Import lösche. Hinzu kommt: Manche Banking-Programme haben nicht einmal die Möglichkeit den Export-Umfang zeitlich zu begrenzen. Da bekomm ich also manchmal generell das gesamte Jahr geliefert, und dann wird's lustig....

Also dann, nochmals vielen Dank an alle!

[p80286]

Zitat:

Zitat von rollstuhlfahrer (Beitrag 1116507)

Je nachdem, was die Überweisung denn war, ist es durchaus sogar normal, dass über das Jahr verschiedene Posten 12x vorkommen, sei es Miete, Lohn, Gehalt, ... .

Einspruch Euer Ehren,
mehrfach soll wohl bedeuten, das der Überweisungsbeleg für juli-Gehalt von Herrn willibald Maier in Ulm von der Landwirtschaftsbank Unterbayern 2x vorhanden ist.
Nich daß er 12 mal im Jahr Gehalt bezogen hat.

Gruß
K-H

[rollstuhlfahrer]

Zitat:

Zitat von musicman56 (Beitrag 1116509)

@Bernhard
Es geht ja nicht darum, dass ich "intern" in der Datenbank ein eindeutiges Kriterium habe. Die Daten stammen von externen Banking-Programmen, in den unterschiedlichsten Formaten (csv,txt,dbf...). Ein User kann ein und die selbe Datei ja mehrfach "versuchen" einzulesen und ich kann das nicht verhindern. Da hilft auch nix, wenn ich die Datei nach dem Import lösche. Hinzu kommt: Manche Banking-Programme haben nicht einmal die Möglichkeit den Export-Umfang zeitlich zu begrenzen. Da bekomm ich also manchmal generell das gesamte Jahr geliefert, und dann wird's lustig....

Sorry, habe ich anders verstanden.

Zitat:

Zitat von musicman56 (Beitrag 1116509)

Wen's interessiert, einfach nach "delphi hash md5.pas" googeln.

Tja, leider ist das nicht ganz so einfach: Es gibt für Delphi bestimmt 10 oder mehr verschiedene Implementierungen für MD5-Hashes, aber das Ergebnis sollte überall das gleiche sein.

Zitat:

Zitat von p80286 (Beitrag 1116510)

Zitat:

Zitat von rollstuhlfahrer (Beitrag 1116507)

Je nachdem, was die Überweisung denn war, ist es durchaus sogar normal, dass über das Jahr verschiedene Posten 12x vorkommen, sei es Miete, Lohn, Gehalt, ... .

Einspruch Euer Ehren,
mehrfach soll wohl bedeuten, das der Überweisungsbeleg für juli-Gehalt von Herrn willibald Maier in Ulm von der Landwirtschaftsbank Unterbayern 2x vorhanden ist.
Nich daß er 12 mal im Jahr Gehalt bezogen hat.

Ich habe es nachgeschaut und tatsächlich steht beim Gehalt der Monat mit dabei. Hätte ja sein können, dass man 12x im Jahr an unterschiedlichen Tagen vom selben Absender mit dem selben Verwendungszweck und der selben Geldmenge eine Transaktion erhält. Das hätte (ohne Datum) dann wirklich Spaß gemacht.

Bernhard

[musicman56]

Hallo,

na ja, die Gehälter sind bei den wiederkehrenden Buchungen weniger das Problem. Bei Abhebungen am Geldautomaten beispielsweise ist ja BLZ und Konto überhaupt nicht angegeben, und der Verwendungszweck ist auch der selbe, wenn's der gleiche Automat ist/war. Und dann wird's lustig: Jetzt hat der Kunde 100,- Euro vom Automaten gezogen, und eine Stunde später nochmals, weil er mit seiner Frau Schuhe kaufen war :shock:

[himitsu]

Ein "einfacher" kleiner Hasch über die gewünschten Felder. (4 oder 8 Byte reicht und ist schnell zu prüfen).

Vor dem einfügen eines neuen Datensatzes den Hash berechnen und nachsehn, ob es andere Datensätze mit diesem Hash gibt.
Gibt es einen, dann die Felder direkt vergleichen. Bei direktem Fund dann doch nichts einfügen.

Eventuell auch erstmal einfügen und dann später die Dubletten rausfiltern, wenn die Dubletten nicht sofort stören.



Wie gesagt, 100% eindeutig kann ein Hash nicht sein.

Bei einem MD5-Hash, bzw. einer GUID (128 Bit) gibt es bei einer Datengröße von nur 17 Byte theoretisch, zu jedem Hash durchschnitlich bis zu 256 Datensätze.
Bei 18 Byte sind es schon 65-tausend, bei 20 Byte über 4 Milliarden usw.