Prüfsumme - Reihenfolge entscheidend?

Hallo,

ich bin auf der Suche nach einem Algorithmus/Hash-Funktion, der mir für gegebene Wörter/Zahlen eine Prüfsumme errechnet, welche eindeutig bezüglich der Reihenfolge der Wörter ist.

Beispiel: Ich weiß, dass ein String z.B 5 A's, 4 B's und 1 C hat. Wenn man nun alle möglichen Permutationen/unterschiedlichen Strings betrachtet und diese nach einander "verschlüsselt", sollen genau so viele Unterschiedliche Hashes rauskommen.

Welcher Algorithmus kann das gewährleisten?

danke!

otze

//edit ahh misinterpretiert. ignore me.

ich glaube nicht, dass das möglich ist. für viele aktuelle Prüfsummenalgorithmen wurden ja nichtmal strings gfunden die überhaupt kollidieren.

peter.bergov schrieb:

Hallo,

ich bin auf der Suche nach einem Algorithmus/Hash-Funktion, der mir für gegebene Wörter/Zahlen eine Prüfsumme errechnet, welche eindeutig bezüglich der Reihenfolge der Wörter ist.

Beispiel: Ich weiß, dass ein String z.B 5 A's, 4 B's und 1 C hat. Wenn man nun alle möglichen Permutationen/unterschiedlichen Strings betrachtet und diese nach einander "verschlüsselt", sollen genau so viele Unterschiedliche Hashes rauskommen.

Welcher Algorithmus kann das gewährleisten?

danke!

Versteh ich nicht...
Warum ist C++s hash nicht gut genug?

#include <algorithm>
#include <iostream>
#include <string>

int main(){
  using namespace std;
  string s="AAAAABBBBC";
  do{
    cout << s << " -> " << hash<string>()(s) << '\n';
  }while(next_permutation(s.begin(), s.end()));
}

Allerdings liest Du Dir wohl am besten selber durch ob std::hash das gewährleistet, was Du willst.

dd++ 0

z.B. bei der CRC Prüfung wird auch die Reihenfolge berücksichtigt

http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung

Skym0sh0

Ist nicht bei allen halbwegs guten Hash-Algorithmen die Reihenfolge entscheidend?

Ich meine, ansonsten würde die Kollisionsgefahr ja nochmal ziemlich steigen...

Letztendlich arbeitet man bei Hashes immer mit Kollisionsgefahr. Das ist auch gar nicht anders möglich, weil die Breite eines Hashes fest und die Ergebnismenge einer Hashfunktion daher endlich mächtig ist, wohingegen die Eingabedaten beliebig lang werden können. Ab einer bestimmten Länge ist die Anzahl möglicher Permutationen stumpf größer als die Anzahl möglicher Hashwerte, und dann hat es sich mit der Anforderung.

Worum geht es denn? Ich kann im Moment nicht einschätzen, was für Garantien du wirklich brauchst.

krümelkacker

peter.bergov schrieb:

ich bin auf der Suche nach einem Algorithmus/Hash-Funktion, der mir für gegebene Wörter/Zahlen eine Prüfsumme errechnet, welche eindeutig bezüglich der Reihenfolge der Wörter ist.

Ich schätze, du hast dich vom Wort "Prüfsumme" etwas irritieren lassen. Tatsächlich geben "gute" Hash-Funktionen im Allgemeinen eine andere "Prüfsumme" wenn du in der Eingabe die Reihenfolge von Wörtern vertauschst. Das ist gar nichts so besonderes.

Was ist der genaue Einsatzzweck in deinem Fall?