Αλγόριθμοι ροής και φίλτρα Bloom - ανδρείκελα

Στην καρδιά πολλών αλγορίθμων ροής είναι τα φίλτρα Bloom. Δημιουργήθηκε σχεδόν πριν από 50 χρόνια από τον Burton H. Bloom, σε μια εποχή όπου η επιστήμη των υπολογιστών ήταν ακόμη αρκετά νεαρή, ο αρχικός σκοπός του δημιουργού αυτού του αλγορίθμου ήταν να εμποδίσει τον χώρο (μνήμη) ή / και τον χρόνο (πολυπλοκότητα) επιτρεπόμενα σφάλματα. Το πρωτότυπο χαρτί του ονομάζεται Διαστήματος / Χρόνος Συναλλαγών σε Hash Κωδικοποίηση με Επιτρεπόμενα Σφάλματα.

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

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

Μια σημαντική σκέψη για τα φίλτρα Bloom είναι ότι μπορούν να εμφανιστούν ψευδώς θετικά, αλλά τα ψευδώς αρνητικά δεν μπορούν. Για παράδειγμα, μια ροή δεδομένων μπορεί να περιέχει δεδομένα παρακολούθησης σε πραγματικό χρόνο για μια μονάδα παραγωγής ενέργειας. Όταν χρησιμοποιείτε ένα φίλτρο Bloom, η ανάλυση της ροής δεδομένων θα δείξει ότι οι αναμενόμενες αναγνώσεις αποτελούν πιθανώς μέρος του συνόλου των επιτρεπόμενων αναγνώσεων, επιτρέποντας μερικά λάθη. Ωστόσο, όταν εμφανιστεί ένα σφάλμα στο σύστημα, η ίδια ανάλυση δείχνει ότι οι μετρήσεις δεν είναι μέρος του συνόλου επιτρεπόμενων αναγνώσεων. Τα ψευδώς θετικά είναι απίθανο να προκαλέσουν προβλήματα, αλλά η απουσία ψευδών αρνητικών σημαίνει ότι όλοι παραμένουν ασφαλείς. Λόγω της πιθανότητας ψευδών θετικών, τα φίλτρα όπως το φίλτρο Bloom είναι πιθανοτικές δομές δεδομένων - δεν παρέχουν μια συγκεκριμένη απάντηση, αλλά μια πιθανή.

Οι Hashes, οι μεμονωμένες καταχωρήσεις σε ένα πίνακα κατακερματισμού, είναι γρήγορες επειδή λειτουργούν σαν το ευρετήριο ενός βιβλίου. Χρησιμοποιείτε μια λειτουργία κατακερματισμού για την παραγωγή του κατακερματισμού. η είσοδος είναι ένα στοιχείο που περιέχει πολύπλοκα δεδομένα και η έξοδος είναι ένας απλός αριθμός που λειτουργεί ως δείκτης αυτού του στοιχείου. Μια συνάρτηση κατακερματισμού είναι καθοριστική επειδή παράγει τον ίδιο αριθμό κάθε φορά που την τροφοδοτείτε με μια συγκεκριμένη εισαγωγή δεδομένων.Χρησιμοποιείτε το hash για να εντοπίσετε τις πολύπλοκες πληροφορίες που χρειάζεστε. Τα φίλτρα Bloom είναι χρήσιμα επειδή είναι ένας οικονομικός τρόπος για να καταγράψετε ίχνη πολλών στοιχείων χωρίς να τα αποθηκεύσετε ως τραπέζι κατακερματισμού. Λειτουργούν με έναν απλό τρόπο και χρησιμοποιούν ως κύρια συστατικά τα ακόλουθα:

Ένα διάνυσμα δυαδικών ψηφίων:

• Μια λίστα στοιχείων bit, όπου κάθε bit στο στοιχείο μπορεί να έχει τιμή 0 ή 1. Η λίστα είναι μια μακρά αριθμός bits που ονομάζεται m. Όσο μεγαλύτερος m είναι, τόσο καλύτερα, αν και υπάρχουν τρόποι για τον καλύτερο καθορισμό του μεγέθους του. Μια σειρά λειτουργιών κατακερματισμού:
• Κάθε συνάρτηση κατακερματισμού αντιπροσωπεύει διαφορετική τιμή. Οι λειτουργίες κατακερματισμού μπορούν να ραγίζουν γρήγορα τα δεδομένα και να παράγουν ομοιόμορφα κατανεμημένα αποτελέσματα, τα οποία είναι αποτελέσματα που κυμαίνονται εξίσου από τις ελάχιστες έως τις μέγιστες τιμές εξόδου του κατακερματισμού.