Penapis Bloom: Adakah sesuatu unsur berada dalam set?

Penapis Bloom (Bloom filter) ialah struktur berkebarangkalian yang membolehkan kita menyatakan, dengan tahap kebarangkalian tertentu, sama ada suatu unsur x berada dalam set M.

Contohnya, dalam sistem kita, kita perlu mengukur berapa kali pengguna mengklik sepanduk iklan. Selepas setiap klik, kita menerima permintaan HTTP GET yang memberitahu bahawa pengguna XYZ telah mengklik iklan 123. Kadangkala pengguna tersilap mengklik dua kali dengan tetikus, jadi kita menerima dua permintaan. Kita mahu menapis permintaan ini supaya hanya satu klik direkodkan dalam pangkalan data.

Oleh itu, kita memerlukan aplikasi yang membaca saluran mesej tentang klik dan menapis pendua. Bagaimanakah kita melakukannya? Setiap mesej mempunyai suatu ID, jadi kita tidak perlu membandingkan keseluruhan mesej; kita hanya perlu menentukan sama ada mesej dengan ID yang sama pernah diproses. Kod JavaScript ringkas yang membuang pendua daripada aliran mesej (di sini, untuk memudahkan, daripada tatasusunan) boleh kelihatan seperti berikut:

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}]
var processedIds = {};

messages.forEach(function(message) {
    if (!processedIds[message.id]) {
        processedIds[message.id] = true;
        console.log(message);
    }
});

// Mencetak: { id: "123" } { id: "456" } { id: "789" }

Penyelesaian ini memadai sehingga ingatan kita habis — dan ingatan itu akan habis suatu hari nanti kerana set processedIds hanya akan terus membesar. Sudah tentu kita boleh menambahkan kod untuk luput data — misalnya, kita sentiasa membuang mesej yang lebih lama daripada satu jam atau seumpamanya.

Masalahnya lebih teruk apabila cara itu pun tidak mencukupi. Bagaimana jika kita perlu menyimpan data sekurang-kurangnya satu hari dalam set processedIds dan kita memproses, misalnya, sepuluh ribu mesej sesaat? Dalam kes terburuk, kita perlu menyimpan sehingga 864 000 000 ID. Jika kita menggunakan uuid v4, setiap ID sepanjang 36 aksara, jadi dalam sehari kita perlu menyimpan sekurang-kurangnya 31 GB. Jumlah itu agak banyak. Bolehkah keperluan ingatan ini dikurangkan?

Penapis Bloom

Daripada menyimpan keseluruhan ID, kita boleh menyimpan nilai cincangnya sahaja. Kita boleh menggunakan murmurhash yang biasa, yang memulangkan integer 32-bit bagi setiap rentetan dan juga mempunyai taburan yang baik:

var murmurhash = require("murmurhash");

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var processedHashedIds = {};

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id);
    if (!processedHashedIds[hashedId]) {
        processedHashedIds[hashedId] = true;
        console.log(message);
    }
});

// Mencetak: { id: "123" } { id: "456" } { id: "789" }

Seterusnya kita menggunakan helah vektor bit, iaitu tatasusunan yang hanya menyimpan sifar dan satu. Jika kita mempunyai fungsi cincang n-bit, kita memerlukan vektor bersaiz 2ⁿ supaya semua output yang mungkin bagi fungsi cincang boleh dialamatkan dalam vektor itu. Ideanya, pada mulanya vektor mengandungi sifar sahaja. Jika fungsi cincang memulangkan nombor 47 bagi input "123", kita hanya menyimpan digit satu dalam vektor pada indeks 47. Dengan cara ini kita menandakan bahawa nilai cincang 47 sudah pernah ditemui.

var n = 8;
var numberOfValues = Math.pow(2, n);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var bitVector = new Array(numberOfValues);

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id) % numberOfValues;
    if (!bitVector[hashedId]) {
        bitVector[hashedId] = true;
        console.log(message);
    }
});

