So projizieren Sie einen Hash gleichmäßig auf eine feste Anzahl von Buckets

Hallo Statistiker,

Ich habe eine Quelle, die Hashes generiert (z. B. das Berechnen eines Strings mit einem Zeitstempel und anderen Informationen und das Hashing mit md5) und ich möchte es in eine feste Anzahl von Buckets projizieren (z. B. 100).

Beispiel-Hash: 0fb916f0b174c66fd35ef078d861a367

Was ich zuerst dachte, war, nur das erste Zeichen des Hashs zu verwenden, um einen Eimer auszuwählen, aber dies führt zu einer wild ungleichmäßigen Projektion (dh einige Buchstaben erscheinen sehr selten und andere sehr häufig).

Dann habe ich versucht, diese Hexa-Zeichenfolge mit der Summe der Zeichenwerte in eine Ganzzahl umzuwandeln, und dann mit dem Modulo einen Bucket ausgewählt:

import sys

for line in sys.stdin:
    i = 0
    for c in line:
        i += ord(c)
    print i%100

Es scheint in der Praxis zu funktionieren, aber ich weiß nicht, ob es einen gesunden Menschenverstand oder theoretische Ergebnisse gibt, die erklären könnten, warum und inwieweit dies zutrifft.

[Bearbeiten] Nach einigem Überlegen kam ich zu folgendem Schluss: Theoretisch können Sie den Hash in eine (sehr große) Ganzzahl umwandeln, indem Sie ihn als Zahl interpretieren: i = h [0] + 16 * h [1] + 16 * 16 * h [2] ... + 16 ^ 31 * h [31] (jeder Buchstabe steht für eine Hexadezimalzahl). Dann könnten Sie diese große Zahl modulieren, um sie auf den Bucket Space zu projizieren. [/Bearbeiten]

Vielen Dank !

uniform oDDsKooL
quelle

Ein echter Hash sollte solche ungleichmäßigen Ergebnisse nicht liefern. Sind Sie sicher, dass der Hash-Algorithmus korrekt implementiert ist?

whuber

Ich bezweifle, dass es einen Fehler im Hashing-Algorithmus selbst gibt. Ich vermute jedoch, dass die Zeichen des Hex-Digests nicht streng einheitlich und unabhängig verteilt sind.

ODDsKooL

Das finde ich zweifelhaft: Ein "kryptografisch sicherer" Hash wie MD5 sollte eine gleichmäßige Verteilung aller Ziffern aufweisen, es sei denn, die Verteilung der Eingabe hat etwas ganz Besonderes ("speziell" bedeutet eng mit dem MD5-Algorithmus verbunden). Ihre vorgeschlagene Lösung läuft darauf hinaus, den Hash erneut zu hashen, was überhaupt nicht notwendig sein sollte.

whuber

Das erste Zeichen des Md5-Hash sollte einheitlich sein. Aber Sie würden nur 16 Werte erhalten (es ist eine hexadezimale Codierung)

leonbloy

Vielen Dank, dass Sie auf diesem Punkt bestanden haben. Ich zähle erneut auf den ersten Buchstaben der Hashes und es scheint tatsächlich gleichmäßig verteilt zu sein: {'a': 789, 'c': 769, 'b': 755, 'e': 730, 'd': 804, 'f': 749, '1': 716, '0': 758, '3': 734, '2': 735, '5': 787, '4': 756, '7': 771, '6': 721, '9': 764, '8': 765}. Daher wird meine Frage mehr oder weniger beantwortet, da ich diesen Zufallsgenerator mit 16 Zuständen nur auf einen Raum mit 100 Zuständen projizieren muss. Dies kann mithilfe der ersten beiden Buchstaben des Hashs erfolgen, um eine Ganzzahl des Bereichs [0,16+] zu generieren 16 * 16] und modulo es auf 100. Stört es mich, wenn ich meine eigene Frage beantworte;)?

ODDsKooL

Antworten:

NB: Formulieren Sie die Antwort, die aus der Diskussion in Kommentaren hervorgegangen ist, so, dass sie für interessierte Personen leichter zu lesen ist

(aktualisierte Version)

$B$

Die wichtigsten Schritte sind:

