Lineare Zählung: Wie man die Anzahl der eindeutigen Werte schätzt

Wie könnte man die Anzahl der eindeutigen Werte in einem Datensatz zählen, wenn es wirklich sehr viele Daten gäbe? Wir könnten zum Beispiel einen Dienst haben, der die Anzahl der eindeutigen Nutzer auf einer großen Website oder vielleicht auf der gesamten .cz/.com/.whatever-Domäne oder so misst.

Naiver Ansatz

Ok, da gibt es nichts zu lösen, wir gehen einfach durch die Daten und speichern jeden Wert nur einmal in einer geeigneten Datenstruktur. In Python könnten wir das so schreiben (der Code ist unnötig langatmig, das ist gewollt):

nonunique_values = [1, 2, 3, 2, 4, 1, 1, 3, 5, 2] def count_unique(values): found = set() for item in values: if item not in found: found.add(item) return len(found) print count_unique(nonunique_values) # 5

Das funktioniert. Okay, aber was ist, wenn die Daten aus 36-stelligen eindeutigen v4-Kennungen bestehen, und was ist, wenn die eindeutigen IDs etwa zehn Millionen sind? Nun... das Programm berechnet immer noch den richtigen Wert, aber wie viel Speicherplatz braucht es? Wir können versuchen, es auszurechnen. Der Einfachheit halber nehmen wir an, dass wir die uuid wirklich als 36-Zeichen-String speichern. Eine uuid nimmt also 36 Byte ein, zehn Millionen ids benötigen 360 MB.

Nicht gerade klein, seien wir ehrlich. Wenn es hundert Millionen eindeutige IDs gäbe, wären wir im Gigabyte-Bereich. Und wir zählen immer noch nur, was die Daten benötigen. Nimmt man noch den Overhead hinzu, der z. B. durch Python/JavaScript entsteht, kann man mit zehn Millionen IDs in die Größenordnung von Gigabytes kommen:

Das wollen Sie nicht. Wie kommt man da wieder raus?

Wir könnten versuchen, die Iden selbst irgendwie effizienter zu speichern, wir könnten C statt Python verwenden, was den Speicherbedarf erheblich reduzieren würde, aber es wäre immer noch nicht dasselbe, und ein solches Programm würde immer noch unglaublich viel Platz beanspruchen. Die Frage bleibt: Müssen wir wirklich auf den Buchstaben genau wissen, ob diese eindeutigen Werte genau 9.563.618 sind? Würde etwas passieren, wenn wir mit einer Anzahl von 9.547.666 arbeiten würden? Wenn Ihre Antwort lautet, dass dies der Fall ist und dass Sie es genau wissen wollen, dann tun Sie bitte, was Sie wollen. Andernfalls lassen Sie uns Verfahren demonstrieren, mit denen wir die Anzahl der eindeutigen Werte in einem Datensatz möglichst genau, schnell und mit minimalem Speicherbedarf schätzen können.

Hash-Funktion - unsere Rettung

Wir betrachten eine Hash-Funktion, die eine Zeichenkette als Eingabe annimmt und eine n-Bit-Zahl als Ausgabe zurückgibt. Wenn Sie eher an Hash-Funktionen gewöhnt sind, die "eine Zeichenkette zurückgeben", dann stellen Sie sich einfach vor, dass die Zeichenkette weiter in eine Zahl umgewandelt wird, da ist nichts dabei. Die Anzahl der Bits gibt dann an, wie groß die Zahl ist. Eine 8-Bit-Funktion gibt eine Zahl zurück, die acht Bits benötigt, und die acht Bits können²⁸ verschiedene Werte speichern, in der Regel ganze Zahlen von 0 bis 255. Wir werden mit der 24-Bit-Hash-Funktion weiterarbeiten. Eine solche Funktion gibt²²⁴ verschiedene Werte zurück, also 16.777.216.

Anstatt die Werte selbst zu speichern, werden wir ihre 24-Bit-Hashes speichern. Wir benötigen 30 MB, um zehn Millionen 24-Bit-Hashes zu speichern. Das ist um eine Größenordnung besser als die bisherigen 360 MB. Der Code könnte wie folgt aussehen:

def nhash(item, n): return hash(item) % (2 ** n) nonunique_values = [1, 2, 3, 2, 4, 1, 1, 3, 5, 2] def count_unique_using_nhash(values): found = set() for item in values: checksum = nhash(item, 24) if checksum not in found: found.add(checksum) return len(found) print count_unique_using_nhash(nonunique_values) # 5

Die Hash-Funktion ist eine systemeigene Python-Funktion und gibt einen Integer zurück, die nhash-Funktion zeigt eine naive Implementierung einer n-Bit-Hash-Funktion; es ist nicht wichtig zu verstehen, wie sie funktioniert, da sie sowieso nicht richtig funktioniert - das Ergebnis der Funktion benötigt keine 24 Bits, aber das ist jetzt egal, mir geht es um das Prinzip.

Dann kommt die Funktion count_unique_using_nhash, die eindeutige Werte zählt. Sie geht alle Werte durch, berechnet ihren Hash und speichert diesen Hash in der gefundenen Variablen, wenn der Wert nicht schon dort ist.

Das Problem bei diesem Verfahren ist, dass die Hash-Funktion möglicherweise dieselbe Prüfsumme für verschiedene Zeichenfolgen zurückgibt - es kann zu einer Kollision kommen. Je mehr solcher Kollisionen auftreten, desto ungenauer ist das Ergebnis. Die Funktion count_unique_using_nhash liefert fast immer weniger eindeutige Werte als tatsächlich vorhanden sind.

Und welche Hashing-Funktion soll man wählen? Das ist eigentlich nicht so wichtig, aber eine Variante von MurmurHash wird im Allgemeinen empfohlen.

Bitmaps

Haben Sie in Grundlagen der C-Programmierung aufgepasst? Wenn ja, dann kennen Sie Bitmaps. Wie können Sie sie nutzen?

Lassen Sie uns die Idee im Feld skizzieren. Da wir keine berechneten Prüfsummen speichern müssen, können wir ein Array der Länge²²⁴ erstellen und alle Elemente auf Null initialisieren. In dem Moment, in dem wir auf eine Prüfsumme treffen - die eine Zahl ist! - schreiben wir eine Eins in das Prüfsummenindexfeld, um anzuzeigen, dass wir diese Prüfsumme bereits gefunden haben. Die Anzahl der eindeutigen Elemente ist dann ungefähr gleich der Anzahl der Einsen in diesem Feld. Der Code könnte wie folgt aussehen:

def count_unique_using_array(values): # list of 2^24 initialized to the same zeros array = [0] * (2 ** 24) for item in values: array[nhash(item, 24)] = 1 return sum(array) print count_unique_using_array(nonunique_values)

Die Verwendung von Arrays ist in diesem Fall jedoch sehr speicherintensiv, da wir in jeder Zelle entweder eine Eins oder eine Null speichern müssen. Stattdessen können wir ein Bit-Array verwenden. Zum Verständnis: Eine ganze Zahl kann z. B. in 32 Bits gespeichert werden. Wenn wir die Zahl 354 in Binärzahlen umwandeln, erhalten wir 101100010. Die Zahl 354 würde also im Computer als 32-Bit-Ganzzahl gespeichert werden (ignorieren wir die Details, ja?), etwa so:

00000000 00000000 00000001 01100010

Das ist doch ein schönes Format, das wir verwenden könnten, oder? Denn wir wollen in unserer Funktion nur Einsen und Nullen speichern, und jetzt haben wir gerade herausgefunden, dass eine gewöhnliche Zahl eigentlich nichts anderes als ein Haufen Nullen und Einsen ist (wie alles in einem Computer, schätze ich...). Kurz gesagt, wir können bitweise Operatoren verwenden, um eine Eins so zu speichern, dass sie tatsächlich ein Bit einnimmt.

Kehren wir zu unserer Array-Funktion zurück. Wenn wir sie in Bit-Arrays umschreiben, bräuchten wir für eine 24-Bit-Hashing-Funktion nur ein Bit-Array mit²²⁴ Bits, was 2 MiB entspricht. Das ist ein ordentliches Upgrade!

Bei einer 32-Bit-Hashing-Funktion mit²³² verschiedenen Ausgabewerten, also 4.294.967.296, würden wir ein Bit-Array von einem halben Gigabyte benötigen. Das ist gar nicht so schlecht, wenn man bedenkt, dass wir auf diese Weise in der Lage sind, Unikate in der Größenordnung von Milliarden zu zählen.

Lineare Zählung

Ich habe bereits erwähnt, dass wir bei der Verwendung der Hashing-Funktion nur eine Schätzung der Anzahl der eindeutigen Werte erhalten. Diese Schätzung wird umso ungenauer, je näher die Zahl der eindeutigen Werte an der Zahl der verschiedenen Ausgabewerte der Hash-Funktion liegt. Wenn wir einen Datensatz mit fünf Milliarden eindeutigen Werten haben, ist es logisch, dass wir diese mit einer 24-Bit-Hash-Funktion nicht zählen können.

Die Schätzung, die wir mit Hash-Funktionen berechnen, kann jedoch weiter verfeinert werden. Dazu wird eine einfache Idee verwendet: Je mehr eindeutige Werte ein Datensatz enthält, desto wahrscheinlicher ist es, dass es im Laufe der Zeit zu Kollisionen kommt. (Kollision = zwei verschiedene Eingaben haben die gleiche Ausgabe der Hash-Funktion, die gleiche Prüfsumme.) Jetzt werden wir ein bisschen rechnen, also werden wir ein paar Variablen einführen:

• Wir arbeiten mit einer n-Bit-Hash-Funktion h.
• Die Anzahl aller möglichen Ausgaben der Funktion h ist also gleich ²ⁿ. Wir werden diese Zahl mit m bezeichnen, also: ^m=2n.
• Das Bit-Array, in dem wir speichern, welche Prüfsummen wir gefunden haben, wird mit dem Großbuchstaben A bezeichnet. Das Array A hat die Länge m.
• Wenn wir unseren Algorithmus durch den gesamten Datensatz laufen lassen, werden einige Werte im Bitfeld Null und einige Eins sein. Wir interessieren uns hauptsächlich für das Verhältnis "Anzahl der Nullen geteilt durch die Länge des Feldes", das uns den relativen Anteil der Nullen im Bitfeld angibt. Anfänglich ist das Verhältnis 1, da die Anordnung mit Nullen initialisiert wird. Wäre es fifty-fifty, wäre der Anteil gleich der Hälfte usw. Wir bezeichnen diesen Wert mit Z und berechnen ihn als Z = Anzahl der Nullen / m.

Je höher der Wert von Z ist, desto sicherer sind wir, dass unsere Schätzung der Anzahl der Unikate richtig ist. Wenn wir z. B. einen leeren Datensatz durchgehen, bleiben alle Nullen im Bit-Array übrig und der Wert von Z ist eins - wir sind also absolut sicher, dass es in unserem Datensatz genauso viele eindeutige Elemente gibt wie Einsen im Bit-Array - also null.

Wenn der Wert von Z gleich 0,99 ist, bedeutet dies, dass die Bitmatrix zu einem Hundertstel aus Einsen besteht. 99 % des Arrays enthalten Nullen. Dies ist immer noch gut, denn es ist wahrscheinlich, dass bei der Berechnung nicht allzu viele Kollisionen aufgetreten sind und keine oder nur eine minimale Korrektur erforderlich ist. Beträgt der Z-Wert jedoch 0,05, so sind nur noch 5 % des Feldes mit Nullen gefüllt, und wir sind bei der Berechnung wahrscheinlich auf viele, viele Kollisionen gestoßen - eine große Korrektur ist erforderlich.

Aber wie berechnet man diese Korrektur? Wir verwenden den Logarithmus, eine Funktion, die diese Form hat:

Wir interessieren uns für den roten Teil auf dem Intervall (0, 1>). Wenn wir Z auf der x-Achse auftragen, werden wir feststellen, dass der y-Wert umso näher bei Null liegt, je höher Z ist. Umgekehrt gilt: Je kleiner Z ist, desto kleiner ist der y-Wert. Wir berechnen die resultierende Schätzung durch Multiplikation dieser Zahl mit -m. Beachten Sie, dass wir für einen hinreichend kleinen Wert von Z eine Zahl erhalten, die sogar kleiner als -1 ist, und wenn wir diesen Wert mit -m multiplizieren, erhalten wir eine Schätzung, die größer als m ist: Wir haben geschätzt, dass die Anzahl der Unikate größer ist als die Anzahl aller möglichen Prüfsummen, die aus der Hash-Funktion h hervorgehen können.