// Mencetak: { id: "123" } { id: "456" } { id: "789" }

Kod % numberOfValues hanya memangkas murmurhash supaya menjadi fungsi cincang n-bit, tidak lebih daripada itu. Dan inilah penapis Bloom, walaupun dalam versi yang sangat ringkas. Masalah pendekatan ini sudah tentu ialah perlanggaran yang pasti berlaku. Nilai input yang berbeza boleh mempunyai nilai cincang output yang sama. Oleh itu, untuk mengurangkan kebarangkalian perlanggaran, kita tidak menggunakan satu fungsi cincang sahaja, tetapi beberapa fungsi. Beberapa fungsi cincang boleh dibina, misalnya, dengan menambahkan garam (salt) kepada nilai input. Fungsi ringkas yang membina fungsi cincang n-bit yang berbeza boleh kelihatan seperti berikut:

var murmurhash = require("murmurhash");

function createNBitHashFunction(n, salt) {
    var upperBound = Math.pow(2, n);
    return function(inputString) {
        return murmurhash.v2(inputString + salt) % upperBound;
    }
}

var firstHashFunction = createNBitHashFunction(8, "nejakaSul");
var secondHashFunction = createNBitHashFunction(8, "nejakaJinaSul");

console.log(firstHashFunction("123")); // 42
console.log(secondHashFunction("123")); // 174

Kelas yang mewakili penapis Bloom boleh ditulis seperti berikut:

function BloomFilter(numberOfHashFunctions, numberOfBits) {
    this.reset(numberOfHashFunctions, numberOfBits);
}

BloomFilter.prototype.reset = function(numberOfHashFunctions, numberOfBits) {
    this.bitVector = new Array(Math.pow(2, numberOfBits));
    this.hashFunctions = [];

    for (var i = 0; i < numberOfHashFunctions; i++) {
        this.hashFunctions.push(createNBitHashFunction(numberOfBits, i.toString()));
    }
}

BloomFilter.prototype.add = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}

Kaedah add menambahkan unsur ke dalam penapis Bloom: kaedah ini mengira nilai cincang dengan semua fungsi cincang dan menyimpan true pada indeks yang sepadan.
Kaedah contains pula menentukan sama ada suatu unsur terkandung dalam penapis Bloom.

Penapis Bloom mudah digunakan:

var bloomFilter = new BloomFilter(3, 8);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];

messages.forEach(function(message) {
    if (!bloomFilter.contains(message.id)) {
        bloomFilter.add(message.id);
        console.log(message);
    }
});

// Mencetak: { id: "123" } { id: "456" } { id: "789" }

Itulah keseluruhan “sihir” penapis Bloom asas. Penapis ini mempunyai sifat asas berikut:

Jika kaedah contains menjawab bahawa suatu unsur tiada dalam penapis Bloom, maksudnya anda memang tidak pernah memasukkan unsur itu.
Jika kaedah itu menjawab bahawa suatu unsur ada dalam penapis Bloom, hal ini tidak semestinya bermakna anda benar-benar telah menyimpan unsur itu — perlanggaran fungsi cincang mungkin telah berlaku.
Secara umumnya, jika anda mahu mengurangkan kebarangkalian jawapan yang salah, tambahkan bilangan fungsi cincang atau besarkan saiznya (iaitu saiz nilai output).
Semakin banyak fungsi cincang yang anda gunakan, semakin perlahan penapis Bloom.
Semakin besar fungsi cincang yang anda gunakan, semakin banyak ruang yang digunakan oleh penapis Bloom.
Sebaik sahaja suatu unsur dimasukkan ke dalam penapis Bloom, unsur itu tidak boleh dibuang.

« Artikel sebelumnya: HyperLogLog: Cara menganggar bilangan nilai unik dengan sangat tepat

Artikel seterusnya: Sifer Caesar »