Πώς να βρείτε τον αριθμό των στοιχείων σε μια ροή δεδομένων - ανδρείκελα

Παρόλο που ένα φίλτρο Bloom μπορεί να εντοπίσει αντικείμενα που φτάνουν από ένα ρεύμα, δεν μπορεί να πει πόσα αντικείμενα υπάρχουν. Ένα διάνυσμα λίγο γεμάτο από αυτά μπορεί (ανάλογα με τον αριθμό των hashes και την πιθανότητα σύγκρουσης) να κρύψει τον πραγματικό αριθμό αντικειμένων που έχουν χυθεί στην ίδια διεύθυνση.

Η γνώση του διακριτού αριθμού αντικειμένων είναι χρήσιμη σε διάφορες καταστάσεις, όπως όταν θέλετε να μάθετε πόσοι διαφορετικοί χρήστες έχουν δει μια συγκεκριμένη σελίδα ιστότοπου ή τον αριθμό διαφορετικών ερωτημάτων μηχανών αναζήτησης. Η αποθήκευση όλων των στοιχείων και η εύρεση των αντιγράφων μεταξύ τους δεν μπορεί να λειτουργήσει με εκατομμύρια στοιχεία, ειδικά από ένα ρεύμα. Όταν θέλετε να γνωρίζετε τον αριθμό των ξεχωριστών αντικειμένων σε μια ροή, εξακολουθείτε να πρέπει να βασίζεστε σε μια λειτουργία κατακερματισμού, αλλά η προσέγγιση περιλαμβάνει τη λήψη αριθμητικού σκίτσου.

Το σκίτσο σημαίνει ότι παίρνεις μια προσέγγιση, δηλαδή μια άστοχη αλλά όχι εντελώς λάθος τιμή ως απάντηση. Η προσέγγιση είναι αποδεκτή επειδή η πραγματική τιμή δεν είναι πολύ μακριά από αυτήν. Σε αυτόν τον έξυπνο αλγόριθμο, HyperLogLog, που βασίζεται στην πιθανότητα και την προσέγγιση, παρατηρείτε τα χαρακτηριστικά των αριθμών που παράγονται από τη ροή. Το HyperLogLog προέρχεται από τις μελέτες των επιστημόνων υπολογιστών Nigel Martin και Philippe Flajolet. Η Flajolet βελτίωσε τον αρχικό αλγόριθμό τους, Flajolet-Martin (ή τον αλγόριθμο LogLog), στην πιο ισχυρή έκδοση HyperLogLog, η οποία λειτουργεί ως εξής:

1. Ένας hash μετατρέπει κάθε στοιχείο που λαμβάνεται από το ρεύμα σε έναν αριθμό.
2. Ο αλγόριθμος μετατρέπει τον αριθμό σε δυαδικό, το βασικό αριθμητικό πρότυπο που χρησιμοποιούν οι υπολογιστές.
3. Ο αλγόριθμος μετρά τον αριθμό των αρχικών μηδενών στον δυαδικό αριθμό και τα κομμάτια του μέγιστου αριθμού που βλέπει, που είναι n.
4. Ο αλγόριθμος υπολογίζει τον αριθμό διακριτών στοιχείων που πέρασαν στη ροή χρησιμοποιώντας το n. Ο αριθμός των ξεχωριστών στοιχείων είναι 2 ^ n.

Για παράδειγμα, το πρώτο στοιχείο της συμβολοσειράς είναι η λέξη

σκύλος. Ο αλγόριθμος το έχει μετατρέψει σε ακέραιη τιμή και το μετατρέπει σε δυαδικό, με αποτέλεσμα 01101010. Μόνο ένα μηδέν εμφανίζεται στην αρχή του αριθμού, οπότε ο αλγόριθμος το καταγράφει ως τον μέγιστο αριθμό των μηδενικών τελικών παρατηρήσεων. Ο αλγόριθμος βλέπει τότε τις λέξεις παπαγάλος και λύκος, των οποίων τα δυαδικά ισοδύναμα είναι 11101011 και 01101110, αφήνοντας το n αμετάβλητο. Ωστόσο, όταν η λέξη cat περάσει, η έξοδος είναι 00101110, έτσι ώστε το n να γίνει 2. Για να εκτιμηθεί ο αριθμός των ξεχωριστών στοιχείων, ο αλγόριθμος υπολογίζει 2 ^ n, δηλαδή 2 ^ 2 = 4. Το σχήμα δείχνει αυτή τη διαδικασία. Μετρώντας μόνο τα αρχικά μηδενικά.

Το τέχνασμα του αλγορίθμου είναι ότι εάν ο κατακερματισμός σας παράγει τυχαία αποτελέσματα, εξίσου κατανεμημένα (όπως σε ένα φίλτρο Bloom), εξετάζοντας τη δυαδική αναπαράσταση, μπορείτε να υπολογίσετε την πιθανότητα εμφάνισης μιας ακολουθίας μηδενικών. Επειδή η πιθανότητα ενός μόνο δυαδικού αριθμού να είναι 0 είναι ένας στους δύο, για τον υπολογισμό της πιθανότητας ακολουθιών μηδενικών, απλά πολλαπλασιάζετε αυτή την πιθανότητα 1/2 όσες φορές το μήκος της ακολουθίας των μηδενικών:

50 τοις εκατό (1/2) πιθανότητα για αριθμούς ξεκινώντας με 0

• 25 τοις εκατό (1/2 * 1/2) πιθανότητα για αριθμούς ξεκινώντας με 00
• 12. 5% (1/2 * 1/2 * 1/2) πιθανότητα για αριθμούς που αρχίζουν με 000
• (1/2) ^ k πιθανότητα για αριθμούς που αρχίζουν με k μηδενικά (χρησιμοποιείτε δυνάμεις για ταχύτερους υπολογισμούς πολλαπλών πολλαπλασιασμών ίδιος αριθμός)
• Όσο λιγότεροι είναι οι αριθμοί που βλέπει το HyperLogLog, τόσο μεγαλύτερη είναι η ανακριβότητα. Η ακρίβεια αυξάνεται όταν χρησιμοποιείτε τον υπολογισμό του HyperLogLog πολλές φορές χρησιμοποιώντας διαφορετικές λειτουργίες κατακερματισμού και μεσολαβεί ο μέσος όρος των απαντήσεων από κάθε υπολογισμό, αλλά ο hashing πολλές φορές απαιτεί χρόνο και τα ρεύματα είναι γρήγορα. Ως εναλλακτική λύση, μπορείτε να χρησιμοποιήσετε την ίδια κατακερματισμό αλλά να διαιρέσετε το ρεύμα σε ομάδες (όπως διαχωρίζοντας τα στοιχεία σε ομάδες κατά την άφιξή τους με βάση την παραγγελία τους) και για κάθε ομάδα, παρακολουθείτε τον μέγιστο αριθμό μηδενικών τελών. Στο τέλος, υπολογίζετε την εκτίμηση του ξεχωριστού στοιχείου για κάθε ομάδα και υπολογίζετε τον αριθμητικό μέσο όρο όλων των εκτιμήσεων. Αυτή η προσέγγιση είναι ο στοχαστικός μέσος όρος και παρέχει ακριβέστερες εκτιμήσεις από την εφαρμογή του αλγορίθμου σε ολόκληρο το ρεύμα.