Die vollständige Formel zur Berechnung der Anzahl p der eindeutigen Werte sieht wie folgt aus:

$$\Large p=-m\cdot \ln Z$$

Eine Implementierung (ohne Bitfelder, nur einfache Felder) könnte wie folgt aussehen:

from uuid import uuid4 from math import log number_of_unique_values = 10000 nonunique_values = [uuid4() for _ in xrange(number_of_unique_values))] nonunique_values += nonunique_values def nhash(item, n):
    return hash(item) % (2 ** n) def count_unique_using_array(values, n): array = [0] * (2 ** n) for item in values: array[nhash(item, n)] = 1 return sum(array) def linear_counting(values, n):
    estimate = count_unique_using_array(values, n) m = 2 ** n number_of_zeros = m - estimate Z = float(number_of_zeros) / m # log ist hier der natürliche Logarithmus zur Basis e p = (-m) * log(Z) p = int(round(p)) print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \ (estimate, m, number_of_zeros, Z, p) return p print "Kardinalität: %s" % linear_counting(nonunique_values, 16)

In der Funktion linear_counting berechnen wir zunächst die erste Schätzung mit dem vorherigen Algorithmus, der eine n-Bit-Hash-Funktion verwendet. Dann wird der Anteil der Nullen im Array berechnet und die Korrektur anhand der Formel durchgeführt. Der Logarithmus im Code ist der natürliche Logarithmus. Die Variable nonunique_values enthält die Anzahl_der_eindeutigen_Werte von eindeutigen Zeichenketten, in diesem Beispiel gibt es also zehntausend eindeutige Werte in der Liste der nonunique_values. Der seltsame Code in Zeile 6 stellt sicher, dass sich mehrere identische Werte im Array befinden: Wir hängen einfach dieselbe Rangliste an das Ende der Liste an, so dass jeder Wert zweimal im Array enthalten ist. Und dann wird gezählt. Die Funktion sollte im Idealfall zurückgeben, dass die Liste zehntausend Unikate enthält. Ausgabe:

Debug-Info: estimate=9289, m=65536, number_of_zeros=56247, Z=0.858261108398, p=10016 Kardinalität: 10016

Da immer eine andere Liste von nicht eindeutigen Werten erzeugt wird, variieren die Ergebnisse bei jedem Aufruf. Wir haben eine 16-Bit-Hash-Funktion verwendet. Wie man sieht, ergab die erste Schätzung der Funktion count_unique_using_array, dass die Liste 9289 Unikate enthält. Wir haben diese Schätzung auf 10.016 verfeinert, indem wir sie korrigiert haben, was schon ziemlich gut ist: Unsere Schätzung ist nur 0,16 % größer, während sie vorher 7,11 % kleiner war - das ist ziemlich viel.

Wenn wir eine "größere" Hash-Funktion nehmen würden, zum Beispiel eine 24-Bit-Hash-Funktion, würden wir ein genaueres Ergebnis erhalten:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, Z=0.999404132366, p=10000 Cardinality: 10000

Die ursprüngliche Schätzung selbst war in Ordnung, die Verfeinerung hat bereits bis zu zehntausend erreicht. Als Beispiel können wir eine Million eindeutige IDs ausprobieren, d. h. number_of_unique_values = 1000000. Mit der 24-Bit-Hash-Funktion kommen wir zu diesen Ergebnissen:

Debug-Info: estimate=971033, m=16777216, number_of_zeros=15806183, Z=0.94212192297, p=1000267 Kardinalität: 1000267

Es geht. Gleichzeitig sollte das Array, wenn wir es als Bit-Array implementieren, nur die oben erwähnten zwei Megabyte (+ das, was die Sprache verbraucht) verbrauchen. Ziemlich gut für mich. Aber wir können es besser machen! Viel besser. Aber für das nächste Mal.

In der Zwischenzeit können Sie den Artikel A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF] lesen. Oder Sie können mit dem nächsten Teil der Serie fortfahren: dem Min-Wert-Algorithmus.