Lập trình BloomFilter sử dụng Scala

Ở bài blog trước, chúng ta đã tìm hiểu các khái niệm cơ bản về Bloom Filter (Giới thiệu về Bloom Filter), ở bài blog lần này, ta sẽ sử dụng Scala để lập trình 1 Bloom Filter đơn giản sử dụng 2 hàm hash là MurmurHash và hàm hashCode của mỗi object của Scala.

Trước tiên là khung của class BloomFilter và companion object cho class này

class BloomFilter[A](val length: Int, val numHash: Int) { def this(length: Int) = this(length, 3) private val bitArr = new util.BitSet(length) } object BloomFilter { def apply[A](length: Int, numHash: Int): BloomFilter[A] = new BloomFilter(length, numHash) def apply[A](length: Int): BloomFilter[A] = new BloomFilter(length) }

Trong đoạn code này:

Như đã viết ở bài trước, 1 Bloom Filter có hai thuộc tính là độ dài của bit array và số hàm hash, nên trong constructor của class BloomFilter, giá trị của 2 thuộc tính này cần được set.
Ta cũng cung cấp 1 constructor khác lấy giá trị mặc định cho số hàm hash là 3.
Sử dụng Bitset của Java để lưu trữ chuỗi các bit
Các phần tử được add vào Bloom Filter có thể là các giá trị với type khác nhau nên class Bloom Filter phải là 1 generic class.
Trong companion object, 2 phương thức apply cũng được cung cấp để tránh việc phải trực tiếp gọi constructor của class Bloom Filter BloomFilter(50, 3) // Thay vì new BloomFilter(50, 3)

Tiếp theo, ta sẽ add thêm một số helper functions vào companion object để có thể tính toán được giá trị tối ưu của độ dài bit array và số hàm hash cho một giá trị false positive mong muốn. Trong bài blog trước, ta đã có 2 công thức để tính các giá trị này như sau:

Độ đài bit array

* (m là độ dài bit vector, n là số phần tử của tập hợp, p là xác suất xảy ra false positive)*

Số hàm hash

* (m là độ dài bit vector, n là số phần tử của tập hợp, k là số hàm hash)*

Sử dụng 2 công thức trên thì method để tính giá trị tối ưu của độ dài bit array vào số hàm hash cho một giá trị false positive sẽ như sau

object BloomFilter { ... def recommendSetting(numItems: Double, falsePositiveRate: Double): (Int, Int) = { val recommendedBitLength = ceil(-(numItems * log(falsePositiveRate)) / pow(log(2), 2)) val recommendedNumHash = round(log(2) * recommendedBitLength / numItems) (recommendedBitLength.toInt, recommendedNumHash.toInt) } .. }

Để kiểm tra với một giá trị độ dài bit array và số hàm hash thì giá trị false positive tương ứng là bao nhiêu thì sử dụng công thức:

* (m là độ dài bit vector, n là số phần tử của tập hợp, k là số hàm hash)*

Ta có method như sau

object BloomFilter { ... def estimateFalsePositiveRate(numItems: Double, bitLength: Int, numHash: Int): Double = { pow(1 - pow(1 - 1.0/bitLength, numHash * numItems), numHash) } }

Kết quả khi test thử 2 method trên với số lượng item sẽ đưa vào bloom filter là 50 và positive rate mong muốn là 0.3

BloomFilter.recommendSetting(50, 0.3) // => res0: (Int, Int) = (126,2) BloomFilter.estimateFalsePositiveRate(50, 126, 2) // => res1: Double = 0.3016629599514688

Quay trở lại class BloomFilter, logic quan trọng nhất là phần pass giá trị của phần tử qua lần lượt các hàm hash rồi từ giá trị đầu ra của các hàm này xác định vị trí index của bit array bị set thành 1. Như đã nói ở đầu bài thì ở đây ta sẽ sử dụng 2 hàm hash là hashCode có sẵn của bất kì object nào của Scala và hàm MurmurHash làm cơ sở để tạo tất cả các hàm hash khác với công thức đã viết ở bài trước:

hash_i(x, m) = (hash_a(x) + i × hash_b(x)) mod m

Hàm apply sau sẽ trả về vị trí các bit có giá trị bị set bằng 1, khi thêm 1 phần tử vào Bloom Filter

class BloomFilter[A](val length: Int, val numHash: Int) { ... def apply(el: A) = { val hash1 = el.## val hash2 = abs(MurmurHash3.mixLast(0, hash1)) (0 until numHash).map { i => val h = hash1 + i * hash2 val nextHash = if (h < 0) ~h else h nextHash % length } } }

Sử dụng hàm này ta có thể dễ dàng viết tiếp 2 hàm chính của BloomFilter là thêm phần tử và check phần tử

Thêm -> set tất cả các bit ở vị trí trả về từ hàm apply thành 1
Check -> nếu tất cả các bít ở vị trí trả về từ hàm apply là 1 thì phần tử này đã được add vào Bloom Filter

class BloomFilter[A](val length: Int, val numHash: Int) { ... def add(el: A): Unit = apply(el).foreach(pos => bitArr.set(pos)) def contains(el: A) = apply(el).forall(pos => bitArr.get(pos)) ... }

Vậy là Bloom Filter của chúng ta đã hoàn tất, việc còn lại chỉ là test thử tính năng

val a = BloomFilter[Any](125, 3) a.add("Programming") a.add(4) a("Programming") // => res2: scala.collection.immutable.IndexedSeq[Int] = Vector(96, 14, 0) a(4) // => res3: scala.collection.immutable.IndexedSeq[Int] = Vector(4, 29, 54) a.contains("Programming") // => res4: Boolean = true a.contains("Gaming") // => res5: Boolean = false a.contains(4) // => res6: Boolean = true a.contains(7) // => res7: Boolean = false

Có thể thấy việc lập trình các tính năng cơ bản của Bloom Filter khá là đơn giản, toàn bộ code không quá 50 dòng. Tuy nhiên, trong thực tế, ngoài các tính năng cơ bản ta còn phải tính đến việc lưu trữ BloomFitler thế nào, serialization ra sao, rồi chọn các hàm hash cho phù hợp, tính toán hiệu năng… Dù vậy, với cấu trúc khá đơn giản, dễ lập trình, tính hiệu quả cao, Bloom Filter là một lựa chọn tốt cho những bài toán liên quan đến việc kiểm tra phần tử có thuộc 1 tập hợp hay không (database lookup, cache…)

Tham khảo: