LogLog: Πώς να εκτιμήσεις το πλήθος των μοναδικών τιμών
Μετά τα προηγούμενα μέρη για το Linear Counting και το Min Value, φτάνουμε επιτέλους στον σχεδόν καλύτερο πιθανοτικό αλγόριθμο για την εκτίμηση του πλήθους των μοναδικών τιμών σε ένα σύνολο δεδομένων, τον LogLog. Καλύτερος είναι μόνο ο μικρός του αδελφός HyperLogLog, που βασίζεται στον LogLog, αλλά γι' αυτόν θα μιλήσουμε την επόμενη φορά.
Ας θυμηθούμε την εκφώνηση του προβλήματος. Στην είσοδο έχουμε ένα σύνολο δεδομένων/πολυσύνολο, για παράδειγμα έναν πίνακα ή μια γεννήτρια αναγνωριστικών. Σε αυτόν τον πίνακα κάποιες τιμές εμφανίζονται πολλές φορές και εμείς θέλουμε να μετρήσουμε πόσες μοναδικές τιμές υπάρχουν. Αυτό το πλήθος θα το λέμε πληθικότητα. Περιμένουμε η πληθικότητα να είναι πραγματικά πολύ μεγάλη, αλλιώς μπορούμε να χρησιμοποιήσουμε συμβατικούς αλγορίθμους.
Η ιδέα του αλγορίθμου LogLog
Φαντάσου ότι έχουμε ένα σύνολο δυαδικών διανυσμάτων. Μην τρομάξεις, για παράδειγμα το 0001011001001100 είναι ένα δυαδικό διάνυσμα μήκους 16. Ας πούμε ότι έχουμε δυαδικά διανύσματα μήκους 32 και ότι έχουμε συνολικά ένα εκατομμύριο από αυτά, όλα εντελώς τυχαία δημιουργημένα. Πόσα διανύσματα θα τελειώνουν σε μηδέν;
Αυτό φυσικά δεν μπορούμε να το γνωρίζουμε με ακρίβεια, αλλά αν τα διανύσματα δημιουργήθηκαν πραγματικά τυχαία, περίπου τα μισά θα τελειώνουν σε μηδέν, δηλαδή 500 χιλιάδες. Πόσα διανύσματα θα τελειώνουν σε 00; Το ένα τέταρτο. Σε 000; Το ένα όγδοο. Και ούτω καθεξής. Μπορούμε να το απεικονίσουμε περίπου έτσι:
μοτίβο διανύσματος ποσοστό επί όλων των διανυσμάτων
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12,5%
...xxx0000 6,25%
... ...
Αν ρωτήσουμε για ένα επίθεμα (το επίθεμα είναι η συμβολοσειρά με την οποία τελειώνει μια άλλη συμβολοσειρά – το αντίθετο του προθέματος) μήκους d, περιμένουμε να βρούμε v διανύσματα που τελειώνουν με αυτό το επίθεμα. Την τιμή v τη βρίσκουμε ως εξής:
όπου N είναι το πλήθος όλων των διανυσμάτων του συνόλου. Το επίθεμα μήκους 3 (για παράδειγμα …010) θα πρέπει να εμφανίζεται σε 1/2^3 N = 1/8 N διανύσματα, δηλαδή στο 12,5% όλων των διανυσμάτων.
Τώρα θα κάνουμε ένα μικρό σοκ στο μυαλό. Έστω ένα πολυσύνολο 1024 μοναδικών διανυσμάτων. Πόσα διανύσματα θα πρέπει να τελειώνουν με το επίθεμα 0000000000; (δέκα μηδενικά) Αντικαθιστούμε στον τύπο και βρίσκουμε
Χα, ένα! Σε χίλια τυχαία δημιουργημένα δυαδικά διανύσματα θα πρέπει να υπάρχει ακριβώς ένα διάνυσμα που τελειώνει με δέκα μηδενικά. Και πώς χρησιμοποιούμε αυτή την πληροφορία για να εκτιμήσουμε το πλήθος των μοναδικών στοιχείων; Μπορούμε να προχωρήσουμε αντίστροφα. Τι γίνεται αν περάσουμε από όλα τα δυαδικά διανύσματα της εισόδου και διαπιστώσουμε ότι στο σύνολο υπάρχει μόνο ένα διάνυσμα που τελειώνει με δέκα μηδενικά; Τότε μπορούμε να εκτιμήσουμε ότι το σύνολο είχε 1024 διανύσματα!
Γενικεύουμε και χτίζουμε τον αλγόριθμο
Στόχος είναι να βρούμε ένα επίθεμα που περιέχεται σε ένα μόνο διάνυσμα και είναι όσο το δυνατόν πιο σύντομο. Αυτό όμως είναι πολύ δύσκολο, γιατί για να βρούμε πραγματικά ένα τέτοιο διάνυσμα θα έπρεπε να αποθηκεύουμε όλα τα επιθέματα, κάτι που δεν θέλουμε, επειδή θα καταλάμβανε υπερβολική μνήμη. Αντί γι' αυτό αρκούμαστε στο να αναζητούμε τη μεγαλύτερη ακολουθία μηδενικών στο τέλος του διανύσματος.
Περνάμε λοιπόν από όλα τα διανύσματα, για καθένα μετράμε πόσα μηδενικά έχει στο τέλος και σε μία μεταβλητή κρατάμε το μέγιστο αυτών των τιμών. Όταν περάσουμε από όλα τα διανύσματα, θα γνωρίζουμε το μήκος του μεγαλύτερου επιθέματος που αποτελείται μόνο από μηδενικά. Αυτό το μήκος το συμβολίζουμε με το γράμμα d. Τώρα τροποποιούμε τον προηγούμενο τύπο ώστε να απομονώσουμε τη μεταβλητή N, δηλαδή ώστε να είναι η έξοδος του αλγορίθμου και όχι η είσοδος. Αντί για v μπορούμε να βάλουμε ένα, επειδή περιμένουμε να βρούμε ακριβώς ένα τέτοιο διάνυσμα, δηλαδή περιμένουμε να ισχύει v=1.
Αν λοιπόν βρούμε το μήκος d του μεγαλύτερου επιθέματος με μηδενικά, εκτιμούμε την πληθικότητα με τον τύπο N=2d.
Πώς θα βρούμε τυχαία δυαδικά διανύσματα;
Με τυχαία δυαδικά διανύσματα ο αλγόριθμός μας ήδη λειτουργεί, αλλά πώς θα εφαρμόσουμε αυτή τη διαδικασία σε πραγματικά δεδομένα; Όπως συνήθως, και εδώ θα χρησιμοποιήσουμε κάποια κατάλληλη συνάρτηση κατακερματισμού. Αν στην είσοδο έχουμε ένα σύνολο δεδομένων, για παράδειγμα αναγνωριστικά (strings), πρώτα υπολογίζουμε το hash τους. Η έξοδος μιας συνάρτησης κατακερματισμού n bit είναι n bit που από πρακτική άποψη μοιάζουν με τυχαία δημιουργημένα δυαδικά διανύσματα.
Τώρα μπορούμε να γράψουμε τον αλγόριθμό μας:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
Η συνάρτηση trailing_zeroes επιστρέφει το πλήθος των μηδενικών στο τέλος του αριθμού. Πώς το κάνει; Αν δεν το κατάλαβες από τον κώδικα, καλύτερα μην ρωτήσεις. Και πόσο επιτυχημένη είναι η συνάρτηση; Για ένα σύνολο που περιείχε εκατό χιλιάδες μοναδικά στοιχεία, η συνάρτηση επέστρεψε την εκτίμηση 524.288.
Χμ…
Δεν είναι ακριβώς καλό, έτσι δεν είναι; Δεν πειράζει όμως! Θα βελτιώσουμε τον αλγόριθμο με τον ίδιο ακριβώς τρόπο όπως τον προηγούμενο Min Value. Χωρίζουμε τα δεδομένα εισόδου σε αρκετές ξένες μεταξύ τους ομάδες, για κάθε ομάδα υπολογίζουμε το μέγιστο επίθεμα μηδενικών και στο τέλος υπολογίζουμε τη μέση τιμή του μήκους του επιθέματος μηδενικών και τη χρησιμοποιούμε για την εκτίμηση του πλήθους των μοναδικών.
Μπορούμε για παράδειγμα να πούμε ότι τα δύο τελευταία bit κάθε διανύσματος θα καθορίζουν τον αριθμό της ομάδας στην οποία ανήκει το διάνυσμα. Αυτά τα έξι διανύσματα
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
μπορούμε να τα χωρίσουμε σε τέσσερις ομάδες ανάλογα με την κατάληξή τους:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Στη συνέχεια υπολογίζουμε το μήκος του μεγαλύτερου επιθέματος μηδενικών σε κάθε διάνυσμα, παραλείποντας όμως τα bit που χρησιμοποιήσαμε ως αριθμό ομάδας. Τα «επιθέματα» μηδενικών τα σημειώνουμε με πράσινο:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Στο τέλος έχουμε τα μήκη των μεγαλύτερων επιθεμάτων μηδενικών από κάθε ομάδα. Από αυτά μπορούμε να υπολογίσουμε τον αριθμητικό μέσο όρο, που μας βγαίνει 2,75. Αντικαθιστούμε την τιμή στον τύπο και βρίσκουμε
Έτσι παίρνουμε τον μέσο αριθμό μοναδικών στοιχείων σε κάθε ομάδα. Που φυσικά δεν ταιριάζει καθόλου, αλλά ας μην μας απασχολεί, για μικρά σύνολα ο αλγόριθμος LogLog δίνει απαίσια αποτελέσματα.
Για να εκτιμήσουμε την πληθικότητα ολόκληρου του συνόλου, πρέπει ακόμη να πολλαπλασιάσουμε αυτή την τιμή με το πλήθος των ομάδων: 6,727 · 4 = 26,908. Ο αλγόριθμος υπολόγισε ότι στο σύνολο υπάρχουν περίπου 27 μοναδικές τιμές. Ήταν έξι, άρα είμαστε τελείως έξω, αλλά αυτό τώρα πραγματικά δεν πειράζει.
Υλοποίηση του αλγορίθμου
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
Η παράμετρος k καθορίζει πόσα bit θα χρησιμοποιηθούν ως δείκτης ομάδας. Αυτή η παράμετρος καθορίζει την ακρίβεια του αλγορίθμου – όσο μεγαλύτερο το k, τόσο μεγαλύτερη η ακρίβεια. Στη μεταβλητή bucket_index φυλάσσεται ο αριθμός της ομάδας. Πώς λειτουργεί αυτή η μαγεία στα δεξιά του ίσον;
Στη μεταβλητή num_buckets είναι το πλήθος των ομάδων, που είναι πάντα δύναμη του δύο. Αν για παράδειγμα k = 3, τότε num_buckets=8. Ο αριθμός 8 στο δυαδικό σύστημα έχει τη μορφή 1000. Αν αφαιρέσουμε ένα, παίρνουμε τον αριθμό 7, που έχει τη μορφή 0111. Μετά την αφαίρεση του ένα από το num_buckets παίρνουμε πάντα έναν αριθμό που έχει στο τέλος k άσους και πριν από αυτούς μόνο μηδενικά. Στη συνέχεια εκτελούμε το λογικό γινόμενο (αυτός είναι ο τελεστής &). Για το διάνυσμα 1110110010100101 η πράξη θα έμοιαζε έτσι:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Ο σκοπός όλης αυτής της μαγείας είναι να πάρουμε έναν αριθμό που στην αρχή περιέχει μόνο μηδενικά και έχει τα τελευταία k bit ίδια με το δοσμένο hash h.
Στη συνέχεια υπολογίζουμε το bucket_hash, που είναι το αρχικό hash από το οποίο έχουμε αφαιρέσει τα τελευταία k bit, μετατοπίζοντας ολόκληρο το hash κατά k bit προς τα δεξιά. Η ολίσθηση λειτουργεί απλά έτσι: μετακινεί όλα τα bit του αριθμού κατά k θέσεις δεξιά και από αριστερά συμπληρώνει τον αριθμό με μηδενικά. (Η ολίσθηση των bit προς τα δεξιά κατά ένα συμπεριφέρεται όπως αν διαιρούσες τον αριθμό με το δύο και πετούσες το υπόλοιπο.) Από το διάνυσμα 1110110010100101 μετά την ολίσθηση κατά τρία θα παίρναμε το 0001110110010100. Αυτό το διάνυσμα θα αποθηκευόταν στη μεταβλητή bucket_hash.
Στη συνέχεια υπολογίζουμε το πλήθος των μηδενικών στο τέλος αυτού του διανύσματος και, αν αυτή η τιμή είναι μεγαλύτερη από την τρέχουσα μέγιστη τιμή που είναι αποθηκευμένη στον πίνακα max_zeroes στη θέση bucket_index, αντικαθιστούμε την τιμή.
Στο τέλος υπολογίζουμε απλώς τον μέσο αριθμό μηδενικών σε όλες τις ομάδες και υπολογίζουμε τον μέσο αριθμό μοναδικών στοιχείων σε κάθε ομάδα (2 ** average_max_zeros). Επειδή έχουμε συνολικά num_buckets ομάδες, πολλαπλασιάζουμε αυτή την τιμή με το πλήθος των ομάδων και έτσι παίρνουμε την τελική εκτίμηση του πλήθους των μοναδικών στοιχείων. Ουφ, και ούτε που πόνεσε. Αποτελέσματα για αρκετά σύνολα δεδομένων που περιέχουν 250.000 μοναδικά στοιχεία και k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Όχι, πάλι λάθος :-(. Όμως είμαστε ήδη αρκετά κοντά, μην ανησυχείς. Πρόσεξε ότι όλα τα αποτελέσματα είναι μεγαλύτερα από το σωστό. Κατά την εκτέλεση του αλγορίθμου συσσωρεύονται διάφορα σφάλματα και γι' αυτό η εκτίμηση είναι αισθητά μεγαλύτερη από το σωστό αποτέλεσμα. Ωστόσο αυτά τα σφάλματα είναι σχετικά σταθερά και μπορούμε να εκτιμήσουμε πόσο μεγάλο ήταν το σφάλμα. Αν πολλαπλασιάσουμε την εκτίμηση με την εμπειρική σταθερά 0,79402, παίρνουμε σημαντικά καλύτερα αποτελέσματα:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Δοκίμασα και ένα πολυσύνολο με πληθικότητα ένα εκατομμύριο, αποτελέσματα:
Αποτέλεσμα Σφάλμα
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Ωραία! Το σφάλμα κυμαίνεται κάτω από 2,5%, που είναι αξιοπρεπής επίδοση. Και αυτός, κυρίες και κύριοι, είναι ο αλγόριθμος LogLog. Η τελική υλοποίηση με την εμπειρική σταθερά μοιάζει έτσι:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
Πώς θα τροποποιήσουμε αυτόν τον αλγόριθμο για να πάρουμε τον θρυλικό και καλύτερο απ' όλους HyperLogLog θα το δούμε την επόμενη φορά. Προς το παρόν ας δούμε πόση μνήμη απαιτεί ο αλγόριθμος.
Απαίτηση σε μνήμη
Ο αλγόριθμος είναι πολύ αποδοτικός ως προς τη μνήμη που καταλαμβάνει. Το μόνο που χρειάζεται να θυμόμαστε είναι ο πίνακας που κρατά τα μέγιστα. Το μήκος αυτού του πίνακα εξαρτάται από την τιμή k, δηλαδή από το πλήθος των bit του διανύσματος που παίρνουμε ως δείκτη ομάδας. Για δοσμένο k έχουμε συνολικά 2k διαφορετικές ομάδες και ο πίνακας των μεγίστων έχει γι' αυτό μήκος 2k. Αυτή την τιμή την ονομάσαμε στην υλοποίηση num_buckets.
Πόσο μεγάλο πρέπει να είναι ένα κελί του πίνακα; Σε αυτό θα αποθηκεύουμε μήκη επιθεμάτων μηδενικών. Μπορώ να σου αποκαλύψω εκ των προτέρων ότι ένα hash 64 bit μάλλον αρκεί για όλα τα νοητά πολυσύνολα του κόσμου, οπότε σε αυτόν τον πίνακα πρέπει να μπορούμε να αποθηκεύσουμε αριθμούς από το 0 (διάνυσμα που αποτελείται μόνο από άσους) έως το 64 (διάνυσμα που αποτελείται μόνο από μηδενικά). Επιπλέον, αν υποθέσουμε ότι το k θα είναι πάντα μεγαλύτερο από μηδέν, τότε αρκεί να αποθηκεύουμε αριθμούς από το 0 έως το 63. Γι' αυτό μας αρκούν, παρακαλώ πολύ, μόλις 6 bit, επειδή 26 = 64.
Ναι, μας αρκεί ένας «πίνακας» στον οποίο κάθε κελί έχει μέγεθος 6 bit. Μπορώ επίσης να σου πω ότι η τιμή k=10 αρκεί για να εκτιμήσουμε αρκετά καλά πληθικότητες έως και εκατοντάδες εκατομμύρια. Ο αλγόριθμος με αυτή τη ρύθμιση θα δημιουργούσε πίνακα μεγέθους 210 = 1024, στον οποίο κάθε κελί καταλαμβάνει 6 bit. Συνολικά αυτός ο πίνακας θα καταλάμβανε 6144 bit, δηλαδή 768 byte. Ούτε ένα kilobyte.
Και αυτό είναι όλο.
Τίποτε άλλο δεν χρειάζεται να αποθηκεύσουμε, τα hash που υπολογίζονται μπορούμε αμέσως να τα πετάμε, μας αρκεί να γνωρίζουμε το πλήθος των μηδενικών στο τέλος του διανύσματος.
Πρόσεξε ότι αν χρησιμοποιούσες μεγαλύτερη συνάρτηση κατακερματισμού, που θα επέστρεφε για παράδειγμα 128 bit, η απαίτηση σε μνήμη δεν θα άλλαζε πολύ. Θα χρειαζόταν να αποθηκεύσουμε αριθμούς από το 0 έως το 127, και γι' αυτό αρκούν 7 bit. Την απαίτηση σε μνήμη καθορίζει λοιπόν κυρίως η παράμετρος k, δηλαδή το πλήθος των ομάδων.
Ο LogLog ταιριάζει κυρίως εκεί όπου χρειάζεται να μετρήσουμε πολυσύνολα με πραγματικά μεγάλη πληθικότητα. Όπως φάνηκε και στο απλό παράδειγμα παραπάνω, ο LogLog δεν τα καταφέρνει ιδανικά με πολυσύνολα που έχουν μικρή πληθικότητα. Και σε αυτό όμως μπορούμε να βοηθήσουμε, για παράδειγμα αν διαπιστώσουμε ότι το πολυσύνολο έχει χαμηλή πληθικότητα, χρησιμοποιούμε για την εκτίμηση έναν άλλο αλγόριθμο, όπως το Linear Counting που περιγράφηκε νωρίτερα. Και γι' αυτό θα μιλήσουμε την επόμενη φορά.
Πηγές:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (από εκεί είναι λίγο πολύ αντιγραμμένος ο κώδικας του LogLog)
Κεφάλαια: Linear counting, Min Value, LogLog, HyperLogLog
