Hallo!

Mal ganz rein interessenhalber... Gibt es eine Hash-Funktion, aus deren Wert man ableiten kann, 'wie falsch' ein Datenblock ist?

Ich suche also ein H(), mit dem das geht:

h0 = H(DATA)

h1 = H(DATA1) //DATA1 hat 5 Unterschiede ggü. DATA
h2 = H(DATA2) //DATA1 hat 100 Unterschiede ggü. DATA

Und es soll gelten:

(h1-h0) < (h2-h0)

oder eine andere, ähnliche Relation... Kurz, ich möchte erkennen können, welcher Datenblock weniger Störungen enthält.

Gibt es sowas (mit annehmbarer Größe)? TigerTree könnte man dazu missbrauchen, ist aber von der Datenmenge her relativ Witzlos, dann kann ich auch gleich die Rohdaten vergleichen.
Geschwindigkeit spielt fast keine Rolle, Datenmenge schon.

Wenn so ein Hash unmöglich ist, sagts mir^^

mfg
Martok

Martok hat folgendes geschrieben:

Hallo! Mal ganz rein interessenhalber... Gibt es eine Hash-Funktion, aus deren Wert man ableiten kann, 'wie falsch' ein Datenblock ist? ...

Hallo Martok,

es gibt natürlich beliebig viele Hash-Funktionen, Aufgabe ist ja, sich eine möglichst geeignete zu stricken. Ich habe mal in den Gründerjahren (erfolgreich) eine Hash-basierte Datenverwaltung für Speicherplatten ohne Dateisystem geschrieben und dazu folgende Forderungen an die Hash-Funktion aufgestellt:

1. geringe Unterschiede im Schlüssel sollen grosse Unterschiede im Hashwert zur Folge haben.

2. für eine zufällige Menge an Schlüsseln sollten die Hashwerte möglichst gleichmässig im Wertebereich verteilt sein. Konkret: 1000 Datensätze mit zufälligen Schlüsseln sollten gleichmässig auf der Platte verteilt sein (1000 Datensätze mit aufeinanderfolgenden Schlüsseln aber auch, daher Punkt1).

Ich denke, zumindest Punkt 2 steht deiner Forderung diametral entgegen. Aber das ist eben nur eine von vielen Möglichkeiten, man kann ja auch ganz andere Anforderungen an die Hashfunktion stellen, die Frage ist immer nur, wie effektiv das resultierende System in realer Umgebung arbeitet.

Ich würde daher so formulieren: es gibt wahrscheinlich eine Funktion mit den von dir gewünschten Eigenschaften (Abstandsfunktion), aber es ist fraglich, ob diese auch als Hash-Funktion für den vorgesehenen Zweck geeignet ist. In dem von mir beschriebenen Scenario wohl nicht.

Gruss Reinhard

Die Konstruktion eines solchen Hash-Verfahrens könnte z.B. wie folgt funktionieren:
1. 16-Bit-Byte-Summe der Eingabe-Daten
2. 16-Bit-Anzahl der 1-Bits der Eingabe-Daten

Daraus dann nen 32-Bit-Wert bilden und dann solltest Du da schon recht gut nen Eindruck bekommen ...

Wenn Du zusätzlich auch Positionsabhängige Datenveränderungen brauchst, solltest Du mal schauen, dass Du noch einen dritten Wert dazu nimmst, den Du aus den Daten und der Position in der Datei berechnest ... Also z.B.


Also in die Richtung lässt sich da'n bissl was finden ...

Alternativ könntest Du auch in die Ecke Fehlererkennende Codes schauen ... Wichtig ist aber in jedem Fall erstmal, dass Du Dir sicher bist, was für Fehler du erwartest, also wo eine solche Hash-Funktion ansetzen muss ...

Häufig auftretende Fehlerarten sind z.B.:
- Bit-Kipper
- Burst-Fehler
- Gekoppelte Fehler
- Vertauschungen
- Auslassungen
- Eingefügte Zeichen

Gibt noch ne Reihe mehr ... Einfach mal n Paar Details zu deinem Vorhaben mehr nennen

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Na dann sollte ich vielleicht den Zweck etwas genauer kennzeichnen...

Und zwar sollte ohne genaue Kenntnis der Originaldaten (sondern eben nur deren Hash) erkannt werden, welcher Vergleichssatz am besten passt. Im Prinzip Mustererkennung...

Die Daten wurden z.B. per Funk übertragen, da könnte es also rauschen.
So ganz rein theoretisch müsste man doch dann aus der Distanz (die ja nicht so groß sein kann, so schlecht ist die Verbindung auch nicht) und Kenntnis der Prüfsumme die Originaldaten errechnen können. Also eine Rückwärts-Fehlerkorrektur als genetischen Algorithmus. Kombiniert mit einem Tree sogar gut parallelisierbar.

Und nein, ich will nicht hören dass das nicht geht. So im groben weiß ich es schon, Frage ist halt, ob es eine brauchbare Funktion gibt. Und aus den beiden Posts schließe ich mal auf ein grundsätzliches Ja.

Hauptanwendung sind sicherlich Bereiche, wo man (viel) mehr Rechenleistung als Datenleitung hat (mir ist nur die Raumfahrt eingefallen; wenn nicht hilft Distributed Computing), aber wir arbeiten ja hier theoretisch

Gut, dann schaue nicht bei den Fehlererkennenden, sondern lieber bei den Fehlerkorrigierenden Codes

BCH, Reed-Solom sind da immer wieder gern gesehen ...


Grad RS kann man soweit aufbohren, dass man Codes mit gigantischen Fehlerkorrektur-Leistungen erzeugen kann. RS wird hauptsächlich zwar auf CDs eingesätzt (Rechenleistung ist durchaus nicht zu vernachlässigen) und korrigiert Burst-Fehler (hat man auf optischen Medien halt häufiger).

Was Du nun mit RS machen könntest: Eingabe-Daten nehmen, RS-Code dafür berechnen und dann Daten + RS-Anhängsel übertragen (oder alternativ auch nur das Anhängsel). Wenn Du nun die Datenlänge kennst und einen Test-Datenbblock zum Vergleichen hast, kannst Du anhand der Fehleranzahl, die der RS-Decoder liefert, die ähnlichkeit abfragen; ferner kannst Du durch das Padding (bei Nachrichten kürzer als der RS-Code) sogar ausschließen, welche Nachrichten überhaupt nicht in Frage kommen ...

Kann man einiges an Späßen auf jeden Fall mit treiben ...

P.S.: Für noch mehr Spaß einfach RS interleaven

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.