$e$ $i$ $2^N$
$\mathcal{R} \times [0, 1[$ $p = \frac{i}{2^N}$
$b_i$ $\frac{b_i}{B} \le p \lt \frac{b_{i+1}}{B}$

Für 1. ist eine beliebte Lösung die Verwendung von MurmurHash , um eine 64- oder 128-Bit-Ganzzahl zu generieren.

$j = 1..B$ $p$ $[\frac{b_j}{B}, \frac{b_{j+1}}{B}[$

Im (Python-) Pseudocode könnte die Gesamtprozedur sein:

def hash_to_bucket(e, B):
    i = murmurhash3.to_long128(str(e))
    p = i / float(2**128)
    for j in range(0, B):
        if j/float(B) <= p and (j+1)/float(B) > p:
            return j+1
    return B

(vorherige Version, wirklich nicht optimal)

Die erste Beobachtung ist, dass der n- te Buchstabe des Hashs in Bezug auf das Alphabet gleichmäßig verteilt sein sollte (das hier 16 Buchstaben lang ist - danke an @leonbloy für den Hinweis).

~~Um es dann auf einen Bereich von [0,100 [zu projizieren, besteht der Trick darin, 2 Buchstaben aus dem Hash (z. B. 1. und 2. Position) zu nehmen und damit eine ganze Zahl zu generieren:~~

~~int_value = int(hash[0])+16*int(hash[1])~~

~~Dieser Wert lebt im Bereich [0,16+ (16-1) * 16 [, daher müssen wir nur Modulo auf 100 einen Eimer in dem [0, 100 [Bereich zu erzeugen:~~ Wie in den Kommentaren darauf hingewiesen, tun Dies wirkt sich auf die Gleichmäßigkeit der Verteilung aus, da der erste Buchstabe einflussreicher ist als der zweite.

bucket = int_value % 100

Theoretisch können Sie den gesamten Hash in eine (sehr große) Ganzzahl umwandeln, indem Sie ihn als Zahl interpretieren: i = h [0] + 16 * h [1] + 16 * 16 * h [2] ... + 16 ^ 31 * h [31] (jeder Buchstabe steht für eine Hexadezimalzahl). Dann könnten Sie diese große Zahl modulieren, um sie auf den Bucket Space zu projizieren. Man kann dann feststellen, dass das Modulo von i in eine verteilende und additive Operation zerlegt werden kann:

\begin{aligned} i \mod N = ( \\ (h_{0} \mod N) \\ + (16 \mod N \times h_{1} \mod N) \\ + . . . \\ + (16^{31} \mod N \times h_{31} \mod N) \\ ) \mod N \end{aligned}

$\begin{align} i \mod N = (&\\ &(h_0 \mod N) \\ &+ (16 \mod N \times h_1 \mod N) \\ &+ ... \\ &+ (16^{31} \mod N \times h_{31} \mod N)\\ &) \mod N \end{align}$

oDDsKooL
quelle

Verbesserungen dieser Antwort sind willkommen.

ODDsKooL

Dies scheint keine gute Lösung zu sein, denn wenn "zwei beliebige Buchstaben" "gleichmäßig verteilt" sind, erhalten die Eimer von bis normalerweise 50% mehr Treffer pro Eimer als die Eimer von bis . Tatsächlich verwenden Sie eine schreckliche Hash-Funktion, um den Hash selbst in 100 Buckets zu hashen. Warum nicht einfach eine bekannte gute Hash-Funktion für diesen Zweck verwenden?

0

$0$

55

$55$

56

$56$

99

$99$

whuber

Genau. Eine bessere handgerollte Lösung wäre, einen Teil der Hex-Zeichenfolge zu nehmen, der beispielsweise eine Ganzzahl von 16 Bit Speicherplatz bedeuten könnte. Teilen Sie dann den tatsächlichen Wert durch den maximalen 16-Bit-Ganzzahlwert und multiplizieren Sie ihn mit hundert und rund.

spdrnl

Wenn Sie eine Anzahl von Buckets in Form von , können Sie nur die letzten Bits des Hashs verwenden (und dies entspricht Hexadezimalzeichen). Auf diese Weise ist das Ergebnis der Modulo-Operation genau das gleiche wie bei der Berechnung bei vollständiger Konvertierung in eine Ganzzahl. Es kann auch OK, wenn Sie eine Reihe von Schaufeln verwenden , die keine Zweierpotenz ist .

2^{n}

$2^n$

n

$n$

2

$2$

Alesc

@whuber Ich stimme zu, dass dies nicht ganz optimal ist und die Projektion auf ein kontinuierliches [0,1 [Intervall viel besser ist. Ich habe das auch experimentell überprüft. Ich werde die Antwort bearbeiten, um diese Ansicht widerzuspiegeln.

ODDsKooL

Ich hatte ein ähnliches Problem und fand eine andere Lösung, die in jeder Sprache schneller und einfacher implementiert werden kann.

Mein erster Gedanke war, Artikel schnell und gleichmäßig in einer festen Anzahl von Eimern zu versenden, und um skalierbar zu sein, sollte ich die Zufälligkeit nachahmen.

Also habe ich diese kleine Funktion codiert, die eine Gleitkommazahl in [0, 1 [mit einem String (oder einer beliebigen Art von Daten) zurückgibt.

Hier in Python:

import math
def pseudo_random_checksum(s, precision=10000):
    x = sum([ord(c) * math.sin(i + 1) for i,c in enumerate(s)]) * precision
    return x - math.floor(x)

Natürlich ist es nicht zufällig, tatsächlich ist es nicht einmal pseudozufällig, dieselben Daten geben immer dieselbe Prüfsumme zurück. Aber es verhält sich zufällig und ist ziemlich schnell.

Sie können Artikel in N Buckets einfach versenden und später abrufen, indem Sie jeden Artikel einfach der Bucket-Nummer math.floor (N * pseudo_random_checksum (item)) zuweisen.

fbparis
quelle

Haben Sie eine Intuition oder einen Beweis dafür, dass die Proben gleichmäßig in [0,1] platziert werden?

Sud_

@sud_ Diese Funktion wird hier diskutiert: stackoverflow.com/a/19303725/1608467

fbparis

@sud_ Außerdem habe ich einige Tests durchgeführt, um es mit einem legitimen Zufallszahlengenerator zu vergleichen, und es war in jedem Fall, den ich getestet habe, in Ordnung.

fbparis