String vergleichen mit Hash?

[stahli]

Ich habe einen langen String:

Code:

Picture=eJxMvAVcVeu6/T/u/3fPOTsMuru7O0QpAUXBIKRbkO4Gwe5uUbpREcXC7u5t7zy7++w8d9+7/+N9#0X2vn8/zmXMFLljzu8YYzzPfufzDLyf9B8Q/N5YFa9vr+g8YyPs3vH78//7rPvAjug9+j57DP6Br#+Ef0jPzC/V/Rd/Q39B4...

(ist etwa 100 mal so lang und enthält ein Bild, umgewandelt in Base64)

Nun merke ich mir den eingelesenen String in OldString und vergleiche die Texte beim nächsten Einlesen.

Wie kann ich (mit XE-Mitteln) am schnellsten 2 lange Strings auf Gleichheit prüfen, ohne eine komplette Kopie des Strigs zu halten?

Mit einer Hash-Funktion? Aber mit welcher?

Ich möchte letztlich den Base64-Text nicht jedesmal in ein Bild zurück rechnen (das ist etwas langsam), sondern direkt auf einen Stream zugreifen, wenn der schon passend vorliegt.

[Deep-Sea]

1. Allgemeine Hashfunktion: Hier musst du beachten, dass selbst wenn der Hash gleich ist, die Daten trotzdem unterschiedlich sein können. Du musst also bei einem "Treffer" trotzdem noch mal die Strings vergleichen. Passender Algorithmus: FNV.
2. Kryptologische Hashfunktion: Die Wahrscheinlichkeit, dass zwei unterschiedliche Daten den gleichen Hash ergeben ist fast Null, dafür ist der Aufwand den Hash zu berechnen größer.

Kommt also wie immer drauf an, was du erreichen willst :stupid:

[blackfin]

Meiner Meinung nach bieten sich hier die Hash-Funktionen MD5, SHA1 / SHAxxx an. MD5 ist der gebräuchlichste für so etwas.
Ob XE einen davon an Bord hat, weiss ich nicht, da ich XE nicht habe, allerdings gibt es im Netz Single-Units für die besagten Algorithmen, ohne dass man eine Komponente installieren müsste.

Edit:
Oder du nimmst eine einfache Hash-Funktion wie den ELF-Hash, der unter Linux-Systemen beispielsweise für so etwas verwendet wird.
(wenn es nicht um kryptographische Sicherheit geht, wie Deep-Sea bereits gesagt hat, sondern nur ums Vergleichen):

Delphi-Quellcode:

function ElfHash(const Value: string): Integer;
var
  i, x: Integer;
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;

[stahli]

Anbei mal ein ScreenShot.
Die Bilddaten wurden bisher jedesmal aus Base64 umgerechnet. Das hat zu lange gedauert, wenn mal mehrere Bilder anzuzeigen waren.
Eine schnelle Lösung war, String und Stream zu speichern und bei Stringgleichheit den letzten Stream wieder zu verwenden.

Das verbrädt halt ziemlich viel Speicher, weshalb ich quasi lieber eine Prüfsumme zum Vergleich speichern würde.
Die Prüfsummenfunktion müsste aber deutlich schneller laufen als die Base64-Umrechnung, damit das Sinn macht.

Sehr kritisch sind die Daten nicht. Bei Falsch-Negativem Ergebnis würde Base64 unnötig neu umgerechnet. Bei Falsch-Positivem Ergebnis würde u.U. ein falsches Bild angezeigt.

Die Funktion müsste also "nach menschlichem Ermessen zuverlässig sein". ;)

Ich schaue mir mal MD5 an. Danke erst mal.

[blackfin]

Wenns dir nur um eine schnelle Prüfsumme geht, bietet sich auch noch der (gute, alte) CRC32 an.

[Deep-Sea]

Zitat:

Zitat von stahli (Beitrag 1108471)

Bei Falsch-Positivem Ergebnis würde u.U. ein falsches Bild angezeigt.

Darum musst du die Daten ja eben noch mal vergleichen. Da dieses Ereignis aber, je nach Algorithmus, sehr selten ist, wirken sich die Vergleiche bei falsch-positivem Ergebnis kaum auf die Performance aus.

[sx2008]

Ich würde da MD4 empfehlen.
MD4 lässt sich schneller als MD5 errechnen.
MD4 ist heutzutage nicht mehr "en vogue", weil es möglich ist, für einen bestimmten Hashwert einen Klartext zu errechnen.
Das macht MD4 abgreifbar für Passwörter oder ähnliches.
Als reine Prüfsumme über ein Image jedoch ist es sehr gut geeignet.
Bei 128Bit Breite ist es in diesem Jahrtausend nicht zu erwarten, dass zwei unterschiedliche Bilder den gleichen Hashwert haben.

[stahli]

Danke Euch.

Mit MD4 bin ich nicht weiter gekommen.

Und in ZLib ist crc32 offenbar von adler32 abgelöst worden.
Das habe ich einfach mal geetestet und es scheint wunderbar und schnell zu funktionieren.
(Intern wird das in ZLib scheinbar als Checksum im Compressverfahren genutzt.)

Delphi-Quellcode:

function TodPerson.GetPictureStream: TMemoryStream;
var
  P: PChar;
  C: LongInt;
begin
  P := PChar(Picture);
  C := adler32(0, P, Length(P));
//  if Picture <> OldString then
  if C <> OldC then
  begin
    Base64ToMS(Picture, FPictureStream);
//    OldString := Picture;
    OldC := C;
  end;
  FPictureStream.Seek(0, soBeginning);
  Result := FPictureStream;
end;

[himitsu]

Wenn es nicht nur "meistens" Gleich sein soll, sindern immer zu 100% identisch,
dann errechne den Hash und vergleiche erstmal damit,
ist der Hash gleich, dann nochmals die Daten direkt vergleichen.

Alleine mit CRC32 sollte damit eine enorme Geschwindigkeitssteigerung erreicht werden.

PS: CRC32 paßt in einen Integer und läßt sich somit schneller vergleichen, als MD5, SHA und Konsorten,
auch ist die Berechnung oftmals flotter.

[Aphton]

Mal eine Nebenfrage - warum wandelst du das Bild in Base64 um und erhälts dadurch eine Datenredundanz (Größenanstieg 133,3*%) - ist es nicht möglich, es direkt als Stream abzuspeichern?

Zum Problem mit der Datenredundanz: Falls du das Bild direkt Base64 - enkodierst, würde ich dir vorschlagen, zuerst den Datenstrom zu komprimieren und anschließend die Kodierung vorzunehmen.
Aber ich schätze mal, du machst das sowieso?!